蛙跳びゲームは黒石と白石を使って遊ぶ、いわゆる飛び石ゲームと呼ばれる種類のパズルです。飛び石ゲームでは、江戸時代からあるおしどりの遊びというパズルが有名です。このパズルは囲碁の白石と黒石を交互に並べ、それをペアで動かしながら黒石と白石とに分けるというものです。
┌─┬─┬─┬─┬─┬─┬─┬─┐
│●│○│●│○│●│○│ │ │ スタート
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│●│●│●│○│○│○│ │ │ ゴール
└─┴─┴─┴─┴─┴─┴─┴─┘
図：おしどりの遊び
石はペアで空いている場所に動かすことができます。このとき、ペアの順番を変えることはできません。たとえば、先頭にある黒白を動かすときに、白黒というように石の順番を逆にすることは許されません。この条件で並べ替えるまでの最短手順 (追記１) を求めます。このパズルは簡単なので、プログラムを作るよりも自分で解いてみるといいでしょう。
蛙飛びゲームは簡単そうに見えて、おしどりの遊びよりも難しいパズルです。
┌─┬─┬─┬─┬─┬─┬─┐
│●│●│●│ │○│○│○│ スタート
└─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┐
│○│○│○│ │●│●│●│ ゴール
└─┴─┴─┴─┴─┴─┴─┘
図：蛙跳びゲーム
上図のように、蛙跳びゲームは黒石と白石を入れ替えることができれば成功です。石を動かす規則は次のとおりです。
石の跳び越しは次の図を参考にしてください。
┌───┐ ┌───┐
↓ │ │ ↓
┬─┬─┬─┬─┬ ┬─┬─┬─┬─┬
│ │●│○│ │ │ │●│○│ │
┴─┴─┴─┴─┴ ┴─┴─┴─┴─┴
白石の移動 黒石の移動
図：石の跳び越し
簡単そうに思えますが、実際にやってみると難しいのです。まず最初に、自分でパズルを解くことに挑戦してください。このパズルの難しさが実感できるでしょう。
いつものように、最短手順を求めるプログラムを作ります。コンピュータにとって、蛙跳びゲームは簡単なパズルです。単純な幅優先探索で最短手順を求めることができます。使用するプログラミング言語は Perl です。
今回は Perl らしく、文字列の置換を使ってプログラムを作りましょう。盤の状態は "WWW_BBB" のように文字列で表します。文字 B, W が黒石と白石で、_ が空き場所を表します。すると、石の移動は次のような文字列の置換で表すことができます。
| 石の移動 | 文字列の置換 |
|---|---|
| 黒石の跳び越し | s/(.*)BW_(.*)/$1_WB$2/ |
| 白石の跳び越し | s/(.*)_BW(.*)/$1WB_$2/ |
| 黒石の移動 | s/(.*)B_(.*)/$1_B$2/ |
| 白石の移動 | s/(.*)_W(.*)/$1W_$2/ |
石の移動パターンは、この 4 通りしかありません。文字列の置換が行われれば、石を移動できたことになります。あとは幅優先探索で必要となるグローバル変数を定義します。
リスト：グローバル変数の定義
# スタートとゴール
$start ="BBB_WWW";
$goal ="WWW_BBB";
@state = (); # 状態を格納
@prev_state = (); # 前の状態を指す
%state_check = (); # 状態チェックのハッシュ
# 置換用
@search = ("BW_", "_BW", "B_", "_W");
@replace = ("_WB", "WB_", "_B", "W_");
置換用のデータは次のように使います。
s/(.*)$search[$i](.*)/$1$replace[$i]$2/
これで簡単に 4 通りの移動パターンをチェックすることができます。実をいうと、文字列の置換に変数が使えることをうっかりしていまして（苦笑）、最初に作ったプログラムは、移動パターンごとに関数を作って、それを呼び出してチェックしていました。
先日、deepgreen さんが作成された Prolog のプログラムを見ると、石の移動条件が Prolog らしくすっきりと記述されていました。Perl でも何とかならないものか、とプログラムを見直していると、そういえば置換でも変数が使えるにょ！、と思い出しました。ご参考までに、最初のプログラムは あとがき で紹介します。
幅優先探索のプログラムは次のようになります。
リスト：幅優先探索
sub search_move {
my $w = 1; # ライトカウンタ
my $r = 0; # リードカウンタ
# 初期化
$state[0] = $start;
$prev_state[0] = -1;
for( ; $r < $w; $r++ ){
my $i;
for( $i = 0; $i < 4; $i++ ){
my $new = $state[$r];
if( $new =~ s/(.*)$search[$i](.*)/$1$replace[$i]$2/ ){
# 移動可能
$state[$w] = $new;
$prev_state[$w] = $r;
if( !$state_check{$new} ){
if( $goal eq $new ){
&print_answer( $w );
print "状態数 $w\n";
return;
}
$state_check{$new} = 1;
$w++;
}
}
}
}
}
ごく普通の幅優先探索なので、難しいところはないと思います。最後に、求めた最短手順を出力する print_answer を作ります。
リスト：最短手順の出力
sub print_answer {
my $i = shift;
if( $prev_state[$i] != -1 ){
&print_answer( $prev_state[$i] );
}
print "$state[$i]\n";
}
再帰呼び出しで先頭まで戻り、最初から手順を表示します。これでプログラムは完成です。
それでは実行結果を示します。移動する石を太字で表しています。
B B B _ W W W B B _ B W W W B B W B _ W W B B W B W _ W B B W _ W B W B _ W B W B W _ B W B W B W W B _ B W B W W B W B _ B W W B W B W B _ W B W B W _ B W B W _ W B B W _ W B W B B W W _ B W B B W W W B _ B B W W W _ B B B
15 手で解くことができました。この手順は黒石から動かしていますが、白石から動かしても解くことができます。
ところで、今回はアルゴリズムに幅優先探索を使いましたが、黒石と白石は後戻りできないことから、バックトラックでも簡単に最短手順を求めることができます。興味のある方は、実際に試してみるといいでしょう。
最初に作ったプログラムは、4 通りの移動パターンに対応する関数を作り、それを順番に呼び出します。プログラムの概要は次のようになります。
リスト：最初のプログラムの概要
# 移動のチェック
sub check_1 {
my $new = shift;
if( $new =~ s/(.*)BW_(.*)/$1_WB$2/ ){
return $new;
}
0;
}
# 呼び出し部分
foreach $func (\&check_1, \&check_2, \&check_3, \&check_4) {
my $new = &$func( $state[$r] );
if( $new ){
・・・ 処理 ・・・
}
}
関数へのリファレンスを使っているので Perl 4 では動作しません。このほかにも、関数をわざわざ定義せずに無名の関数を使うとか、いろいろな方法があると思います。面白いプログラムができたら教えてくださいね。
「おしどりの遊び」の解答です。
┌─┬─┬─┬─┬─┬─┬─┬─┐
│●│○│●│○│●│○│ │ │ スタート
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│●│●│●│○│○│○│ │ │ ゴール
└─┴─┴─┴─┴─┴─┴─┴─┘
図：おしどりの遊び
「おしどりの遊び」は、上図のように白石と黒石を交互に並べ、それをペアで動かしながら黒石と白石とに分けるというものです。正解は次のようになります。
[0] ● ○ ● ○ ● ○ ・ ・
^^^^^
[1] ● ○ ● ・ ・ ○ ○ ●
^^^^^
[2] ● ○ ● ○ ○ ・ ・ ●
^^^^^
[3] ● ・ ・ ○ ○ ○ ● ●
^^^^^
[4] ● ● ● ○ ○ ○ ・ ・
図：正解手順
4 回で解くことができました。ちなみに、黒と白の分け方を逆にした「白白白黒黒黒空空」も、4 回で解くことができます。ところで、空き場所や石の配置を限定しなければ 3 回で解くことができます。
[0] ● ○ ● ○ ● ○ ・ ・ ・ ・
^^^^^
[1] ● ○ ● ・ ・ ○ ○ ● ・ ・
^^^^^
[2] ・ ・ ● ● ○ ○ ○ ● ・ ・
^^^^^
[3] ・ ・ ・ ・ ○ ○ ○ ● ● ●
図：別条件での正解手順
参考文献 [9] [10] は、この条件で解いています。この本によると、黒石と白石を n 個ずつにした場合、最小回数は n 回で解くことができるそうです。
石の移動は、違う色の石を跳び越すか、隣の空いている場所へひとつ移動するという 2 通りの方法があります。まず、跳び越す回数を求めましょう。ひとつの黒石に注目してください。この石は白石を跳び越すか、または白石に跳び越されることになります。どちらにしても、この黒石には白石の数だけ跳び越しが行われます。
したがって、n 個ずつの石がある場合、ひとつの黒石が右側へ移動する間に跳び越しは n 回行われることになります。黒石は n 個ありますから、跳び越す回数は全部で n 2 回となります。
次は、石をひとつ移動する回数を求めます。石が n 個ずつある場合、各石の移動距離は n + 1 なので、合計では 2n(n + 1) になります。この値から跳び越しによる移動距離を引けば、石をひとつ移動する回数を求めることができます。
ひとつ移動する回数：２ｎ（ｎ＋１）−２ｎ2 ＝２ｎ
したがって、石の移動回数は次のようになります。
移動回数：ｎ2＋２ｎ
石が 3 個ずつの場合は 3 * 3 + 2 * 3 = 15 回、4 個ずつの場合は 4 * 4 + 2 * 4 = 24 回、とあっていますね。簡単に説明しましたが、詳しいことは 参考文献 [9] を参考にしてください。
ところで、このドキュメントでは「最短手数」と書きましたが、これより長い手順はありません。つまり、蛙飛びゲームは、この回数でないと解けないのです。
次は、蛙跳びゲームを平面に拡張して見ましょう。それでは問題です。
┌─┐ ┌─┬─┐ ┌─┬─┬─┐
│●│ │●│●│ │●│●│●│
┌─┼─┤ ├─┼─┤ ├─┼─┼─┤
│●│●│ │●│●│ │●│●│●│
┌─┼─┼─┼─┬─┐ ├─┼─┼─┐ ├─┼─┼─┼─┬─┐
│●│●│ │○│○│ │●│ │○│ │●│●│ │○│○│
└─┴─┼─┼─┼─┘ └─┼─┼─┤ └─┴─┼─┼─┼─┤
│○│○│ │○│○│ │○│○│○│
├─┼─┘ ├─┼─┤ ├─┼─┼─┤
│○│ │○│○│ │○│○│○│
└─┘ └─┴─┘ └─┴─┴─┘
（Ａ） （Ｂ） （Ｃ）
問題：平面上の蛙跳びゲーム
黒石と白石を入れ替えるのがパズルの目的です。石を動かす規則は次のとおりです。
この規則で黒石と白石を入れ替える最短手順を求めてください。
問題 (A) と (B) は Common Lisp 入門 の 蛙跳びゲームを解く で取り上げました。そこで、今回は問題 (C) の解法プログラムをＣ言語で作成してみましょう。
今回は幅優先探索でプログラムを作ります。最初にキューの大きさを決めるため、局面の総数を求めます。マスは全部で 17 か所あるので、空き場所の配置は 17 通りあります。石の配置は、残り 16 か所に 8 個の黒石を配置するので 16Ｃ8 = 12870 通りあります。局面の総数は 17 * 12870 = 218790 通りになるので、キューの大きさは 218790 に設定します。同一局面のチェックはハッシュ法を使いましょう。
┌─┬─┬─┐
│０│１│２│
├─┼─┼─┤
│３│４│５│
├─┼─┼─┼─┬─┐
│６│７│８│９│10│
└─┴─┼─┼─┼─┤
│11│12│13│
├─┼─┼─┤
│14│15│16│
└─┴─┴─┘
図：盤面
最初にデータ構造を定義します。盤面は 1 次元配列で表して、黒石を B (1), 白石を W (2), 空き場所を S (0) で表します。盤面と配列の対応は左図を見てください。
石の移動方向を番号の大小関係でチェックするため、番号は左上から右下へ順番につけています。こうすると、黒石の移動は小さな番号から大きな番号、逆に白石の移動は大きな番号から小さな番号になります。
石の移動は「隣接リスト」と「跳び先表」を用意すると簡単にプログラムできます。次のリストを見てください。
リスト：隣接リスト
char neighbor[SIZE][5] = {
1, 3, -1, -1, -1, /* 0 */
0, 2, 4, -1, -1, /* 1 */
1, 5, -1, -1, -1, /* 2 */
0, 4, 6, -1, -1, /* 3 */
1, 3, 5, 7, -1, /* 4 */
2, 4, 8, -1, -1, /* 5 */
3, 7, -1, -1, -1, /* 6 */
4, 6, 8, -1, -1, /* 7 */
5, 7, 9, 11, -1, /* 8 */
8, 10, 12, -1, -1, /* 9 */
9, 13, -1, -1, -1, /* 10 */
8, 12, 14, -1, -1, /* 11 */
9, 11, 13, 15, -1, /* 12 */
10, 12, 16, -1, -1, /* 13 */
11, 15, -1, -1, -1, /* 14 */
12, 14, 16, -1, -1, /* 15 */
13, 15, -1, -1, -1, /* 16 */
};
リスト：跳び先表
char jump[SIZE][9] = {
1, 2, 3, 6, -1, -1, -1, -1, -1, /* 0 */
4, 7, -1, -1, -1, -1, -1, -1, -1, /* 1 */
1, 0, 5, 8, -1, -1, -1, -1, -1, /* 2 */
4, 5, -1, -1, -1, -1, -1, -1, -1, /* 3 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, /* 4 */
4, 3, 8, 11, -1, -1, -1, -1, -1, /* 5 */
3, 0, 7, 8, -1, -1, -1, -1, -1, /* 6 */
4, 1, 8, 9, -1, -1, -1, -1, -1, /* 7 */
5, 2, 7, 6, 9, 10, 11, 14, -1, /* 8 */
8, 7, 12, 15, -1, -1, -1, -1, -1, /* 9 */
9, 8, 13, 16, -1, -1, -1, -1, -1, /* 10 */
8, 5, 12, 13, -1, -1, -1, -1, -1, /* 11 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, /* 12 */
12, 11, -1, -1, -1, -1, -1, -1, -1, /* 13 */
11, 8, 15, 16, -1, -1, -1, -1, -1, /* 14 */
12, 9, -1, -1, -1, -1, -1, -1, -1, /* 15 */
13, 10, 15, 14, -1, -1, -1, -1, -1, /* 16 */
};
跳び先表 jump は空き場所を基準にして、跳び越される石の位置と跳ぶ石の位置を交互に並べたものです。たとえば、空き場所が 0 番の場合、2 番の石が 1 番の石を跳び越して 0 番へ移動することができます。このとき、石の種類をチェックすることをお忘れなく。
次は指し手を生成する関数 make_move を作ります。次のリストを見てください。
リスト：指し手の生成
/* 移動可能か */
int check_move( char *board, int n, int s )
{
if( board[n] == B ){
if( n < s ) return TRUE;
} else {
if( n > s ) return TRUE;
}
return FALSE;
}
/* 指し手の生成 */
int make_move( char *board, int s )
{
int i, j = 0, k = 0;
/* 隣への移動 */
while( (i = neighbor[s][j++]) >= 0 ){
if( check_move( board, i, s ) ){
move_position[k++] = i;
}
}
/* 跳び越し */
j = 0;
while( (i = jump[s][j++]) >= 0 ){
int n = jump[s][j++];
if( board[i] != board[n] && check_move( board, n, s ) ){
move_position[k++] = n;
}
}
return k;
}
関数 make_move の引数 board が盤面、s が空き場所の位置を表します。関数 check_move は石の移動方向をチェックします。生成した指し手は配列 move_position にセットします。move_position はグローバル変数として定義します。
最初に、隣の空き場所へ石を移動する場合をチェックします。隣接リスト neighbor から空き場所の隣の位置を取り出して変数 i にセットします。あとは check_move で移動方向をチェックするだけです。移動できる場合は、移動する石の位置 i を配列 move_position にセットします。
次に、他の石を跳び越して移動する場合をチェックします。跳び先表 jump から跳び越される石の位置と跳ぶ石の位置を取り出して、変数 i と n にセットします。board[i] と board[n] の値が異なっていて、check_move が真であれば n から s へ跳び越すことができます。配列 move_position に n をセットします。最後に生成した指し手の個数 k を返します。
あとは単純な幅優先探索です。配列 move_position から指し手を取り出し、石を移動して新しい局面を生成します。生成した局面はハッシュ法でチェックして、同一局面がなければキューに登録します。これらの処理は簡単なので説明は省略いたします。詳細は プログラムリスト をお読みくださいませ。
それでは実行結果を示します。
[0] [1] [2] [3] [4] [5] [6] [7]
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2
1 1 0 2 2 1 1 1 2 2 1 1 1 2 2 1 1 0 2 2 1 0 1 2 2 1 2 1 0 2 1 2 1 2 0 1 2 0 2 1
2 2 2 2 2 2 0 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[8] [9] [10] [11] [12] [13] [14] [15]
1 1 0 1 0 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1
1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2
1 2 1 2 1 1 2 1 2 1 1 0 1 2 1 1 2 1 0 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 0 2 1
1 2 2 1 2 2 1 2 2 1 2 2 1 0 2 0 1 2 2 1 2 2 1 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 1 2 2
[16] [17] [18] [19] [20] [21] [22] [23]
1 2 0 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2
1 1 2 1 1 0 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2
1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 0 1 2 0 2 1 0 2 1 2 1
2 1 2 2 1 2 0 1 2 2 1 0 2 1 2 2 1 2 2 1 2 2 1 2
1 2 2 1 2 2 1 2 2 1 2 2 1 2 0 1 2 1 1 2 1 1 2 1
[24] [25] [26] [27] [28] [29] [30] [31]
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 0 2 2
0 1 2 2 1 0 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2
1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 0 1 2 0 2 1 0 2 1 2 1 1 2 1 2 1
2 1 2 2 1 2 0 1 2 2 1 0 2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1
[32] [33] [34] [35] [36] [37] [38] [39]
2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2
1 2 1 2 1 1 0 1 2 1 1 2 1 0 1 1 2 1 2 1 1 2 1 2 1 1 2 0 2 1 0 2 1 2 1 2 0 1 2 1
2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1
[40] [41] [42] [43] [44] [45] [46]
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 0 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 0 2 1 2 0 1 2 1 2 2 1 0 1 2 2 0 1 1
2 1 1 2 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
最短手数は 46 手になりました。実行時間ですが、M.Hiroi のオンボロマシン (Windows 95, Pentium 166 MHz) で約 2 秒かかりました。スタートとゴールの双方向から探索を行うと、もう少し速くなるかもしれません。興味のある方は挑戦してみてください。ご参考までに、問題 (A) と (B) の解答を示します。
/*
* 平面上の蛙跳びゲーム（幅優先探索）
*
* Copyright (C) 2005 Makoto Hiroi
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* 盤面
０ １ ２
３ ４ ５
６ ７ ８ ９ 10
11 12 13
14 15 16
*/
#define TRUE 1
#define FALSE 0
#define SIZE 17
#define S 0
#define B 1
#define W 2
#define NIL (-1)
#define MAX 218790
#define HASH_SIZE 21881
/* 隣接リスト */
char neighbor[SIZE][5] = {
1, 3, -1, -1, -1, /* 0 */
0, 2, 4, -1, -1, /* 1 */
1, 5, -1, -1, -1, /* 2 */
0, 4, 6, -1, -1, /* 3 */
1, 3, 5, 7, -1, /* 4 */
2, 4, 8, -1, -1, /* 5 */
3, 7, -1, -1, -1, /* 6 */
4, 6, 8, -1, -1, /* 7 */
5, 7, 9, 11, -1, /* 8 */
8, 10, 12, -1, -1, /* 9 */
9, 13, -1, -1, -1, /* 10 */
8, 12, 14, -1, -1, /* 11 */
9, 11, 13, 15, -1, /* 12 */
10, 12, 16, -1, -1, /* 13 */
11, 15, -1, -1, -1, /* 14 */
12, 14, 16, -1, -1, /* 15 */
13, 15, -1, -1, -1, /* 16 */
};
/* 跳び先表 */
char jump[SIZE][9] = {
1, 2, 3, 6, -1, -1, -1, -1, -1, /* 0 */
4, 7, -1, -1, -1, -1, -1, -1, -1, /* 1 */
1, 0, 5, 8, -1, -1, -1, -1, -1, /* 2 */
4, 5, -1, -1, -1, -1, -1, -1, -1, /* 3 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, /* 4 */
4, 3, 8, 11, -1, -1, -1, -1, -1, /* 5 */
3, 0, 7, 8, -1, -1, -1, -1, -1, /* 6 */
4, 1, 8, 9, -1, -1, -1, -1, -1, /* 7 */
5, 2, 7, 6, 9, 10, 11, 14, -1, /* 8 */
8, 7, 12, 15, -1, -1, -1, -1, -1, /* 9 */
9, 8, 13, 16, -1, -1, -1, -1, -1, /* 10 */
8, 5, 12, 13, -1, -1, -1, -1, -1, /* 11 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, /* 12 */
12, 11, -1, -1, -1, -1, -1, -1, -1, /* 13 */
11, 8, 15, 16, -1, -1, -1, -1, -1, /* 14 */
12, 9, -1, -1, -1, -1, -1, -1, -1, /* 15 */
13, 10, 15, 14, -1, -1, -1, -1, -1, /* 16 */
};
/* 初期状態 */
char init_state[SIZE] = {
B,B,B,
B,B,B,
B,B,S,W,W,
W,W,W,
W,W,W,
};
/* 終了状態 */
char final_state[SIZE] = {
W,W,W,
W,W,W,
W,W,S,B,B,
B,B,B,
B,B,B,
};
/* キュー */
char state[MAX + 1][SIZE];
char space[MAX + 1];
int prev[MAX + 1];
char move_position[8];
/* ハッシュ表 */
int hash_table[HASH_SIZE];
int next[MAX];
/* ハッシュ表の初期化 */
void init_hash( void )
{
int i;
for( i = 0; i < HASH_SIZE; i++ ) hash_table[i] = NIL;
}
/* ハッシュ表の計算 */
int hash_value( char *board )
{
unsigned int value = 0;
int i;
for( i = 0; i < SIZE; i++ ){
value += value * 3 + board[i];
}
return value % HASH_SIZE;
}
/* データの挿入 */
int insert_hash( int n )
{
int value = hash_value( state[n] );
int p = hash_table[value];
for( ; p != NIL; p = next[p] ){
if( !memcmp( state[p], state[n], SIZE ) ) return FALSE;
}
/* 挿入 */
next[n] = hash_table[value];
hash_table[value] = n;
return TRUE;
}
/* 移動可能か */
int check_move( char *board, int n, int s )
{
if( board[n] == B ){
if( n < s ) return TRUE;
} else {
if( n > s ) return TRUE;
}
return FALSE;
}
/* 指し手の生成 */
int make_move( char *board, int s )
{
int i, j = 0, k = 0;
/* 隣への移動 */
while( (i = neighbor[s][j++]) >= 0 ){
if( check_move( board, i, s ) ){
move_position[k++] = i;
}
}
/* 跳び越し */
j = 0;
while( (i = jump[s][j++]) >= 0 ){
int n = jump[s][j++];
if( board[i] != board[n] && check_move( board, n, s ) ){
move_position[k++] = n;
}
}
return k;
}
/* 手順の表示 */
void print_state( char *board )
{
printf("%d %d %d\n%d %d %d\n%d %d %d %d %d\n %d %d %d\n %d %d %d\n\n",
board[0], board[1], board[2],
board[3], board[4], board[5],
board[6], board[7], board[8], board[9], board[10],
board[11], board[12], board[13],
board[14], board[15], board[16] );
}
void print_answer( int n )
{
int i;
if( n > 0 ) print_answer( prev[n] );
print_state( state[n] );
}
/* 幅優先探索 */
void solve( void )
{
int front = 0, rear = 1;
/* キューの初期化 */
memcpy( state[0], init_state, SIZE );
space[0] = 8;
prev[0] = -1;
/* ハッシュ表の初期化 */
init_hash();
insert_hash( 0 );
while( front < rear ){
int i;
int s = space[front];
int n = make_move( state[front], s );
for( i = 0; i < n; i++ ){
int j, p = move_position[i];
memcpy( state[rear], state[front], SIZE );
state[rear][s] = state[rear][p];
state[rear][p] = S;
space[rear] = p;
prev[rear] = front;
if( !memcmp( state[rear], final_state, SIZE ) ){
/* 発見したよ */
print_answer( rear );
printf("総数 %d\n", rear);
return;
} else if( insert_hash( rear ) ){
rear++;
}
}
front++;
}
}
int main()
{
int s = clock();
solve();
printf("時間 %d\n", clock() - s);
return 0;
}
図では黒石を B, 白石を W, 空き場所を S で表しています。
0:
B
B B
B B S W W
W W
W
1: 2: 3: 4: 5: 6:
B B B B B B
B B B S B W B W B W B W
B B W W W B B W W W B B S W W B B W S W B S W B W S B W B W
S W B W B W B W B W B W
W W W W W W
7: 8: 9: 10: 11: 12:
B B B B B B
B W B W B W B W B W B W
W B S B W W B W B W W B W B W W B W B W W B W S W W S W B W
B W B W S W W S W B W B
W S B B B B
13: 14: 15: 16: 17: 18:
B B B B B B
S W W S W W W W W W W W
W B W B W W B W B W W B S B W W B W B S W B W S B W S W B B
W B W B W B W B W B W B
B B B B B B
19: 20: 21: 22: 23:
B S W W W
W W W W W S W W W W
W W S B B W W B B B W W B B B W W B B B W W S B B
W B W B W B S B B B
B B B B B
図：問題 (A) の解答 (23 手)
図では黒石を B, 白石を W, 空き場所を S で表しています。
0:
B B
B B
B S W
W W
W W
1: 2: 3: 4: 5: 6: 7: 8:
B B B B B S B W B W B W B W B W
B B B S B B B B B B B B B B B B
B W W B W W B W W B S W B W S S W B W S B W W B
S W B W B W B W B W B W B W B W
W W W W W W W W W W W W W W S W
9: 10: 11: 12: 13: 14: 15: 16:
B W B W B W B W B W B W S W W S
B B B B B B B B B S S B B B B B
W W B W W S W W W W W W W W W W W W W W W W W W
B W B W B S S B B B B B B B B B
W S W B W B W B W B W B W B W B
17: 18: 19: 20: 21: 22: 23: 24:
W W W W W W W W W W W W W W W W
B B B S S B W B W B W B W B W B
W S W W B W W B W S B W W B S W S B W W B W W B
B B B B B B B B B B B B B B S B
W B W B W B W B W B W B S B B B
25: 26:
W W W W
W S W W
W W B W S B
B B B B
B B B B
図：問題 (B) の解答 (26 手)
次は、蛙跳びゲームの盤面を小さくしてみましょう。下図を見てください。
┌─┬─┐
│●│●│
├─┼─┼─┐
│●│ │○│
└─┼─┼─┤
│○│○│
└─┴─┘
図：蛙跳びゲーム
黒石と白石が 3 個ずつあります。この場合、今までの規則では黒石と白石を入れ替えることができません。そこで、規則を次のように変更します。
規則 1 と 2 で、黒石と白石を入れ替える最短手順を求めてください。出典は 参考文献 [1] と [2] です。[2] には規則 2 の問題が掲載されています。そこで、今回は新しい規則 1 を追加してみました。ちなみに、規則 1 の方が簡単に解けます。
それではプログラムを作りましょう。この問題は局面の総数が 140 通りしかないので、同一局面のチェックは線形探索で十分です。あとは、隣接リストと跳び先表を修正するだけです。
リスト：規則１
/* 隣接リスト（斜め跳びを許す） */
char neighbor[SIZE][7] = {
1, 2, 3, -1, -1, -1, -1, /* 0 */
0, 2, 3, 4, -1, -1, -1, /* 1 */
0, 1, 3, 5, -1, -1, -1, /* 2 */
0, 1, 2, 4, 5, 6, -1, /* 3 */
1, 3, 5, 6, -1, -1, -1, /* 4 */
2, 3, 4, 6, -1, -1, -1, /* 5 */
3, 4, 5, -1, -1, -1, -1, /* 6 */
};
/* 跳び先表 */
char jump[SIZE][3] = {
3, 6, -1, /* 0 */
3, 5, -1, /* 1 */
3, 4, -1, /* 2 */
-1, -1, -1, /* 3 */
3, 2, -1, /* 4 */
3, 1, -1, /* 5 */
3, 0, -1, /* 6 */
};
リスト：規則２
/* 隣接リスト */
char neighbor[SIZE][5] = {
1, 2, -1, -1, -1, /* 0 */
0, 3, -1, -1, -1, /* 1 */
0, 3, -1, -1, -1, /* 2 */
1, 2, 4, 5, -1, /* 3 */
3, 6, -1, -1, -1, /* 4 */
3, 6, -1, -1, -1, /* 5 */
4, 5, -1, -1, -1, /* 6 */
};
/* 跳び先表 */
char jump[SIZE][3] = {
-1, -1, -1, /* 0 */
3, 5, -1, /* 1 */
3, 4, -1, /* 2 */
-1, -1, -1, /* 3 */
3, 2, -1, /* 4 */
3, 1, -1, /* 5 */
-1, -1, -1, /* 6 */
};
規則 1 は斜め跳びができるので、隣接リストと跳び先表のデータ数は規則 2 よりも多くなります。それから、規則 2 では後戻りができるので、関数 check_move によるチェックが不要になります。修正はこれだけです。
それでは実行結果を示します。規則１の最短手数は 8 手になります。
[0]
1 1
1 0 2
2 2
[1] [2] [3] [4] [5] [6] [7] [8]
0 1 2 1 2 1 2 0 2 2 2 2 2 2 2 2
1 1 2 1 1 2 1 0 2 1 1 2 1 1 2 0 1 2 2 1 0 2 0 1
2 2 2 0 2 1 2 1 0 1 1 1 1 1 1 1
後戻りを許す規則 2 の場合、最短手数は 15 手になります。
[0] [1] [2] [3] [4] [5] [6] [7]
1 1 1 0 1 2 1 2 1 2 0 2 2 0 2 1
1 0 2 1 1 2 1 1 2 1 0 2 0 1 2 1 1 2 1 1 2 1 0 2
2 2 2 2 0 2 1 2 1 2 1 2 1 2 1 2
[8] [9] [10] [11] [12] [13] [14] [15]
2 1 2 1 2 1 2 0 2 2 2 2 2 2 2 2
1 2 0 1 2 2 1 2 2 1 2 2 1 0 2 0 1 2 2 1 0 2 0 1
1 2 1 0 0 1 1 1 1 1 1 1 1 1 1 1
[6] -> [7] で、黒石 (1) が後戻りしています。
今回は幅優先探索で解きましたが、「反復深化」でも簡単に解くことができると思います。興味のある方は挑戦してみてください。