/* *** hanoi1.c: 「ハノイの塔」の探索版プログラム *** * (2004.06.24 YH) * * 状態空間探索により「ハノイの塔」の解を求める。 * * 探索には search.c の探索エンジンを用いる。 * *** コンパイルの仕方 * % cc -o hanoi1 hanoi1.c *  search.c を直接取り込んでいるので、分割コンパイルは不要。 */ #define MAXDISK 10 // 円盤の最大枚数 #define MAXLINK 20000 // 1000 以上のリンクが必要なので上限値を定義 #include "search.c" // 分割コンパイルでなく、直接 search.c を取り込む /* *** 状態は、各円盤がどの軸にあるかを3進数で表す。 */ #define MAXSTATE 59049 // = 3^10 #define A 0 #define B 1 #define C 2 #define FULL 0x07 int states[MAXSTATE]; // 状態ノード。内容は最短経路長 int ndisk = 3; // 円盤の枚数(デフォールト 3) int nstate, initial_state, final_state; void init() { int i; for (i=0, nstate=1; i MAXDISK)) { fprintf(stderr, "%s: %d%s\n", "枚数", ndisk, "(1...10 枚の間であること)"); exit(1); } init(); n = search(states+initial_state, method); len = answer_length(); ans = (int **)answer_path(1); printf("%s: %d %s: %d (%s: %d, %s: %d, %s: %d)\n", "解の個数", n, "長さ", len, "状態数", nstate, "割当リンク総数", l_assigned, "極大リンク数", l_max); if (answer_flag == 0) exit(0); for (i=1; i<=len; i++) { int this = ans[i]-states, prev = ans[i-1]-states; for (j=1;; j++) { if (this % 3 != prev % 3) { printf("%4d: %s %2d %s %c %s %c %s\n", i, "円盤", j, "を", "ABC"[prev%3], "から", "ABC"[this%3], "へ"); break; } this /= 3; prev /= 3; } } }