今回は おしどりの遊び の変形版を考えてみましょう。このパズルは囲碁の白石と黒石を交互に並べ、それをペアで動かしながら黒石と白石とに分けるというものです。参考文献 [9] によると、白黒 n 個ずつの「おしどりの遊び」は n 回の移動で解けるそうです。変形版というと、たとえば 3 個 1 組で移動する、などいろいろ考えられますが、今回は石の種類を増やしてみましょう。
┌─┬─┬─┬─┬─┬─┬─┬─┐
│●│○│◎│●│○│◎│ │ │スタート
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│●│●│○│○│◎│◎│ │ │ゴール
└─┴─┴─┴─┴─┴─┴─┴─┘
図：石の種類が 3 種類の場合
ルールは同じで、石はペアで空いている場所に動かすことができます。このとき、ペアの順番を変えることはできません。石はそれぞれ 2 個ずつとし、石の種類を増やすと移動手順はどうなるか調べてみたいと思います。
最短手順を求めるので、幅優先探索を使いましょう。幅優先探索でパズルを解く場合、同一局面の検索処理が重要になります。もう何回も説明しているので、耳にタコができているかもしれませんね。今回はハッシュ法を使います。それから、「8 パズル」で説明したように、スタートとゴールの双方向から探索することにします。
簡単にハッシュ法の仕組みを説明します。ハッシュ法は、ハッシュ表と呼ばれるデータを格納する配列と、データを数値に変換するハッシュ関数を用意します。たとえば、ハッシュ表の大きさを n とすると、ハッシュ関数はデータを 0 から n - 1 までの整数値に変換するように作ります。この値をハッシュ値と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。
ハッシュ法では、不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成されることがあります。これをハッシュ値の衝突といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。
ひとつは空いている場所を探して、そこに入れる方法です。新しい場所を探すといっても、テーブルの先頭から線形探索するのではなく、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。これを空いている場所が見つかるまで繰り返します。
この方法だと、データの最大数はハッシュ表の大きさに制限されます。また、ハッシュ表の空きが少なくなると、探索効率も極端に低下してしまいます。このため、ハッシュ表の空きが少なくなったら、ハッシュ表のサイズを大きくし、ハッシュ表を作り直す作業を行うのがふつうです。これを リハッシュ (rehash) といいます。そのあと探索効率は良くなりますので、リハッシュにかけた時間のもとは十分にとれます。
もうひとつは、ハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納しておく工夫が必要になります。このときによく利用されるデータ構造が 連結リスト (Linked List) です。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。連結リストの代わりに二分探索木を使う方法もあります。
この方法では、ハッシュ値の衝突が頻繁に発生すると、データを格納するリストが長くなるため、探索時間が余分にかかってしまいます。効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。今回は、この連結リストを採用します。
まず最初に、連結リストを表すデータ構造とグローバル変数を定義しましょう。
リスト：データの定義
/* 連結リスト */
typedef struct _cell {
char board[MAX_SIZE];
int next;
} CELL;
/* キュー */
CELL state[MAX_STATE];
char space_postion[MAX_STATE];
int prev_state[MAX_STATE];
char direction[MAX_STATE];
/* ハッシュ表 */
#define HASH_SIZE 19997
int hash_table[HASH_SIZE];
構造体 CELL が連結リストのセル (CELL) です。連結リストは、このセルを連結したデータ構造です。一般に、連結リストはポインタを使用するのがふつうですが、今回は配列の添字で次のセルをポイントすることにします。このため、連結リストの終端は NIL (-1) で表します。
キューを表すデータ構造は簡単です。局面を表す state を CELL で定義するだけです。これで連結リストと同時にキューも表すことができます。ハッシュテーブルは NIL に初期化します。これで連結リストが登録されていない状態になります。HASH_SIZE は素数を選んだ方がよいとされています。石の種類が増えると局面数が多くなるので、HASH_SIZE は 19997 と大きく取っています。
次はハッシュ表にデータを登録する関数を作ります。まず、ハッシュ関数を定義します。プログラムは次のようになります。
リスト：ハッシュ関数
int hash_value( int n, int size )
{
int i, value = 0;
for( i = 0; i < size; i++ ){
value = value * 10 + state[n].board[i];
}
return value % HASH_SIZE;
}
とても単純なハッシュ関数です。size は石の種類を表します。3 種類の石であれば先頭から 3 つのデータを、8 種類の石であれば先頭から 8 つのデータを使ってハッシュ値を計算します。石の種類が多くなってもオーバーフローしないように、このような方法にしてみました。もっと上手な方法もあるでしょう。興味のある方はいろいろと試してみてください。
ハッシュ表への登録はとても簡単です。プログラムは次のようになります。
リスト：ハッシュ表への登録
int insert_hash( int i, int size, int board_size )
{
int h = hash_value( i, size );
int n = hash_table[h];
/* 連結リストの探索 */
while( n != NIL ){
if( memcmp( state[i].board, state[n].board, board_size ) == 0 ){
return n; /* 登録済み */
}
n = state[n].next;
}
/* 先頭に追加 */
state[i].next = hash_table[h];
hash_table[h] = i;
return NOT_FOUND;
}
最初に関数 hash_value でハッシュ値を計算し、ハッシュ表からデータを取り出します。あとは連結リストを単純に線形探索するだけです。同じ局面を見つけたら、その局面が格納されている番号を返します。見つからなければ、連結リストの先頭に追加して NOT_FOUND(-1) を返します。
残りのプログラムは、今まで説明した幅優先探索とほとんど同じです。詳細はソースファイルをご覧くださいませ。
それでは実行結果を示します。実行環境は Pentium 166 MHz です。8 種類まで調べると次のようになりました。
----- 3 種類の探索 ----- 1 2 3 1 2 3 0 0 1 0 0 1 2 3 2 3 1 1 2 0 0 3 2 3 1 1 2 2 3 3 0 0 状態数 15 個 時間 0 ----- 4 種類の探索 ----- 1 2 3 4 1 2 3 4 0 0 1 0 0 4 1 2 3 4 2 3 1 4 1 0 0 2 3 4 2 3 0 0 1 1 4 2 3 4 2 3 1 1 0 0 4 2 3 4 2 3 1 1 2 3 4 0 0 4 2 3 1 1 2 0 0 3 4 4 2 3 1 1 2 2 3 3 4 4 0 0 状態数 467 個 時間 0 ----- 5 種類の探索 ----- 1 2 3 4 5 1 2 3 4 5 0 0 1 0 0 4 5 1 2 3 4 5 2 3 1 1 2 4 5 0 0 3 4 5 2 3 1 1 2 4 5 3 4 0 0 5 2 3 1 1 2 0 0 3 4 4 5 5 2 3 1 1 2 2 3 3 4 4 5 5 0 0 状態数 199 個 時間 10 ----- 6 種類の探索 ----- 1 2 3 4 5 6 1 2 3 4 5 6 0 0 1 0 0 4 5 6 1 2 3 4 5 6 2 3 1 1 2 4 5 6 0 0 3 4 5 6 2 3 1 1 2 4 5 6 4 5 3 0 0 6 2 3 1 1 2 4 0 0 4 5 3 5 6 6 2 3 1 1 2 4 5 3 4 0 0 5 6 6 2 3 1 1 2 0 0 3 4 4 5 5 6 6 2 3 1 1 2 2 3 3 4 4 5 5 6 6 0 0 状態数 2632 個 時間 30 ----- 7 種類の探索 ----- 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 0 0 3 4 5 6 7 1 2 1 2 3 0 0 6 7 4 5 3 4 5 6 7 1 2 1 2 3 3 4 6 7 4 5 0 0 5 6 7 1 2 1 2 3 3 4 6 7 4 5 5 6 0 0 7 1 2 1 2 3 3 4 0 0 4 5 5 6 6 7 7 1 2 1 2 3 0 0 3 4 4 5 5 6 6 7 7 1 2 1 0 0 2 3 3 4 4 5 5 6 6 7 7 1 2 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 状態数 16935 個 時間 684 ----- 8 種類の探索 ----- 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 0 0 1 0 0 4 5 6 7 8 1 2 3 4 5 6 7 8 2 3 1 1 2 4 5 6 7 8 0 0 3 4 5 6 7 8 2 3 1 1 2 4 0 0 7 8 5 6 3 4 5 6 7 8 2 3 1 1 2 4 6 3 7 8 5 0 0 4 5 6 7 8 2 3 1 1 2 4 6 3 7 8 5 5 6 4 0 0 7 8 2 3 1 1 2 0 0 3 7 8 5 5 6 4 4 6 7 8 2 3 1 1 2 4 4 3 7 8 5 5 6 0 0 6 7 8 2 3 1 1 2 4 4 3 7 8 5 5 6 6 7 0 0 8 2 3 1 1 2 4 4 3 0 0 5 5 6 6 7 7 8 8 2 3 1 1 2 0 0 3 4 4 5 5 6 6 7 7 8 8 2 3 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 0 0 状態数 977337 個 時間 115787
| 種類 | ３ | ４ | ５ | ６ | ７ | ８ |
|---|---|---|---|---|---|---|
| 手数 | ３ | ７ | ５ | ７ | ８ | 11 |
時間の単位は msec です。石の種類が 8 種類になると、スタートとゴールの双方向から探索しても、生成する局面数が約 98 万個と多くなり、実行時間も約 2 分かかりました。
ところで、石の種類と最短手数の関係ですが、どうもよくわかりません。石の種類をこれ以上増やすとなると、メモリがもっともっと必要になります。石の種類が 6, 7, 8 と増えるにしたがい、生成する局面数も爆発的に増加しているので、幅優先探索だとメモリ不足になるのは避けられません。探索方法を反復深化に切り替えた方がよいと思われます。
石の種類を増やすという単純な変形版なので、もっと簡単に答えが求まると予想していたのですが、見通しが甘かったようです（苦笑）。興味のある方は反復深化にも挑戦してください。
/*
* oshidori.c : パズル「おしどり」の解法
*
* Copyright (C) 2000 by Makoto Hiroi
*
*/
/*
黒白黒白黒白空空 -> 黒黒黒白白白空空
動かせる駒はペア単位である
Ｎ種類２個ずつの石で解があるか？
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define NOT_FOUND (-1)
#define MAX_SIZE 20
#define FORWARD 0
#define BACKWARD 1
#define NIL (-1)
/* 適当 */
#define MAX_STATE 0x100000
/* 連結リスト */
typedef struct {
char board[MAX_SIZE];
int next;
} CELL;
/* キュー */
CELL state[MAX_STATE];
char space_postion[MAX_STATE];
int prev_state[MAX_STATE];
char direction[MAX_STATE];
/* ハッシュ表 */
#define HASH_SIZE 19997
int hash_table[HASH_SIZE];
/* ハッシュ関数 */
int hash_value( int n, int size )
{
int i, value = 0;
for( i = 0; i < size; i++ ){
value = value * 10 + state[n].board[i];
}
return value % HASH_SIZE;
}
/* ハッシュ表への登録 */
int insert_hash( int i, int size, int board_size )
{
int h = hash_value( i, size );
int n = hash_table[h];
/* 連結リストの探索 */
while( n != NIL ){
if( memcmp( state[i].board, state[n].board, board_size ) == 0 ){
return n; /* 登録済み */
}
n = state[n].next;
}
/* 先頭に追加 */
state[i].next = hash_table[h];
hash_table[h] = i;
return NOT_FOUND;
}
/* 結果を出力 */
void print_answer_forward( int n, int size )
{
int i;
if( n > 1 ) print_answer_forward( prev_state[n], size );
for( i = 0; i < size; i++ ){
printf("%d ", state[n].board[i] );
}
printf("\n");
}
void print_answer_backward( int n, int size )
{
do {
int i;
n = prev_state[n];
for( i = 0; i < size; i++ ){
printf("%d ", state[n].board[i] );
}
printf("\n");
} while( prev_state[n] != -1 );
}
void print_answer( int i, int j, int size )
{
if( direction[i] == FORWARD ){
print_answer_forward( i, size );
print_answer_backward( j, size );
} else {
print_answer_forward( j, size );
print_answer_backward( i, size );
}
}
/* 初期化 */
void init_data( int size, int board_size )
{
int i, j, k;
/* 初期値 */
for( k = 0, i = 0; i < 2; i++ ){
for( j = 1; j <= size; j++ ){
state[0].board[k++] = j;
}
}
space_postion[0] = k;
state[0].board[k++] = 0;
state[0].board[k] = 0;
prev_state[0] = -1;
direction[0] = FORWARD;
/* ゴール */
for( k = 0, j = 1; j <= size; j++ ){
state[1].board[k++] = j;
state[1].board[k++] = j;
}
space_postion[1] = k;
state[1].board[k++] = 0;
state[1].board[k] = 0;
prev_state[1] = -1;
direction[1] = BACKWARD;
/* ハッシュ表の初期化 */
for( i = 0; i < HASH_SIZE; i++ ){
hash_table[i] = NIL;
}
insert_hash( 0, size, board_size ); /* 登録 */
insert_hash( 1, size, board_size );
}
/* 探索関数 */
void search( int size )
{
int r = 0, w = 2;
int board_size = size * 2 + 2;
/* 初期化 */
init_data( size, board_size );
printf("----- %d 種類の探索 ----- \n", size );
for( ; r < w; r++ ){
int k = space_postion[r];
int i, j;
for( i = 0; i < board_size - 1; i++ ){
if( state[r].board[i] && state[r].board[i + 1] ){
/* 盤面をコピーする */
memcpy( state[w].board, state[r].board, board_size );
state[w].board[k] = state[r].board[i];
state[w].board[k + 1] = state[r].board[i + 1];
state[w].board[i] = 0;
state[w].board[i + 1] = 0;
space_postion[w] = i;
direction[w] = direction[r];
prev_state[w] = r;
/* 検索する */
j = insert_hash( w, size, board_size );
if( j >= 0 ){
if( direction[j] != direction[w] ){
/* 解けた */
print_answer( j, w, board_size );
printf("状態数 %d 個\n", w );
return;
}
} else {
w++; /* 登録 */
if( w >= MAX_STATE ){
fprintf( stderr, "状態数オーバー\n" ); exit( 1 );
}
}
}
}
}
}
int main()
{
int i, start, end;
for( i = 3; i <= 8; i++ ){
start = clock();
search( i );
end = clock();
printf("時間 %d\n", end - start );
}
return 0;
}