数理パズルの一つにナイト・ツアー(https://en.wikipedia.org/wiki/Knight%27s_tour)
というものがあります。
nが6以下のときについてn×n board における directed open tour を
以下のコードで数時間かけて数えあげたのですが、
n = 6 のとき0通り(正しくは6637920通り)になるのはどうしてでしょうか?
#include <stdio.h>
int used = 0;
int search(int x, int y, int w, int h, int depth){
int cnt = 0;
// はみ出したり、一度通った場所に来てはダメ
if (x < 0 || w <= x || y < 0 || h <= y || (used & (1 << (x + y * w))) > 0) return 0;
if (depth == w * h) return 1;
used += 1 << (x + y * w);
cnt += search(x + 2, y - 1, w, h, depth + 1);
cnt += search(x + 2, y + 1, w, h, depth + 1);
cnt += search(x - 2, y - 1, w, h, depth + 1);
cnt += search(x - 2, y + 1, w, h, depth + 1);
cnt += search(x + 1, y - 2, w, h, depth + 1);
cnt += search(x + 1, y + 2, w, h, depth + 1);
cnt += search(x - 1, y - 2, w, h, depth + 1);
cnt += search(x - 1, y + 2, w, h, depth + 1);
used -= 1 << (x + y * w);
return cnt;
}
int main(void){
int w;
for (w = 1; w < 7; w++){
int total = 0;
int i;
// (i % w, i / w)を始点とする経路
for (i = 0; i < w * w; i++){
total += search(i % w, i / w, w, w, 1);
}
printf("%d\n", total);
}
return 0;
}
実行結果
1
0
0
0
1728
0