ペグ・ソリテアは、盤上に配置されたペグ（駒）を最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動して取り除くことができます。
「トライトライ」は芦ヶ原伸之氏のデザインによるペグ・ソリテアです。次の図を見てください。
●───●
／ ＼ ／ ＼
●───●───●
／ ＼ ／ ＼ ／ ＼
●───●───●───●
／ ＼ ／ ＼ ／ ＼ ／ ＼
●───●───○───●───●
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
●───●───●───●───●───●
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
●───●───●───●───●
図：トライトライ (25 穴盤)
トライトライは 25 の穴にペグがありますが、そこからペグをひとつ取り除いてゲームを開始します。上図では黒丸がペグを表し、中央の白丸が空き場所を表しています。ペグは線に沿って移動することができます。ルールに従ってペグを移動し、最後にペグがひとつ残る跳び方の最小手数を求めてください。
参考文献 [6] によると、最初の空き位置と最後に残ったペグの位置が同じになることを「補償型の解」といい、最初の空き位置が盤の中央で、なおかつ補償型の解がある場合を「中央補償型の解」というそうです。トライトライには「中央補償型の解」が存在します。この最小手数を求めてください。
それではプログラムを作りましょう。最小手数を求めるアルゴリズムといえば「幅優先探索」ですが、今回は 変形三角盤 と同様に「反復深化＋下限値枝刈り法」で解くことにします。
プログラムのポイントは、ペグを跳び越すときに手数も同時に数えていくことです。直前に動かしたペグと違うペグを動かすときは手数をカウントし、同じペグを動かすときは手数をカウントしません。これで連続跳び越しを 1 手と数えることができます。そして、この手数を使って反復深化を実行するわけです。
最初に、ペグの跳び先表を定義します。下図のように穴に番号をつけると、跳び先表は次のようになります。
０───１
／ ＼ ／ ＼
２───３───４
／ ＼ ／ ＼ ／ ＼
５───６───７───８
／ ＼ ／ ＼ ／ ＼ ／ ＼
９───10───11───12───13
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
14───15───16───17───18───19
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
20───21───22───23───24
図：トライトライ (25 穴盤)
リスト：跳び先表
const char jump_table[][SIZE] = {
{ 2, 5, 3, 7, -1}, /* 0 */
{ 3, 6, 4, 8, -1}, /* 1 */
{ 3, 4, 5, 9, 6, 11, -1}, /* 2 */
{ 6, 10, 7, 12, -1}, /* 3 */
{ 3, 2, 7, 11, 8, 13, -1}, /* 4 */
{ 2, 0, 6, 7, 9, 14, 10, 16, -1}, /* 5 */
{ 3, 1, 7, 8, 10, 15, 11, 17, -1}, /* 6 */
{ 3, 0, 6, 5, 11, 16, 12, 18, -1}, /* 7 */
{ 4, 1, 7, 6, 12, 17, 13, 19, -1}, /* 8 */
{ 5, 2, 10, 11, 15, 21, -1}, /* 9 */
{ 6, 3, 11, 12, 15, 20, 16, 22, -1}, /* 10 */
{ 6, 2, 7, 4, 10, 9, 12, 13, 16, 21, 17, 23, -1}, /* 11 */
{ 7, 3, 11, 10, 17, 22, 18, 24, -1}, /* 12 */
{ 8, 4, 12, 11, 18, 23, -1}, /* 13 */
{ 9, 5, 15, 16, -1}, /* 14 */
{10, 6, 16, 17, -1}, /* 15 */
{10, 5, 11, 7, 15, 14, 17, 18, -1}, /* 16 */
{11, 6, 12, 8, 16, 15, 18, 19, -1}, /* 17 */
{12, 7, 17, 16, -1}, /* 18 */
{13, 8, 18, 17, -1}, /* 19 */
{15, 10, 21, 22, -1}, /* 20 */
{15, 9, 16, 11, 22, 23, -1}, /* 21 */
{16, 10, 17, 12, 21, 20, 23, 24, -1}, /* 22 */
{17, 11, 18, 13, 22, 21, -1}, /* 23 */
{18, 12, 23, 22, -1}, /* 24 */
};
データは跳び越す位置と着地する位置の 2 個 1 セットで表しています。たとえば、2 番のペグは 3 番を跳び越して 4 番に着地するという跳び方があります。データの終端は -1 で表しています。
ペグ・ソリテアでは、コーナーと辺にあるペグから下限値を求めることができます。次の図を見てください。
●───●
／ ＼ ／ ＼
○───○───○
／ ＼ ／ ＼ ／ ＼
○───○───○───○
／ ＼ ／ ＼ ／ ＼ ／ ＼
○───○───○───○───○
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
●───○───○───○───○───●
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
●───○───○───○───●
図：コーナーにあるペグ
ペグ・ソリテアの場合、コーナーにあるペグはほかのペグから跳び越されることはありません。つまり、コーナーのペグは自分でジャンプするしか移動する方法がないのです。したがって、コーナーにペグが残っていれば、最低でもその個数だけ移動手数が必要になります。トライトライの場合、コーナーは 0, 1, 14, 19, 20, 24 番の 6 か所あります。これを下限値として利用することができます。
ところが、コーナーペグの下限値だけでは不十分のようで、M.Hiroi のオンボロマシン (Pentium 166 MHz) では時間がとてもかかるのです。そこで、辺にあるペグを下限値として使うことにします。次の図を見てください。
○───○
／ ＼ ／ ＼
●───○───●
／ ＼ ／ ＼ ／ ＼
（Ａ）●───○───○───●（Ｂ）
／ ＼ ／ ＼ ／ ＼ ／ ＼
●───○───○───○───○
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
○───○───○───○───○───○
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
○───●───○───●───○
（Ｃ）
図：辺にあるペグ
トライトライには 3 つの辺 (2, 5, 9), (4, 8, 13), (21, 22, 23) があります。図 (A) の辺を見てください。ペグが 3 つ並んでいますね。この状態では、ほかのペグから跳び越されることはありません。つまり、コーナーペグと同様に自分でジャンプするしか移動する方法がないのです。
だからといって、移動手数が 3 手必要になるわけではありません。たとえば、中央のペグが 5 -> 16 -> 14 -> 5 -> 0 と連続跳びすれば、辺にあるペグを取り除くことができますね。つまり、辺にあるペグが 3 つ並んでいる場合、移動手数は最低でも 1 手必要になるのです。
図 (B) の状態も同様です。ペグが 2 つ並んでいる状態では、ほかのペグから跳び越されることはありません。この場合、移動手数は最低でも 1 手必要になります。ただし、辺にペグがひとつしかない場合や図 (C) の状態では、ほかのペグの連続跳びで取り除かれることがあるので、移動手数は 0 手とします。辺にあるペグとコーナーペグを合わせて下限値として利用することにしましょう。
ところで、これらの下限値を利用する場合、注意点がひとつだけあります。それはペグが連続跳びをしている場合です。次の局面を見てください。
０───１
／ ＼ ／ ＼
●───●───４
／ ＼ ／ ＼ ／ ＼
５───●───７───８
／ ＼ ／ ＼ ／ ＼ ／ ＼
９───10───●───12───13
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
14───15───●───17───18───19
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
20───21───22───23───24
図：最終手で連続跳びする局面
上限値を N 手とします。今、上限値の 1 手前で上図の局面になりました。ここで、16 -> 7 -> 5 -> 0 -> 7 または 16 -> 7 -> 0 -> 5 -> 7 と連続跳びすると、N 手で解くことができますね。ここで 15 -> 7 -> 5 と跳んだ局面に注目してください。辺のペグ (2 番と 5 番) が 2 つ並びますが、ここで下限値に 1 を加えると上限値 N を越えるため枝刈りされてしまいます。15 -> 7 -> 0 と跳ぶ場合も同じです。ペグはコーナー (0 番) に移動しますが、ここで下限値に 1 を加えると上限値 N を越えてしまいます。これでは解を求めることができませんね。
そこで、直前に移動したペグは下限値の計算から除外することにします。ようするに、直前に移動したペグは連続跳びする可能性があるので、下限値の対象にしてはいけないのです。15 -> 7 -> 5 と跳んで 2 番と 5 番のペグが並んだ場合、直前に移動したペグは 5 番なので下限値の計算から除外します。15 -> 7 -> 0 と跳んでペグがコーナーに移動した場合も同様です。これで条件を満たす手順が枝刈りされることはありません。
下限値を求めるときに、コーナーに残っているペグをいちいち数えているようでは、面倒で時間もかかりそうです。そこで、グローバル変数 lower_value にコーナーに残っているペグの数を記憶しておきます。そして、コーナーからジャンプするときは lower_value の値をひとつ減らし、コーナーに着地するときはひとつ増やすことにします。もちろん、バックトラックするときは元の値に戻します。この処理のため、グローバル変数にコーナーを判定するための配列 corner を定義します。
リスト：グローバル変数の定義
/* corner */
const char corner[SIZE] = {
1, 1,
0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1,
};
char board[SIZE]; /* 盤面 */
char move[MAX_JUMP][2]; /* 移動手順を格納 */
int lower_value = 6; /* コーナーのペグ数 */
盤面は char 型の配列 board で表します。探索はこの配列を直接書き換え、バックトラックするときに元の値に戻します。移動手順は配列 move に格納します。ペグが 23 回移動すると盤上のペグはひとつになります。したがって、MAX_JUMP は 23 となります。そして、ペグを動かす関数 move_piece とペグを元に戻す関数 back_piece で、コーナーにあるペグのチェックを行います。
リスト：ペグの移動
/* ペグを動かす */
void move_piece( int n, int from, int del, int to )
{
board[from] = 0;
board[del] = 0;
board[to] = 1;
move[n][0] = from;
move[n][1] = to;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value--;
} else if( corner[to] ){
lower_value++;
}
}
/* ペグを元に戻す */
void back_piece( int from, int del, int to )
{
board[from] = 1;
board[del] = 1;
board[to] = 0;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value++;
} else if( corner[to] ){
lower_value--;
}
}
コーナーにあるペグは跳び越されることがないので、from か to をチェックすればＯＫです。form がコーナーであれば、ペグがコーナーから取り除かれました。この場合、lower_value をひとつ減らします。to がコーナーであれば、ペグがコーナーに着地したわけですから、lower_value をひとつ増やせばいいわけです。
関数 back_piece では、この逆の操作になること、つまり from がコーナーであれば lower_value をひとつ増やし、to がコーナーであれば lower_value をひとつ減らすことに注意してください。
それでは、下限値を求める関数 get_lower_value を作ります。
リスト：下限値の計算
/* edge */
const char edge[SIZE] = {
0, 0,
1, 0, 2,
1, 0, 0, 2,
1, 0, 0, 0, 2,
0, 0, 0, 0, 0, 0,
0, 3, 3, 3, 0,
};
/* 辺の下限値 */
const char edge_value[8] = {
/* 000, 001, 010, 011, 100, 101, 110, 111 ペグの並び */
0, 0, 0, 1, 0, 0, 1, 1, /* 下限値 */
};
/* 辺の下限値を求めるマクロ */
#define GET_EDGE_VALUE(a,b,c) edge_value[(board[(a)]<<2) + (board[(b)]<<1) + board[(c)]]
/* 下限値の計算 */
int get_lower_value( int prev )
{
int low = lower_value - corner[prev];
int eg = edge[prev];
/* 辺のチェック */
if( eg != 1 ) low += GET_EDGE_VALUE( 2, 5, 9 );
if( eg != 2 ) low += GET_EDGE_VALUE( 4, 8, 13 );
if( eg != 3 ) low += GET_EDGE_VALUE( 21, 22, 23 );
return low;
}
get_lower_value の引数 prev は直前に移動したペグの位置を表します。最初に、コーナーペグの下限値を求めます。配列 corner の要素はコーナーペグならば 1、そうでなければ 0 なので、lower_value - corner[perv] で下限値を求めることができます。
辺の下限値は配列 edge_value から求めます。ペグの並びをビットに対応させて数値で表すと 0 から 7 の値になります。それに対応する下限値を edge_value にセットしておきます。そして、マクロ GET_EDGE_VALUE でペグの並びを数値に変換して下限値を求めます。辺のペグは配列 edge によりグループ分けされていて、prev が同じグループでなければ、下限値 low に GET_EDGE_VALUE で求めた値を加算します。
次は反復深化を行う関数 search_move を作ります。次のリストを見てください。
リスト：反復深化＋下限値枝刈り法
void search_move( int n, int jc, int limit )
{
int prev = move[n - 1][1];
if( (jc + get_lower_value( prev )) > limit ) return;
if( n == MAX_JUMP ){
print_move(); exit( 0 );
} else {
int from, del, to, i;
for( from = 0; from < SIZE; from++ ){
if( !board[from] ) continue; /* ペグが無い */
i = 0;
while( (del = jump_table[from][i++]) != -1 ){
to = jump_table[from][i++];
if( board[del] && !board[to] ){
/* 跳び越せる */
move_piece( n, from, del, to );
search_move( n + 1, (prev == from ? jc : jc + 1), limit );
back_piece( from, del, to );
}
}
}
}
}
引数 n がペグの移動回数、jc が跳んだ回数、limit が反復深化の上限値を表します。最初に、直前に移動したペグの位置を move から取り出して prev にセットします。move[n - 1][0] が移動元の位置、move[n - 1][1] が移動先の位置を表します。次に、get_lower_value を呼び出して下限値を求め、jc + 下限値が limit よりも大きくなったならば枝刈りを行います。ここが下限値枝刈り法のポイントです。
n が MAX_JUMP に達したならば、盤上にはひとつのペグしか残っていません。print_move で移動手順を表示して、exit でプログラムの実行を終了します。
ペグが複数残っている場合は探索を続行します。跳び先表から跳び越す位置を del に、着地する位置を to にセットします。del の位置にペグがあり to の位置が空いているならば、ペグを移動することができます。search_move を再帰呼び出しするとき、prev と from が同じであれば連続跳びなので、跳んだ回数 jc をカウントしないことに注意してください。そして、再帰呼び出しから戻ってきたら back_piece で元の状態に戻します。
あとはとくに難しいところはないでしょう。詳細は プログラムリスト をお読みくださいませ。
それでは実行結果を示します。移動手順は 1 手を ( 移動元 (from), 移動先 (to) ) で表し、連続跳び越しの場合は (from, to1, to2, ..., to3) とします。最初に取り除くペグが 11 番の場合、初手は 6 通りありますが、トライトライの対称性からその中のひとつだけ調べれば十分です。このプログラムでは初手を (2, 11) としました。
・・・手数 9 を探索中・・・ ・・・手数 10 を探索中・・・ ・・・手数 11 を探索中・・・ (2, 11)(1, 6)(10, 3)(8, 1, 6)(22, 10, 3)(19, 8, 6)(0, 7, 16)(20, 22, 10)(24, 22) (9, 2, 11, 13, 23, 21, 9)(14, 5, 16, 18)
最短手数は 11 手、実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で 1.2 秒でした。コーナーペグだけではなく、辺のペグを下限値に加えた効果は十分に出ていますね。また、思っていたよりも短い手数で解けたのには驚きました。トライトライは連続跳びしやすい盤なのかもしれません。
今度は「中央補償型の解」を求めてみましょう。プログラムの改造は簡単です。関数 search_move でペグがひとつ残ったときに、そのペグが 11 番にあるかチェックするだけです。
if( n == MAX_JUMP && board[11] ){
print_move(); exit( 0 );
}
さっそく実行してみたところ、結果は次のようになりました。
・・・手数 9 を探索中・・・ ・・・手数 10 を探索中・・・ ・・・手数 11 を探索中・・・ ・・・手数 12 を探索中・・・ (2, 11)(1, 6)(9, 2)(0, 5)(10, 3)(20, 10)(8, 6, 15)(22, 10)(14, 16, 7) (19, 8, 6, 15)(24, 22, 20, 10)(4, 2, 9, 11, 13, 23, 11)
最短手数は 12 手、実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で約 84 秒でした。手数が 1 手長くなったぶんだけ、時間もかかるようになりました。そこで、ペグをグループに分けて枝刈りを行ってみましょう。
ペグ・ソリテアの場合、ペグは移動できる場所が決まっていて、下図のようなグループに分けることができます。
０───１
／ ＼ ／ ＼
３───２───３
／ ＼ ／ ＼ ／ ＼
０───１───０───１
／ ＼ ／ ＼ ／ ＼ ／ ＼
３───２───３───２───３
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
０───１───０───１───０───１
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
２───３───２───３───２
図：ペグのグループ分け
たとえば、0 番のペグは 5, 7, 14, 16, 18 番にしか移動することができません。逆にいえば、この場所にあるペグは、これ以外の場所へ移動することはできないのです。したがって、これをひとつのグループとして考えることができます。これをグループ 0 としましょう。同じようにペグの位置によって、上図のように 4 つのグループに分けることができます。ペグは移動してもグループは変わらないし、跳び越すペグは必ず他グループのペグになります。
ここで、グループ 3 に注目してください。このグループのペグは、最後には 11 番にひとつだけ必要になります。すなわち、このグループのペグの個数が 0 になると、パズルを解くことができないわけです。この枝刈りは簡単に実現できます。実際に試してみたのですが、残念ながらこの枝刈りの効果はほとんどありませんでした。そこで、考え方を変えてみましょう。
最後に残るペグは 11 番ですから、最終手で跳ぶペグはグループ 3 でなければいけません。また、最終手でグループ 3 のペグが複数残っていても解くことはできませんね。つまり、最終手で跳ぶペグはグループ 3 で、ペグの個数はそのひとつだけでないと解くことはできないのです。
それから、最終手でグループ 3 のペグを動かすので、その 1 手前ではグループ 3 のペグを動かすことはありません。もし、最終 1 手前でグループ 3 のペグが複数残っているならば、グループ 3 のペグを取り除くため他グループのペグを動かさないといけません。
また、最終 1 手前でグループ 3 のペグがひとつしか残っていない場合、このペグを動かすと最終手でも同じペグを動かすことになり連続跳び越しになってしまいます。これで解けるのであれば最終 1 手前で解けることになり、反復深化の動作と矛盾してしまいます。したがって、最終 1 手前で動かすのはグループ 3 以外のペグになります。
この 2 つの条件で枝刈りを行ってみましょう。
プログラムの修正は簡単です。ペグのグループは配列 group で定義して、
グループごとのペグの個数は配列 rest_peg に格納します。
リスト：ペグのグループ分け
/* Group */
const char group[SIZE] = {
0, 1,
3, 2, 3,
0, 1, 0, 1,
3, 2, 3, 2, 3,
0, 1, 0, 1, 0, 1,
2, 3, 2, 3, 2
};
/* Group ごとのペグの個数 */
int rest_peg[4] = { 6, 6, 6, 6 };
配列 rest_peg は関数 move_piece と back_piece で操作します。あとは関数 search_move に枝刈りを追加するだけです。
リスト：反復深化＋下限値枝刈り法
void search_move( int n, int jc, int limit )
{
int prev = move[n - 1][1];
if( (jc + get_lower_value( prev )) > limit ) return;
if( n == MAX_JUMP ){
print_move(); exit( 0 );
} else {
int from, del, to, i;
for( from = 0; from < SIZE; from++ ){
if( !board[from] ) continue; /* ペグが無い */
i = 0;
while( (del = jump_table[from][i++]) != -1 ){
to = jump_table[from][i++];
if( board[del] && !board[to] ){
/* 跳び越せる */
move_piece( n, from, del, to );
if( prev == from ){
search_move( n + 1, jc, limit );
} else {
if( jc < limit - 2 ||
(jc == limit - 2 && group[from] != 3) ||
(jc == limit - 1 && group[from] == 3 && rest_peg[3] == 1)){
search_move( n + 1, jc + 1, limit );
}
}
back_piece( from, del, to );
}
}
}
}
}
手数 jc を増やして search_move を再帰呼び出しするときにチェックを行います。最終 1 手前ではグループ 3 のペグではないこと、最終手ではグループ 3 のペグでひとつしかないことを確認します。プログラムの主な修正はこれだけです。詳細は プログラムリスト２ をお読みくださいませ。
さっそく実行してみたところ、実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で 50 秒、約 1.7 倍の高速化に成功しました。それなりの効果はありましたが、これ以上の高速化は下限値の精度を上げないと無理のようです。興味のある方は挑戦してみてください。