Counting Cram game positions in C

This code counts the number of possible positions in the game of Cram on a mxn board.

EDIT 1: In the original question I mistakenly mentioned that this number is equal to the number of domino tilings. While the two are related, this is wrong.

This is the first C code I've written in a long time and I wonder whether there are better ways to solve it, especially in terms of:

• the handling of 2D arrays (or whether something like a bitset might be better),
• the data-structure to hold the results (I'm using the hash table from uthash),
• combining the two for loops which are placing dominoes horizontally and vertically, respectively.

My approach is to represent the board as a 2D bool array and iterate over it until I find two adjacent free cells. I then create a copy of the array, fill those cells with a domino (by setting their value to true) and continue searching recursively.

As this will yield some configurations multiple times, I store a binary representation of each position in a hash set and only consider positions I haven't encountered before. My assumption is that generating these numbers and using them as the key for the hash table is faster than doing array comparison.

X | - | -
----------
X | X | -
----------
- | X | -

For example, the above board would be represented as 1 * 2^0 + 0 * 2^1 + 0 * 2^2 + 1 * 2^3 + 1 * 2^4 + 0 * 2^5 + 0 * 2^6 + 1 * 2^7 + 0 * 2^8 = 153.

EDIT 2: This will only work for boards with less than 8 * sizeof(long long) fields.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include "uthash.h"

/*
* Count the number of game positions in CRAM and DJUV
* Usage: positions width height
*/

struct board {
int key;
UT_hash_handle hh;
};

long long key(int h, int w, bool b[h][w]) {
long long key = 0;
for (int i = 0; i < w * h; i++) {
key += b[i % h][i / h] << i;
}
return key;
}

struct board *positions(int h, int w, bool b[][w], struct board *map) {
int bin_key = key(h, w, b);
struct board *s;
HASH_FIND_INT(map, &bin_key, s);
if (s == NULL) {
s = malloc(sizeof(struct board));
s -> key = bin_key;
for (int j = 0; j < w; j++) {
for (int i = 0; i < h - 1; i++) {
if (!b[i][j] && !b[i + 1][j]) {
bool b1[h][w];
memcpy(&b1, &b, h * w * sizeof(bool));
b1[i][j] = 1;
b1[i + 1][j] = 1;
map = positions(h, w, b1, map);
}
}
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w - 1; j++) {
if (!b[i][j] && !b[i][j + 1]) {
bool b1[h][w];
memcpy(&b1, &b, h * w * sizeof(bool));
b1[i][j] = 1;
b1[i][j + 1] = 1;
map = positions(h, w, b1, map);
}
}
}
return map;
}

int main(int argc, char *argv[]) {
if (argc != 3) {
printf("usage: positions height width\n");
return 1;
}
int h = atoi(argv);
int w = atoi(argv);
if (h*w >= 8 * sizeof(long long)) {
printf("Board is too large\n");
return 1;
}
bool b[h][w];
memset(b, 0, h * w * sizeof(bool));
struct board *map = NULL;
map = positions(h, w, b, map);
printf("%u\n", HASH_COUNT(map));
return 0;
}

Here is my Python implementation (same idea) for reference.

EDIT 3: I've implemented the same algorithm using a bitset and it's significantly faster:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include "uthash.h"

/*
* Count the number of game positions in CRAM and DJUV using a bitmap
* Usage: positions width height
*/

const unsigned char h_d = 0b11; // horizontal domino
unsigned char v_d; // vertical domino (value depends on width)

struct board {
int key;
UT_hash_handle hh;
};

struct board *positions(int h, int w, long long b, struct board *map) {
struct board *s;
HASH_FIND_INT(map, &b, s);
if (s == NULL) {
s = malloc(sizeof(struct board));
s -> key = b;
for (int i=0; i<h*w; i++) {
if (i%w!=w-1 && !(b & h_d << i)) {
map = positions(h, w, b | h_d << i, map);
}
if (i<w*(h-1) && !(b & (v_d << i))) {
map = positions(h, w, b | v_d << i, map);
}
}
}
return map;
}

int main(int argc, char *argv[]) {
if (argc != 3) {
printf("usage: positions height width\n");
return 1;
}
int h = atoi(argv);
int w = atoi(argv);
if (h*w >= 8 * sizeof(long long)) {
printf("Board is too large\n");
return 1;
}
struct board *map = NULL;
v_d = 1 | 1<<w;
map = positions(h,w, 0, map);
printf("%u\n", HASH_COUNT(map));
return 0;
}