●パズル「おしどりの遊び」
それでは実際にパズルを解いてみましょう。まずはウオーミングアップとして、石を並べ替える「おしどりの遊び」という古典的なパズルを取り上げます。このパズルは囲碁の白石と黒石を交互に並べ、それをペアで動かしながら黒石と白石とに分けるというもので、文献 [4] によると江戸時代からある遊びだそうです。
石はペアで空いている場所に動かすことができます。このときペアの順番を変えることはできません。たとえば、先頭にある黒白を動かすときに、白黒というように石の順番を逆にすることは許されません。この条件で並べ替えるまでの最短手順を求めます。
盤面は配列で表すことにします。黒石、白石、空き場所をそれぞれマクロで B, W, S と定義します。
/* 種別の設定 */ #define S 0 #define B 1 #define W 2
そうすると移動できる石は、連続した 2 つの場所の値が真であること、で判定することができます。具体的には、次のようなプログラムで移動できるすべての石をチェックすることができます。
int i;
for( i = 0; i < SIZE - 1; i++ ){
if( state[i] && state[i + 1] ){
/* 駒を移動できる */
}
}
盤面の状態（局面）を表す配列を state とし、SIZE は配列の大きさを表すマクロです。石はペアで動かすので、変数 i の範囲は 0 から 6 までということに注意してください。7 までにすると配列の範囲をオーバーしてしまいます。
今度は移動手順の管理を考えましょう。最短手順を求めるだけならば、すべての手順を記憶しておく必要はありません。n 手目の移動で作られた局面が、n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する移動手順があるはずです。したがって、この n 手の手順を記憶しておく必要はないのです。そこで、キューには局面だけを格納し、手順は番号で管理することにします。
| 図 9 : 手順の管理 | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
図 9 を使って具体的に説明しましょう。局面は配列 state に格納します。このときの添字が、その局面の番号になります。そして、その 1 手前の局面の番号を配列 prev_state に格納します。まず最初の配置を state[0] にセットします。prev_state[0] には終端を表すため -1 をセットします。次に、石を移動して 1 手目の局面を生成します。移動できる石のペアは 5 種類あるので、新しく生成される局面は 5 つとなります。それぞれ、state[1] から state[5] にセットし、prev_state には元になった局面 state[0] の番号 0 をセットします。
次に、2 手目の局面を生成します。state[1] で石を動かして生成される局面は 5 つありますが、そのうち 3 つはいままで出現した局面と同じになるので、新しい局面は 2 つとなります。これを state[6] と state[7] にセットします。このときの prev_state には、元になった局面 state[1] の番号 1 がセットされます。あとは同様に、キューから局面を取り出して石を動かし、新しい局面であればキューに登録することを繰り返します。最終状態と同じ局面になったときは、prev_state をたどることで手順を再現することができます。
●おしどりの遊びを解く
それではプログラムを作ります。最初に、キューの大きさを決めるため石の置き方が何通りあるか数えましょう。これは空き場所の配置から考えた方が簡単です。2 つの空き場所は離ればなれにならないのですから、7 通りの配置が考えられます。次に、残り 6 ヵ所に 3 個の黒石を置くことを考えます。これは 6 個の中から 3 個を選ぶ組み合わせと考えられるので、組み合わせの公式から (6 * 5 * 4) / (1 * 2 * 3) = 20 通りあります。黒石の置き方が決まれば、白石は残りの 3 ヵ所に置くだけです。したがって、全体では 20 * 7 = 140 通りになるので、キューの大きさは 140 に設定します。キューの構成は次のようになります。
/* キュー */ #define MAX_STATE 140 char state[MAX_STATE + 1][SIZE]; /* +1 は ワーク領域 */ char space_position[MAX_STATE]; short prev_state[MAX_STATE];
配列 state は石を動かすときにワーク領域としても使うので、大きさをひとつ余分に設定します。石を動かすには空き場所の位置を求めなければいけません。配列 state を探索してもいいのですが、あらかじめ配列 space_position に空き場所の位置をセットしておけば、簡単に求めることができます。石の移動は次のようになります。
リスト : 石の移動
void move_stone( int front, int rear, int dest )
{
int j = space_position[front];
memcpy( state[rear], state[front], SIZE );
state[rear][j] = state[front][dest];
state[rear][j + 1] = state[front][dest + 1];
state[rear][dest] = S;
state[rear][dest + 1] = S;
space_position[rear] = dest;
prev_state[rear] = front;
}
引数 dest は移動する石の位置を表します。space_position から空き場所の位置を求め変数 j にセットします。dest と dest + 1 にある石を、j と j + 1 へ移動し、dest と dest + 1 には空き場所を表す S をセットすれば、石を移動することができます。石を動かすときは、state[front] を state[rear] にコピーしてから行います。これは経路の場合と同じですね。最後に、空き場所の位置を space_position に、front を prev_state に値を書き込みます。
探索を行う関数 search は次のようになります。
リスト : おしどりの遊び
/* 初期状態 */
const char initial_state[SIZE] = {
B, W, B, W, B, W, S, S
};
/* ゴール */
const char final_state[SIZE] = {
B, B, B, W, W, W, S, S
};
/* 探索関数 */
void search( void )
{
int front = 0, rear = 1;
memcpy( state[0], initial_state, SIZE );
prev_state[0] = -1;
space_position[0] = 6;
while( front < rear ){
int i;
for( i = 0; i < SIZE - 1; i++ ){
if( state[front][i] && state[front][i + 1] ){
move_stone( rear, front, i );
if( !memcmp( state[rear], final_state, SIZE ) ){
print_answer( rear );
return;
} else if( !check_same_state( rear ) ){
rear++;
}
}
}
front++;
}
}
プログラムの骨格は経路の探索と同じです。move_stone で石を動かしたら、ゴールに到達したかチェックします。state[rear] が配列 final_state と同じであれば、解を見つけることができました。print_answer で最短手順を表示します。そうでなければ、同一の局面がないか check_same_state でチェックします。新しい局面であれば rear の値をインクリメントして、新しい局面をキューに追加します。move_stone で state[rear] にデータをコピーしていますが、rear の値を更新しない限りキューにデータは追加されません。
同一局面のチェックを行う関数 check_same_state は簡単です。
リスト : 同じ状態をチェックする
int check_same_state( int n )
{
int i;
for( i = 0; i < n; i++ ){
if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
}
return FALSE;
}
配列 state を先頭から順番にチェックしていきます。これを「線形探索」といいます。このプログラムは次のように書き換えると、ループ中での変数 i の範囲チェックを省略することができます。
リスト : 番人を使う方法
int check_same_state( int n )
{
int i = 0;
while( memcmp( state[i], state[n], SIZE ) ) i++;
return (i != n) ? TRUE : FALSE;
}
検索するデータの最後にはキーデータ state[n] があるので、検索は必ず成功します。発見したデータの位置が n と等しければ、キーデータを見つけたことがわかるので、検索は失敗となります。そうでなければ検索は成功です。キーデータ自身で、検索ポイントがデータの範囲を飛び出さないように監視するわけです。このような方法を「番人」とか「番兵」と呼びます。まあ、最近のように高速 CPU を使った環境では、速度の差はほとんどありませんが、番人を使った方が簡単にプログラムできるアルゴリズムもあるので、覚えておいて損はありません。
最後に手順を表示する print_answer を作ります。
リスト : 手順の表示
void print_answer( int n )
{
int i;
if( n != 0 ) print_answer( prev_state[n] );
for( i = 0; i < SIZE; i++ ){
switch( state[n][i] ){
case S: printf("空 "); break;
case B: printf("黒 "); break;
case W: printf("白 "); break;
}
}
printf("\n");
}
prev_state を順番にたどって出力すると、手順は逆順に表示されてしまいます。そこで、再帰呼び出しを使って最初の状態に戻り、そこから局面を順番に出力させます。
実行結果は次のようになります。
4 手で解くことができました。このとき、生成した局面の総数は 64 個でした。ちなみに、黒と白の分け方を逆にした「白白白黒黒黒空空」も、4 手で解くことができます。プログラムは簡単に改造できますが、その前に自分で解いてみるのも面白いでしょう。
●６パズル
次は 15 パズルでお馴染みの、スライディングブロックと呼ばれるパズルを解いてみましょう。文献 [4] によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。
図 10 : 15 パズル
15 パズルは図 10 に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を飛び越したり持ち上げたりすることはできません。
15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を六角形に変形し、1 から 6 までの数字を並べる「6 パズル」を考えることにします。
図 11 : 6 パズル
図 11 は 6 パズルをグラフで表したものです。0 が空き場所を表します。ここには 3, 4, 6 の駒を動かすことができます。6 パズルは単純に考えると駒の配置は 7! = 5040 通りとなります。これならば簡単に解くことができそうです。
6 パズルの盤面は配列を使って表します。位置と配列の関係は図 12 を見てください。
隣接リストとキューの定義は、次のようになります。
リスト : 隣接リストとキューの定義
/* 隣接リスト */
#define SIZE 7
const char adjacent[SIZE][7] = {
1, 2, 3, -1, -1, -1, -1, /* 0 */
0, 3, 4, -1, -1, -1, -1, /* 1 */
0, 3, 5, -1, -1, -1, -1, /* 2 */
0, 1, 2, 4, 5, 6, -1, /* 3 */
1, 3, 6, -1, -1, -1, -1, /* 4 */
2, 3, 6, -1, -1, -1, -1, /* 5 */
3, 4, 5, -1, -1, -1, -1 /* 6 */
};
/* キュー */
#define MAX_STATE 5040
char state[MAX_STATE + 1][SIZE]; /* +1 はワーク領域 */
char space_position[MAX_STATE];
short prev_state[MAX_STATE];
手順の管理は「おしどりの遊び」と同じです。駒の移動は、動かすことができる駒を探すよりも、空き場所を基準に考えた方が簡単です。その局面での空き場所の位置を配列 space_position に記憶しておきます。新しい局面を作るときは、空き場所に隣接している駒を隣接リストから求め、それを空き場所に移動させればいいわけです。
それではプログラムを作ります。
リスト : 6 パズルの解法(1)
/* 初期状態 */
char init_state[SIZE] = {
1, 5, 2, 6, 3, 4, 0
};
/* 最終状態 */
char final_state[SIZE] = {
1, 2, 3, 4, 5, 6, 0
};
/* 探索 */
void search( void )
{
int front = 0, rear = 1;
memcpy( state[0], init_state, SIZE );
space_position[0] = 6;
prev_state[0] = -1;
while( front < rear ){
int n, i, s = space_position[front];
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
memcpy( state[rear], state[front], SIZE );
state[rear][s] = state[rear][n];
state[rear][n] = 0;
space_position[rear] = n;
prev_state[rear] = front;
if( !memcmp( state[rear], final_state, SIZE ) ){
print_answer( rear );
return;
} else if( !check_same_state( rear ) ){
rear++;
}
}
front++;
}
}
プログラムの骨格は前の 2 つと同じなので、詳しく説明しなくてもいいでしょう。同一局面のチェックを行う check_same_state は単純な線形探索です。手順を出力する print_answer は、配列の内容をそのまま出力するだけです。六角形に出力するなど、工夫してみてください。
実際に実行すると (ソースファイル hex1.c)、11 手で解くことができました。このときの実行時間は約 3.2 秒 (Pentium 166 MHz) もかかっています。簡単に解けると思っていたのですが、けっこう時間がかかりますね。
時間がかかる理由のひとつは、同一局面のチェックを行う check_same_state にあります。線形探索は配列の先頭から順番にデータを比較していくため、その実行時間はデータ数に比例します。今回生成された局面は 2818 個だったのですが、ひとつの局面から複数の局面を生成し、それを検索するのですから、データの比較回数は相当の数になるでしょう。実際に数えてみると 7,598,140 回にもなります。これでは時間がかかるのも当然ですね。
●６パズルの高速化
このようなときの常套手段が、線形探索に代えて高速な検索アルゴリズムを使うことです。ハッシュ法や二分探索木など、優れたアルゴリズムを使うことで、実行時間を大幅に短縮することができます。ですが、いきなり使ってみましょう、といわれても困ってしまいますね。そこで、ほかの方法を採用することにします。幅優先探索の場合、出発点から探索するだけではなく、ゴール地点からも探索を行うことで、探索する局面数を減らすことができるのです。
その理由を説明するために、簡単なシミュレーションをしてみましょう。たとえば、1 手進むたびに 3 つの局面が生成され、5 手で解けると仮定します。すると、n 手目で生成される局面は 3 の n 乗個になるので、初期状態から単純に探索すると、生成される局面の総数は、3 + 9 + 27 + 81 + 243 = 363 個となります。
これに対し、初期状態と終了状態から同時に探索を始めた場合、お互い 3 手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。この場合、生成される局面の総数は 3 手目までの局面数を 2 倍した 78 個となります。
生成される局面数はぐっと減りますね。局面数が少なくなると、同一局面の検索処理に有利なだけではなく、キューからデータを取り出して新しい局面を作るという根本的な処理のループ回数を減らすことになるので、処理速度は大幅に向上するのです。
それではプログラムを改造しましょう。単純に考えると、2 つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な改造が必要になります。ここは、探索方向を示すフラグを用意することで、ひとつのキューだけで処理することにしましょう。メモリを余分に使うことになりますが、プログラムの改造は最小限で済みます。
/* 探索方向を格納する */ #define FORWARD 0 #define BACKWARD 1 char direction[MAX_STATE];
探索方向は配列 direction に格納します。初期状態からの探索は FORWARD を、終了状態からの探索は BACKWARD をセットします。探索プログラムは次のようになります
リスト : 6 パズルの解法(2)
void search( void )
{
int front = 0, rear = 2;
/* キューの初期化 */
memcpy( state[0], init_state, SIZE );
space_position[0] = 6;
prev_state[0] = -1;
direction[0] = FORWARD;
memcpy( state[1], final_state, SIZE );
space_position[1] = 6;
prev_state[1] = -1;
direction[1] = BACKWARD;
while( front < rear ){
int s = space_position[front];
int i, j, n;
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* ・・・駒の移動・・・（省略） */
direction[rear] = direction[front];
if( (j = check_same_state( rear )) >= 0 ){
if( direction[j] != direction[rear] ){
print_answer( j, rear );
return;
}
} else {
rear++;
}
}
front++;
}
}
キューの初期化では、最初に初期状態を、次に終了状態をセットします。2 つのデータをセットしたのですから、変数 rear の値は 2 に初期化することに注意してください。最初に、初期状態から 1 手目の局面が生成され、次に最終状態から 1 手目の局面が生成されます。あとは、交互に探索が行われます。
駒の移動は同じなので省略しますが、direction の値をコピーする処理を追加していることに注意してください。direction の値を比較するため、check_same_state は見つけた局面の番号を返すように改造します。見つからない場合は -1 を返すことにします。同じ局面を見つけたとき、direction を比較して探索方向が異なっていれば、2 方向の探索で同一局面に到達したことがわかります。見つけた最短手順を print_answer で出力します。同じ探索方向であれば、キューへの追加は行いません。
手順の表示は探索方向によって処理が異なるので、print_answer で振り分けます。
リスト : 結果を出力
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 );
}
}
初期状態からの手順を表示する関数が print_answer_forward です。この処理は、今までの print_answer と同じです。終了状態までの手順を表示するのが print_answer_backward です。これは prev_state を順番にたどって表示するだけなので、繰り返しで簡単にプログラムできます。これでプログラムの改造は終わりです。
プログラム (ソースファイル hex2.c) を実行してみると、生成された局面数は 342 個で、実行時間は約 60 [msec] でした。50 倍以上の高速化ですね。予想していた以上の効果に、筆者もたいへん驚きました。
●６パズルの最長手順は？
さて、図 11 の配置は 11 手で解くことができましたが、5040 通りの配置の中では、これよりも短い手数で解けるものもあるでしょうし、もっと長い手数がかかるものもあるでしょう。そこで、今度は単純に解くのではなく、パズルが完成するまでにいちばん手数がかかる配置を求めることにします。つまり、最短手順で解いてもいちばん長い手順となる、いちばん難しい配置を求めるわけです。
この場合、5040 通りの配置からその最短手順を求めていき、そのなかから最長の手順となる配置を求めることもできますが、それでは時間がとてもかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。ただし、初期状態からの探索しかできないので、同一局面のチェックが線形探索のままでは時間がかかる、ということは覚悟してください。
このプログラムの目的は、いちばん難しい手順となる配置を求めることなので、手順を表示することは行いません。このため、ひとつ前の局面番号を格納する配列 prev_state は定義しません。その代わり、その局面までの手数を格納する配列 move を用意します。ひとつ前の局面の手数を move から求め、それに 1 を足せば現在の局面の手数となります。
それではプログラムを作ります。
リスト : 最長手数を求める
void search( void )
{
int front = 0, rear = 1;
memcpy( state[0], init_state, SIZE );
space_position[0] = 6;
move[0] = 0;
while( front < rear ){
int n, i, s = space_position[front];
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
memcpy( state[rear], state[front], SIZE );
state[rear][s] = state[rear][n];
state[rear][n] = 0;
space_position[rear] = n;
move[rear] = move[front] + 1;
if( !check_same_state( rear ) ){
rear++;
}
}
front++;
}
print_answer( rear );
}
最終状態をチェックする処理がないことに注意してください。生成できる局面がなくなるまで、つまりキューにデータがなくなるまで処理を繰り返します。最後に print_answer で最長手数とその配置を出力します。この関数は簡単なので説明は省略します。これでプログラム（ソースファイル hex3.c）は完成です。
実際に実行すると、最長手数は 15 手で、その配置は全部で 24 通りありました。そのうちのひとつを図 13 に示します。
図 13 : いちばん難しい配置の例
ちなみに、生成した全局面は 5040 個ありました。しがたって、6 パズルでは数字をランダムに配置しても、必ず完成形に到達できることがわかります。実行時間ですが、予想したように約 16 秒と時間がかかっています。生成した局面が 5040 個もあるのですから、データの比較回数は相当の数になります。実際に数えてみると 43,454,059 回にもなります。実行時間の短縮には、高速な検索アルゴリズムを使う必要があります。
●次回は？
次回はパズルから離れて、高速なデータ検索方法の中から二分探索木を中心に説明します。木構造の基本から多分木まで、ねっとりと説明する予定です。6 パズルがどこまで速くなるか、お楽しみに。