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;
}