Counting Cram game positions in C

Question

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;
    HASH_ADD_INT(map, key, s);
    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[0][0], &b[0][0], 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[0][0], &b[0][0], 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[1]);
  int w = atoi(argv[2]);
  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;
    HASH_ADD_INT(map, key, s);
    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[1]);
  int w = atoi(argv[2]);
  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;
}