16307


数理パズルの一つにナイト・ツアー（<https://en.wikipedia.org/wiki/Knight%27s_tour>）  
というものがあります。

nが6以下のときについてn×n board における directed open tour を  
以下のコードで数時間かけて数えあげたのですが、  
n = 6 のとき0通り（正しくは6637920通り）になるのはどうしてでしょうか？

[code]

    #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;
    }
    
[/code]

実行結果  
1  
0  
0  
0  
1728  
0


CC BY-SA 3.0
2015-09-06T06:56:57.477
16301
2015-09-06T11:00:12.553
2015-09-06T10:46:03.947
5363
5363
question
c アルゴリズム
n×n board におけるナイト・ツアーの数えあげについて


`int used`が32ビット整数で6×6=36ビットの状態を表せていないのでは？


CC BY-SA 3.0
2015-09-06T11:00:12.553
16307
2015-09-06T11:00:12.553
5750
16301
answer