ペグ・ソリテアは、盤上に配置されたペグ（駒）を、最後にはひとつ残るように取り除いていく、古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。
盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。
●─●─●
│ │ │
●─●─●
│ │ │
●─●─●─●─●─●─●
│ │ │ │ │ │ │
●─●─●─○─●─●─●
│ │ │ │ │ │ │
●─●─●─●─●─●─●
│ │ │
●─●─●
│ │ │
●─●─●
図：ペグ・ソリテア 33 穴英国盤
33 のマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。上図では、ペグを ● で空き位置を ○ で表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、盤の種類によっては、ペグを取り除く位置（空き位置）によって、解けない場合もあるので注意してください。
参考文献 [6] によると、最初の空き位置と最後に残ったペグの位置が同じになることを「補償型の解」といい、最初の空き位置が盤の中央で、なおかつ、補償型の解がある場合を「中央補償型の解」というそうです。33 穴英国盤には、中央補償型の解があるそうです。
ペグ・ソリテアの場合、昔から補償型や中央補償型の解の最小手数を求めることが行われてきました。33 穴英国盤のように、数が多いと解くのが大変なので、サイズを小さくした簡単なペグ・ソリテアをコンピュータで解いてみましょう。
まずは数をぐっと減らして 13 穴盤から解きます。
●
／│＼
●─●─●
／│＼│／│＼
●─●─○─●─●
＼│／│＼│／
●─●─●
＼│／
●
図：13 穴盤
斜め跳びを許した条件で、中央補償型の最小手数を求めます。最小手数といえば「幅優先探索」ですが、連続飛びの処理が面倒になりそうなので、ここは「深さ優先探索」を採用することにします。
プログラムのポイントは、ペグを跳び越すときに手数も同時に数えていくことです。直前に動かしたペグと違うペグを動かすときは手数をカウントし、同じペグを動かすときは手数をカウントしません。そして、手数の上限値を定めて探索を行います。たとえば、最初は 5 手を限度に探索し、見つからなければ上限値を 6 手に増やす、というように 1 手ずつ増やしながら探索するのです。
このような探索を「反復深化」 [*1] と呼びます。幅優先探索が使えない問題には有効な探索手法のひとつです。
それではプログラムを作りましょう。使用するプログラミング言語はＣ言語です。ペグ・ソリテアの場合、ペグの「跳び先表」を用意すると簡単にプログラムできます。盤面は 1 次元配列を使って表し、座標は次のように定義します。
０
／│＼
１─２─３
／│＼│／│＼
４─５─６─７─８
＼│／│＼│／
９─10─11
＼│／
12
図：盤の座標
リスト：跳び先表の定義
char jump_table[][SIZE] = {
{ 1, 4, 2, 6, 3, 8, -1}, /* 0 */
{ 2, 3, 5, 9, 6, 11, -1}, /* 1 */
{ 6, 10, -1}, /* 2 */
{ 2, 1, 7, 11, 6, 9, -1}, /* 3 */
{ 1, 0, 5, 6, 9, 12, -1}, /* 4 */
{ 6, 7, -1}, /* 5 */
{ 2, 0, 5, 4, 10, 12, 7, 8, -1},/* 6 */
{ 6, 5, -1}, /* 7 */
{ 3, 0, 7, 6, 11, 12, -1}, /* 8 */
{ 5, 1, 6, 3, 10, 11, -1}, /* 9 */
{ 6, 2, -1}, /* 10 */
{ 7, 3, 6, 1, 10, 9, -1}, /* 11 */
{ 9, 4, 10, 6, 11, 8, -1}, /* 12 */
};
データは跳び越す位置と着地する位置の 2 個 1 セットで表しています。たとえば、10 のペグは 6 を跳び越して 2 に着地する、という跳び方があります。データの終端は -1 で表しています。
次にグローバル変数を定義します。
リスト：グローバル変数の定義
/* 盤面 */
char board[SIZE] = {
1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
};
char move[MAX_JUMP][2]; /* 手順を格納 */
int count = 0; /* 解の総数をカウント */
int jump_limit; /* 探索する手数 */
盤面は配列 board で表します。探索はこの配列を直接書き換え、バックトラックするときに元の値に戻します。移動手順は配列 move に格納します。ペグが 11 回移動すると盤上のペグはひとつになるので、MAX_JUMP は 11 となります。
探索プログラムは次のようになります。
リスト：手順の探索
void search_move( int n, int jc )
{
if( jc > jump_limit ) return;
if( n == MAX_JUMP && board[6] ){
count++;
print_move();
} 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, (move[n-1][1] == from ? jc : jc + 1) );
back_piece( from, del, to );
}
}
}
}
}
引数 n がペグの移動回数を表し、jc が跳んだ回数を表します。jc が探索手数 jump_limit より多くなったならば探索を打ち切ります。ここが重要なポイントですが、プログラム自体はいたって簡単ですね。n が MAX_JUMP に達したならば、盤上にはひとつのペグしか残っていません。それが中央の board[6] にあるならば解の条件を満たします。count を +1 して print_move で手順を表示します。
ペグが複数残っている場合は、探索を続行します。ペグの移動処理も簡単です。跳び先表から跳び越す位置を del に、着地する位置を to にセットします。del の位置にペグがあり、to の位置が空いているならば、ペグを移動することができます。
ペグの移動は move_piece で行います。search_move を再帰呼び出しするときは、前回移動したペグ move[n-1][1] と同じペグならば、跳んだ回数 jc をカウントしないことに注意してください。そして、再帰呼び出しから戻ってきたら、back_piece で元の状態に戻します。
move_piece, back_piece, print_move は簡単なので説明は省略します。プログラムリスト を参照してください。
最後にメインプログラムを説明します。
リスト：メインプログラム
int main()
{
int move, start, end;
start = clock();
for( move = 5; move <= MAX_JUMP; move++ ){
printf("・・・手数 %d を探索中・・・\n", move );
jump_limit = move;
move_piece( 0, 0, 2, 6 ); /* 0 からスタート */
search_move( 1, 1 );
if( count ) break;
}
end = clock();
printf("総数 %d 個, 時間 %d\n", count, end - start );
return 0;
}
変数 move が手数を表しています。move を 5 からひとつずつ増やして、探索を行います。最初に移動できるペグは 0, 4, 8, 12 の 4 か所ありますが、0 だけを調べています。count が 0 でなければ解が見つかったので、break でループから脱出します。
それでは実行結果を示します。あいかわらず Pentium 166 MHz のオンボロマシンで実行しました。
・・・手数 5 を探索中・・・ ・・・手数 6 を探索中・・・ ・・・手数 7 を探索中・・・ ( 0, 6)(10, 2)( 4, 0, 6)(11, 1)( 8, 0, 4, 6)( 7, 5)(12, 4, 6) ( 0, 6)(10, 2)( 4, 0, 6)(11, 1)( 8, 6)( 5, 7)(12, 4, 0, 8, 6) ( 0, 6)(10, 2)( 4, 0, 6)(11, 1)(12, 4, 6)( 7, 5)( 8, 0, 4, 6) ( 0, 6)(10, 2)( 4, 6)( 7, 5)( 8, 0, 4, 6)( 9, 3)(12, 8, 0, 6) ( 0, 6)(10, 2)( 4, 6)( 7, 5)( 8, 0, 4, 6)(11, 1)(12, 4, 0, 6) ( 0, 6)(10, 2)( 4, 6)( 7, 5)( 8, 0, 6)( 9, 3)(12, 8, 0, 4, 6) ( 0, 6)(10, 2)( 4, 6)( 7, 5)(12, 4, 0, 6)( 3, 9)( 8,12, 4, 6) ( 0, 6)(10, 2)( 4, 6)( 7, 5)(12, 4, 0, 6)(11, 1)( 8, 0, 4, 6) ( 0, 6)(10, 2)( 4, 6)( 7, 5)(12, 4, 6)( 3, 9)( 8,12, 4, 0, 6) ( 0, 6)(10, 2)( 8, 0, 6)( 9, 3)( 4, 0, 8, 6)( 5, 7)(12, 8, 6) ( 0, 6)(10, 2)( 8, 0, 6)( 9, 3)( 4, 6)( 7, 5)(12, 8, 0, 4, 6) ( 0, 6)(10, 2)( 8, 0, 6)( 9, 3)(12, 8, 6)( 5, 7)( 4, 0, 8, 6) ( 0, 6)(10, 2)( 8, 6)( 5, 7)( 4, 0, 6)(11, 1)(12, 4, 0, 8, 6) ( 0, 6)(10, 2)( 8, 6)( 5, 7)( 4, 0, 8, 6)( 9, 3)(12, 8, 0, 6) ( 0, 6)(10, 2)( 8, 6)( 5, 7)( 4, 0, 8, 6)(11, 1)(12, 4, 0, 6) ( 0, 6)(10, 2)( 8, 6)( 5, 7)(12, 8, 0, 6)( 1,11)( 4,12, 8, 6) ( 0, 6)(10, 2)( 8, 6)( 5, 7)(12, 8, 0, 6)( 9, 3)( 4, 0, 8, 6) ( 0, 6)(10, 2)( 8, 6)( 5, 7)(12, 8, 6)( 1,11)( 4,12, 8, 0, 6) 総数 18 個, 時間 328
7 手で解を見つけました。13 穴盤なので、オンボロマシンでも実行時間は 1 秒もかかりません。18 通りの解を見つけましたが、どの解も最後は連続跳びで中央に着地するところが面白いですね。
ところで、このプログラムは回転解や対称解などの重複解をチェックしていません。興味のある方は、重複解のチェックを入れてみるといいでしょう。
/*
* peg1.c : ペグ・ソリティア 13 穴盤
*
* Copyright (C) 2000 Makoto Hiroi
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 13
#define MAX_JUMP 11
/* 跳び先表 */
char jump_table[][SIZE] = {
{ 1, 4, 2, 6, 3, 8, -1}, /* 0 */
{ 2, 3, 5, 9, 6, 11, -1}, /* 1 */
{ 6, 10, -1}, /* 2 */
{ 2, 1, 7, 11, 6, 9, -1}, /* 3 */
{ 1, 0, 5, 6, 9, 12, -1}, /* 4 */
{ 6, 7, -1}, /* 5 */
{ 2, 0, 5, 4, 10, 12, 7, 8, -1},/* 6 */
{ 6, 5, -1}, /* 7 */
{ 3, 0, 7, 6, 11, 12, -1}, /* 8 */
{ 5, 1, 6, 3, 10, 11, -1}, /* 9 */
{ 6, 2, -1}, /* 10 */
{ 7, 3, 6, 1, 10, 9, -1}, /* 11 */
{ 9, 4, 10, 6, 11, 8, -1}, /* 12 */
};
/* 盤面 */
char board[SIZE] = {
1,
1,1,1,
1,1,0,1,1,
1,1,1,
1,
};
/* 跳び手順を格納 */
char move[MAX_JUMP][2];
/* 解の総数をカウント */
int count = 0;
/* 探索する手数 */
int jump_limit;
/* 駒を動かす */
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;
}
/* 駒を元に戻す */
void back_piece( int from, int del, int to )
{
board[from] = 1;
board[del] = 1;
board[to] = 0;
}
/* 手順を表示 */
void print_move( void )
{
int i, j;
for( i = 0, j = 1; i < MAX_JUMP; i++, j++ ){
printf("(%2d,%2d", move[i][0], move[i][1] );
for( ; j < MAX_JUMP; i++, j++ ){
if( move[i][1] != move[j][0] ) break;
printf(",%2d", move[j][1] );
}
printf(")");
}
printf("\n");
}
/* 手順の探索 */
void search_move( int n, int jc )
{
if( jc > jump_limit ) return;
if( n == MAX_JUMP && board[6] ){
count++;
print_move();
} 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, (move[n-1][1] == from ? jc : jc + 1) );
back_piece( from, del, to );
}
}
}
}
}
int main()
{
int move, start, end;
start = clock();
for( move = 5; move <= MAX_JUMP; move++ ){
printf("・・・手数 %d を探索中・・・\n", move );
jump_limit = move;
move_piece( 0, 0, 2, 6 ); /* 0 からスタート */
search_move( 1, 1 );
if( count ) break;
}
end = clock();
printf("総数 %d 個, 時間 %d\n", count, end - start );
return 0;
}