/* * Peg Soliteire * * conjugate でなければ 15 手、conjugate なら 18 手 (H.O.Davis) * * ------- board address for ------------ * program solution diagram * 0 1 2 a b c * 3 4 5 d e f * 6 7 8 9 10 11 12 g h i j k l m * 13 14 15 16 17 18 19 n o p x P O N * 20 21 22 23 24 25 26 M L K J L H G * 27 28 29 F E D * 30 31 32 C B A */ #include <stdio.h> #include <signal.h> #include <time.h> #define SIZE 33 /* # of holes */ #define MAX_MOVE 31 /* SIZE - 2 */ int jt[][SIZE] = { /* jump table */ /* over, to, over, to, .. from */ { 1, 2, 3, 8, -1}, /* 0 */ { 4, 9, -1}, /* 1 */ { 1, 0, 5, 10, -1}, /* 2 */ { 4, 5, 8, 15, -1}, /* 3 */ { 9, 16, -1}, /* 4 */ { 4, 3, 10, 17, -1}, /* 5 */ { 7, 8, 13, 20, -1}, /* 6 */ { 8, 9, 14, 21, -1}, /* 7 */ { 9, 10, 3, 0, 7, 6, 15, 22, -1}, /* 8 */ { 10, 11, 4, 1, 8, 7, 16, 23, -1}, /* 9 */ { 11, 12, 5, 2, 9, 8, 17, 24, -1}, /* 10 */ { 10, 9, 18, 25, -1}, /* 11 */ { 11, 10, 19, 26, -1}, /* 12 */ { 14, 15, -1}, /* 13 */ { 15, 16, -1}, /* 14 */ { 16, 17, 8, 3, 14, 13, 22, 27, -1}, /* 15 */ { 17, 18, 9, 4, 15, 14, 23, 28, -1}, /* 16 */ { 18, 19, 10, 5, 16, 15, 24, 29, -1}, /* 17 */ { 17, 16, -1}, /* 18 */ { 18, 17, -1}, /* 19 */ { 21, 22, 13, 6, -1}, /* 20 */ { 22, 23, 14, 7, -1}, /* 21 */ { 23, 24, 15, 8, 21, 20, 27, 30, -1}, /* 22 */ { 24, 25, 16, 9, 22, 21, 28, 31, -1}, /* 23 */ { 25, 26, 17, 10, 23, 22, 29, 32, -1}, /* 24 */ { 18, 11, 24, 23, -1}, /* 25 */ { 19, 12, 25, 24, -1}, /* 26 */ { 28, 29, 22, 15, -1}, /* 27 */ { 23, 16, -1}, /* 28 */ { 24, 17, 28, 27, -1}, /* 29 */ { 31, 32, 27, 22, -1}, /* 30 */ { 28, 23, -1}, /* 31 */ { 29, 24, 31, 30, -1} /* 32 */ }; int b[SIZE] = { /* board */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int move[MAX_MOVE][3]; /* from, to, by */ char lastsol[65]; /* last solution */ int minmove; /* minumum move */ char bestsol[65]; /* best solution */ int cnt = 0; /* solution counter */ time_t start, end; int vflg; char *cmd; main(argc, argv) char **argv; { void onint(); char *s; cmd = argv[0]; while (--argc > 0 && (*++argv)[0] == '-') for (s = argv[0]+1; *s; s++) switch(*s) { case 'v': vflg++; break; default: Usage(); } minmove = 32; time(&start); signal(SIGINT, onint); /* 対称解を除去するスマートな方法を思いつけない */ forward(0, 4, 9, 16); /* 4 からスタート */ forward(1, 7, 8, 9); /* 対称解のかなりを避ける */ search(2); /* 後は虱潰し */ time(&end); /* ここまでたどりついたことがない */ printf("総数 %d 個, 時間 %d Sec\n", cnt, end - start ); return 0; } /* バックトラックで n 回目の飛び越しから検索 */ search(n) { int from, by, to, i; if (n == MAX_MOVE && b[16]) { /* move vector */ outsol(); /* move illustration */ if (vflg) disp(); } else { for (from = 0; from < SIZE; from++) if (b[from]) { for (i = 0; (by = jt[from][i++]) != -1; ) { to = jt[from][i++]; if (b[by] && !b[to]) { /* jumpable */ forward(n, from, by, to); search(n + 1); back(from, by, to); } } } } } /* from から by を飛び越して to に移動 */ forward(n, from, by, to) { b[from] = 0; b[by] = 0; b[to] = 1; move[n][0] = from; move[n][1] = to; move[n][2] = by; } /* to から by を埋めもどして from に戻る */ back(from, by, to) { b[from] = 1; b[by] = 1; b[to] = 0; } /* 解の出力 */ outsol() { int i, j, k, n; n = 32; for (i = 0; i < MAX_MOVE; i++) { k = move[i][0]; lastsol[i*2] = (k == 16) ? 'x' : ((k < 16) ? k + 'a' : 32 - k + 'A'); k = move[i][1]; lastsol[i*2+1] = (k == 16) ? 'x' : ((k < 16) ? k + 'a' : 32 - k + 'A'); if (0 < i && move[i-1][1] == move[i][0]) n--; } lastsol[i*2] = '\0'; printf("%d %d %s\n", ++cnt, n, lastsol); /* 最小手順解を更新 */ if (n < minmove) { minmove = n; strcpy(bestsol, lastsol); } } void onint() { time(&end); printf("\nCurrent best solution in %d sec\n", end - start); printf("%d move: %s\n", minmove, bestsol); exit(0); } /* 以下、主としてデバック用 */ int bd[SIZE]; disp() { int i, j, k; for (i = 0; i < SIZE; i++) bd[i] = 1; bd[16] = 0; dispbd(); for (i = 0, j = 1; i < MAX_MOVE; i++, j++) { bd[move[i][0]] = bd[move[i][2]] = -1; bd[move[i][1]] = 1; dispbd(); for ( ; j < MAX_MOVE; i++, j++) { if (move[i][1] != move[j][0]) break; bd[move[j][0]] = bd[move[j][2]] = -1; bd[move[j][1]] = 1; dispbd(); } } } dispbd() { int i, j, k; for (i = k = 0; i < 2; i++) { if (bd[k] == -1) { printf(" ."); bd[k++] = 0; } else printf(" %d", bd[k++]); for (j = 0; j < 2; j++) if (bd[k] == -1) { printf(" ."); bd[k++] = 0; } else printf(" %d", bd[k++]); printf("\n"); } for (i = 0; i < 3; i++) { for (j = 0; j < 7; j++) if (bd[k] == -1) { printf(" ."); bd[k++] = 0; } else printf(" %d", bd[k++]); printf("\n"); } for (i = 0; i < 2; i++) { if (bd[k] == -1) { printf(" ."); bd[k++] = 0; } else printf(" %d", bd[k++]); for (j = 0; j < 2; j++) if (bd[k] == -1) { printf(" ."); bd[k++] = 0; } else printf(" %d", bd[k++]); printf("\n"); } printf("\n"); } Usage() { static char *t[] = { "コマンド %s - Peg Solitaire を解く", "構文 %s [-v]", "得られた解を「解番号 手数 ペグの移動順」で表示しますが、移動順は下記の座標系", "に置ける移動元と移動先の2文字の連続で表示しています。", " a b c", " d e f", " g h i j k l m", " n o p x P O N", " M L K J I H G", " F E D", " C B A", "例えば、「ex」は「e を j 超しに x に移動」という意味です。-v を指定するとこれ", "らの移動を図示し、Ctrl-C で打ち切ると、それまでの最小手数の解の1つを表示して", "終了します。" }; int i; for (i = 0; t[i] != NULL; i++) { fprintf(stderr, t[i], cmd); fprintf(stderr, "\n"); } exit(1); }