今回は 5 行 5 列盤の裏表パズルに挑戦しましょう。最初に 5 行 5 列盤の最長手数を求めてみます。前回 の「裏表パズルの偶奇性」で説明したように、5 行 5 列盤の局面の総数は 663,552 通りあります。局面の総数が多いので、同一局面のチェックには「ハッシュ法」を使うことにします。それから、盤面を配列で表すと数値に変換する処理が必要になるので、盤面は整数値で表すことにします。白をビットオフ、黒をビットオンと定義すると、盤面は 0 - 0x1ffffff で表すことができます。
列を裏返しにする関数 reverse_line は次のようになります。
リスト:列を裏返す int reverse_line( int board, int n ) { int p0 = line_table[n][0]; int p1 = line_table[n][1]; int p2 = line_table[n][2]; int p3 = line_table[n][3]; int p4 = line_table[n][4]; if( ((board >> p0) & 0x01) == ((board >> p4) & 0x01) ){ board ^= biton[p0]; board ^= biton[p4]; } if( ((board >> p1) & 0x01) == ((board >> p3) & 0x01) ){ board ^= biton[p1]; board ^= biton[p3]; } board ^= biton[p2]; return board; }
reverse_line の引数 board が盤面、n が裏返しにする列の番号です。配列 line_table から位置を取り出して、変数 p0 - p4 にセットします。
最初に、p0 と p4 のビットを比較します。p0 の場合、board >> p0 と右シフトして 0x01 と AND を計算すると、p0 のビットがオンであれば値は 1 に、ビットがオフであれば値は 0 になります。p4 の場合も同様に計算します。そして、その値が等しい場合は p0 と p4 のビットを反転させます。各位置のビットオンの値は配列 biton に格納されているので、board と biton[p0], biton[p4] の XOR を計算するだけです。
p1 と p3 のビットも同様です。p2 のビットは無条件に反転させます。最後に、列 n を裏返しにした board を返します。
幅優先探索を行う関数 solve_b は次のようになります。
リスト:幅優先探索 /* リストの定義 */ typedef struct { int board; int next; } CELL; CELL state[MAX_STATE + 1]; /* 局面 */ char move[MAX_STATE]; /* 手数 */ int hash_table[HASH_SIZE]; /* ハッシュ表 */ /* 幅優先探索 */ void solve_b( void ) { int front = 0, rear = 1; /* 初期化 */ init_hash(); state[0].board = 0; move[0] = 0; insert_hash( 0 ); /* 探索 */ while( front < rear ){ int i, b = state[front].board; for( i = 0; i < LINE; i++ ){ state[rear].board = reverse_line( b, i ); if( insert_hash( rear ) ){ /* 登録 */ move[rear] = move[front] + 1; rear++; } } front++; } printf("局面の総数 %d\n", rear ); print_answer( rear ); }
ハッシュ法は パズルでプログラミング第 3 回(後編):ハッシュ法 と同じく、連結リストを使って実装します。CELL がセルを表す構造体で、メンバ変数 board が盤面を表し、next が次のセルを表します。セルは配列 state に格納します。
最初に init_hash でハッシュ表を初期化し、state[0].board に白一色の盤面 (0) をセットし、手数を表す move[0] に 0 をセットします。そして、insert_hash で state[0] をハッシュ表に登録します。insert_hash は新しい局面であればハッシュ表に登録して TRUE を返します。同じ局面がある場合は FALSE を返します。
あとは単純な幅優先探索です。とくに難しいところはないと思います。詳細は プログラムリスト1 をお読みくださいませ。
それでは実行結果を示します。5 行 5 列盤の最長手数は 13 手、全部で 4608 通りのパターンがあります。実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で約 34 秒かかりました。けっこう時間がかかりますね。ハッシュ表をもう少し大きくするか、あるいは、最小完全ハッシュ関数を作成した方が速くなるかもしれません。興味のある方は挑戦してみてください。
最長手数の局面の例を図に示します。黒の個数が一番少ないパターンからいくつか選んでみました。
□□■□□ □□■□□ □□■□□ □□■□□ □□□□□ □□■□□ ■□■■□ ■□■■□ ■■■□□ □□□□□ □□■□□ □□□□□ □□□□□ □□□□□ □□□□□ 図:最長手数の局面の例 (5 * 5 盤)
生成された局面は全部で 663,552 通り、これは偶奇性で計算した結果と一致します。実際に 13 手で解けるか、反復深化でプログラムを作ってみたのですが、時間がかかりすぎて途中で断念しました。手数が長いので、単純な反復深化ではダメですね。下限値枝刈り法も考えてみたのですが、効率のよい下限値の求め方がわかりません。何かよいアイデアがありましたら、ぜひ教えてくださいね。
そこで、オーソドックスに幅優先探索でプログラムを作ってみました。スタートとゴールの双方向から探索することで、M.Hiroi のオンボロマシン (Pentium 166 MHz) でも 1 秒かからずに解くことができます。興味のある方は プログラムリスト2 をお読みくださいませ。
最短手順の一例を図に示します。
↓ ↓ →□□■□□ ■■□■■ ■■□■■ ■■□■■ ■■□■■ →■■□■■ □□■□□ □□■□□ →□□■□□ ■■□■■ ■■□■■ ■■□■■ ■■□■■ →■■□■■ ■□■■□ ■□■■□ →■□■■□ ■□□■□ □□□■□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ 0 1 2 3 4 5 6 ↓ ↓ ↓ ↓ □□■□□ □■■□□ ■■■□□ →■■■□□ ■■□□□ ■□□□□ □□□□□ □□■□□ □■■□□ →■■■□□ ■■□□□ ■■□□□ ■□□□□ □□□□□ □□□□□ □■□□□ ■■□□□ ■■□□□ ■■□□□ ■□□□□ □□□□□ □□□□□ □■□□□ ■■□□□ ■■□□□ ■■□□□ ■□□□□ □□□□□ □□□□□ □■□□□ ■■□□□ ■■□□□ ■■□□□ ■□□□□ □□□□□ 7 8 9 10 11 12 13 図:最短 13 手で解く手順
/* * uo5_max.c : 裏表パズル (5 * 5) の最長手数を求める * * Copyright (C) 2003 Makoto Hiroi */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define TRUE 1 #define FALSE 0 #define SIZE 25 #define LINE 10 #define B 1 #define W 0 #define MAX_STATE 663552 #define HASH_SIZE 19997 #define NIL (-1) /* * 盤面 * 0 1 2 3 4 * 5 6 7 8 9 * 10 11 12 13 14 * 15 16 17 18 19 * 20 21 22 23 24 */ const char line_table[LINE][5] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 0, 5, 10, 15, 20, 1, 6, 11, 16, 21, 2, 7, 12, 17, 22, 3, 8, 13, 18, 23, 4, 9, 14, 19, 24, }; int biton[SIZE] = { 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000, 0x80000, 0x100000, 0x200000, 0x400000, 0x800000, 0x1000000, }; /* リストの定義 */ typedef struct { int board; int next; } CELL; /* キューの定義 */ CELL state[MAX_STATE + 1]; /* 局面 */ char move[MAX_STATE]; /* 手数 */ /* ハッシュ表 */ int hash_table[HASH_SIZE]; /* ハッシュ表の初期化 */ void init_hash( void ) { int i; for( i = 0; i < HASH_SIZE; i++ ) hash_table[i] = NIL; } /* ハッシュ表の登録 */ int insert_hash( int i ) { int b = state[i].board; int h = b % HASH_SIZE; int n = hash_table[h]; while( n != NIL ){ if( state[n].board == b ) return FALSE; n = state[n].next; } state[i].next = hash_table[h]; hash_table[h] = i; return TRUE; } /* 裏返し */ int reverse_line( int board, int n ) { int p0 = line_table[n][0]; int p1 = line_table[n][1]; int p2 = line_table[n][2]; int p3 = line_table[n][3]; int p4 = line_table[n][4]; if( ((board >> p0) & 0x01) == ((board >> p4) & 0x01) ){ board ^= biton[p0]; board ^= biton[p4]; } if( ((board >> p1) & 0x01) == ((board >> p3) & 0x01) ){ board ^= biton[p1]; board ^= biton[p3]; } board ^= biton[p2]; return board; } /* 盤面を表示 */ void print_board( int board ) { int x, y, z; for( y = 0; y < 5; y++ ){ for( x = 0; x < 5; x++ ){ z = y * 5 + x; if( board & biton[z] ){ printf( "1 " ); } else { printf( "0 " ); } } printf("\n"); } printf("\n"); } /* 結果を出力 */ void print_answer( int n ) { int m = move[n - 1], c = 0; while( move[--n] == m ){ c++; print_board( state[n].board ); } printf("最長手数 %d 手、総数 %d 個\n", m, c ); } /* 幅優先探索による解法 */ void solve_b( void ) { int front = 0, rear = 1; /* 初期化 */ init_hash(); state[0].board = 0; move[0] = 0; insert_hash( 0 ); /* 探索 */ while( front < rear ){ int i, b = state[front].board; for( i = 0; i < LINE; i++ ){ state[rear].board = reverse_line( b, i ); if( insert_hash( rear ) ){ /* 登録 */ move[rear] = move[front] + 1; rear++; } } front++; } printf("局面の総数 %d\n", rear ); print_answer( rear ); } int main() { int s = clock(); solve_b(); printf("時間 %d\n", clock() - s ); return 0; }
/* * uo5.c : 裏表パズル (5 * 5) を幅優先探索(双方向)で解く * * Copyright (C) 2003 Makoto Hiroi */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define TRUE 1 #define FALSE 0 #define SIZE 25 #define LINE 10 #define B 1 #define W 0 #define MAX_STATE 663552 #define HASH_SIZE 19997 #define NIL (-1) #define FORWARD 0 #define BACKWARD 1 /* * 盤面 * 0 1 2 3 4 * 5 6 7 8 9 * 10 11 12 13 14 * 15 16 17 18 19 * 20 21 22 23 24 */ const char line_table[LINE][5] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 0, 5, 10, 15, 20, 1, 6, 11, 16, 21, 2, 7, 12, 17, 22, 3, 8, 13, 18, 23, 4, 9, 14, 19, 24, }; int biton[SIZE] = { 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000, 0x80000, 0x100000, 0x200000, 0x400000, 0x800000, 0x1000000, }; /* リストの定義 */ typedef struct { int board; int next; } CELL; /* キューの定義 */ CELL state[MAX_STATE + 1]; /* 局面 */ int prev_state[MAX_STATE]; /* 前の局面 */ char direction[MAX_STATE]; /* 探索の方向 */ /* ハッシュ表 */ int hash_table[HASH_SIZE]; /* ハッシュ表の初期化 */ void init_hash( void ) { int i; for( i = 0; i < HASH_SIZE; i++ ) hash_table[i] = NIL; } /* ハッシュ表の登録 */ int insert_hash( int i ) { int b = state[i].board; int h = b % HASH_SIZE; int n = hash_table[h]; while( n != NIL ){ if( state[n].board == b ) return n; n = state[n].next; } state[i].next = hash_table[h]; hash_table[h] = i; return NIL; } /* 裏返し */ int reverse_line( int board, int n ) { int p0 = line_table[n][0]; int p1 = line_table[n][1]; int p2 = line_table[n][2]; int p3 = line_table[n][3]; int p4 = line_table[n][4]; if( ((board >> p0) & 0x01) == ((board >> p4) & 0x01) ){ board ^= biton[p0]; board ^= biton[p4]; } if( ((board >> p1) & 0x01) == ((board >> p3) & 0x01) ){ board ^= biton[p1]; board ^= biton[p3]; } board ^= biton[p2]; return board; } /* 盤面を表示 */ void print_board( int board ) { int x, y, z; for( y = 0; y < 5; y++ ){ for( x = 0; x < 5; x++ ){ z = y * 5 + x; if( board & biton[z] ){ printf( "1 " ); } else { printf( "0 " ); } } printf("\n"); } printf("\n"); } /* 結果を出力 */ void print_answer_forward( int n ) { if( n > 1 ) print_answer_forward( prev_state[n] ); print_board( state[n].board ); } void print_answer_backward( int n ) { do { n = prev_state[n]; print_board( state[n].board ); } while( prev_state[n] != NIL ); } void print_answer( int i, int j ) { if( direction[i] == FORWARD ){ print_answer_forward( i ); print_answer_backward( j ); } else { print_answer_forward( j ); print_answer_backward( i ); } } /* 幅優先探索による解法 */ void solve_b( int init_board ) { int front = 0, rear = 2; /* 初期化 */ init_hash(); state[0].board = init_board; prev_state[0] = NIL; direction[0] = FORWARD; insert_hash( 0 ); state[1].board = 0; prev_state[1] = NIL; direction[1] = BACKWARD; insert_hash( 1 ); /* 探索 */ while( front < rear ){ int i, j, b = state[front].board; for( i = 0; i < LINE; i++ ){ state[rear].board = reverse_line( b, i ); prev_state[rear] = front; direction[rear] = direction[front]; /* 同一局面のチェック */ j = insert_hash( rear ); if( j != NIL ){ if( direction[j] != direction[rear] ){ /* 発見 */ print_answer( rear, j ); printf("状態数 %d 個\n", rear ); return; } } else { /* 登録 */ rear++; } } front++; } } /* 初期値 */ char init_state0[SIZE] = { W, W, B, W, W, W, W, B, W, W, B, B, B, W, W, W, W, W, W, W, W, W, W, W, W, }; char init_state1[SIZE] = { W, W, B, W, W, W, W, W, W, W, B, W, B, B, W, W, W, B, W, W, W, W, W, W, W, }; char init_state[SIZE] = { W, W, B, W, W, W, W, B, W, W, B, W, B, B, W, W, W, W, W, W, W, W, W, W, W, }; int main() { int i, b, s = clock(); /* 初期化 */ for( i = b = 0; i < SIZE; i++ ){ if( init_state[i] ) b |= biton[i]; } solve_b( b ); printf("時間 %d\n", clock() - s ); return 0; }