5 行 5 列盤の最長手数
今回は 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 を返します。
あとは単純な幅優先探索です。とくに難しいところはないと思います。詳細は プログラムリスト１ をお読みくださいませ。
●実行結果
それでは実行結果を示します。5 行 5 列盤の最長手数は 13 手、全部で 4608 通りのパターンがあります。実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で約 34 秒かかりました。けっこう時間がかかりますね。ハッシュ表をもう少し大きくするか、あるいは、最小完全ハッシュ関数を作成した方が速くなるかもしれません。興味のある方は挑戦してみてください。
最長手数の局面の例を図に示します。黒の個数が一番少ないパターンからいくつか選んでみました。
生成された局面は全部で 663,552 通り、これは偶奇性で計算した結果と一致します。実際に 13 手で解けるか、反復深化でプログラムを作ってみたのですが、時間がかかりすぎて途中で断念しました。手数が長いので、単純な反復深化ではダメですね。下限値枝刈り法も考えてみたのですが、効率のよい下限値の求め方がわかりません。何かよいアイデアがありましたら、ぜひ教えてくださいね。
そこで、オーソドックスに幅優先探索でプログラムを作ってみました。スタートとゴールの双方向から探索することで、M.Hiroi のオンボロマシン (Pentium 166 MHz) でも 1 秒かからずに解くことができます。興味のある方は プログラムリスト２ をお読みくださいませ。
最短手順の一例を図に示します。
●プログラムリスト１
/*
* 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;
}