2

数理パズルの一つにナイト・ツアー(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

4
  • 1
    オフトピなのでコメントにて。数時間かかったとありますが、以下のようにすることで時間短縮が図れます。(1) 縦横半分ずつに割ると、それぞれ線対称・点対称になりますので、1/4だけ計算するだけで済みます。奇数の場合はもうちょっと必要ですが。また、正方形なら 1/8 にできるかも(未検証)。 (2) 単に訪問済か否かではなく、マス毎に、そこへ到達できる未訪問のマス数を管理 (桂馬飛びの位置にあるマスを訪問する度に減っていきます) し、次の訪問先の候補を決める際、(2-1) (今の位置による減算前で) 残り1のマスがあったら、そこへ問答無用で飛ぶ。残り1が複数あったら、片方には絶対に到達できなくなるのでその時点で探索打ち切り。
    – yoh2
    Commented 2015年9月10日 15:34
  • 上記を実装することにより、5x5では、質問のコードで1.6秒かかっているのが0.05秒に短縮されました。6x6では、質問のコードは未検証ですが、短縮後は3分強でした。また、(2)による枝刈りは、(2-1)、(2-2)の他にももっとできそうな感じです。
    – yoh2
    Commented 2015年9月10日 15:37
  • (2-2)とは何のことでしょうか? また、高速化についての質問をしました。(ja.stackoverflow.com/questions/16525/…)
    – TOM
    Commented 2015年9月11日 12:44
  • (2-2)は番号を振り忘れました。「残り1が複数あったら、片方には絶対に到達できなくなるのでその時点で探索打ち切り。」のことです。この辺、もうちょっと考えが整理できて、さらに速くなったので新しい質問のところに回答します。
    – yoh2
    Commented 2015年9月11日 14:14

1 件の回答 1

2

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

6
  • long long used = 0LL に変えて再計算してみます。
    – TOM
    Commented 2015年9月6日 11:40
  • 1
    1 << (x + y * w) となっている部分も 1LL << (x + y * w) とする必要があるのではないでしょうか。
    – user9156
    Commented 2015年9月6日 12:31
  • 1
    1 << (x + y * w) となっている部分が3箇所もありますね。もう一度再計算してみます。
    – TOM
    Commented 2015年9月6日 12:57
  • 1
    @Manyama 私の方では計算が終了しました。結果は「6637920」で一致しています。
    – user9156
    Commented 2015年9月6日 22:18
  • 1
    結果が「6637920」となることを確認できました。used に関する4箇所を直せばよいということでした。
    – TOM
    Commented 2015年9月7日 11:30

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。