最後までいったのだが、途中をなんとか表示しなければならない。つまり、どのような順番で動かしていけば最終的に最後に中央に１個だけ残せたかである。
再帰的になっているので、その結果はスタックに残っていると言えば言えないこともないのだが、どこかに移動の履歴を記憶するようにしたい。記憶ができれば、再生は後から考えればいいだろう。
ピンを移動するのは、あきらかに forward() と backward() の２つの関数であるが、動きを記憶できる配列があって、何手目、つまり何個目(n)を取り除くときの手を、配列のn番目の要素として記録、つまり上書き記録すれば大丈夫だろう。
履歴記録配列
┏━━━┓
┃ ┃ ← １個目を取り除くときの履歴
┣━━━┫
┃ ┃ ← ２個目を取り除くときの履歴
┣━━━┫
┃ ┃ ← ３個目を取り除くときの履歴
┣━━━┫
┃ ┃ ・・・・・・・・・・・・・・
┣━━━┫
┣━━━┫
┃ ┃
┗━━━┛
この履歴に記憶するのは、関数 forward( int x, int y, int dx, int dy ) の引数全てでよいはずだ。この履歴の１要素分を、以下のように構造体にしてしまおう。 typedefしてあるので、movement という型にしてしまった。
typedef struct { /* 移動 */
int x;
int y;
int dx;
int dy;
} movement;
そして、履歴用の配列として、 history[]を設けた。
movement history[40]; /* 移動履歴 */
また、残りペグ数だけでなく、総ペグ数(初期のペグ数)も設けた。したがって、プログラムの先頭で、配列などを以下のように宣言した。
movement history[40]; /* 移動履歴 */
char board[7][7]; /* ペグ・ソリテリア盤 */
int totalcount; /* 総ペグ数 */
int restcount; /* 残りペグ数 */
まず、総ペグ数は、最初に設定しなければならないので、関数 initboard()の最後で、 restcount と totalcount を一致させる。
void initboard( void )
{
int x, y;
for( x=0; x<7; ++x )
for( y=0; y<7; ++y )
board[x][y] = OUT;
for( x=2; x<5; ++x )
for( y=0; y<7; ++y )
board[x][y] = EXIST;
for( y=2; y<5; ++y )
for( x=0; x<7; ++x )
board[x][y] = EXIST;
board[3][3] = BLANK;
restcount = 0;
for( x=0; x<7; ++x )
for( y=0; y<7; ++y )
if( board[x][y] == EXIST )
++restcount;
totalcount = restcount;
}
次にすることは、前進移動 forward() の動きを、履歴の指定要素の所に記憶する。履歴配列の先頭から順に記憶するとすれば、添字が、totalcount - restcount であれば良いだろう。とういことで、forward()の先頭で、以下のようにして履歴配列に動きを記憶させた。
void forward( int x, int y, int dx, int dy )
{
movement *hp;
hp = history+(totalcount - restcount);
hp->x = x;
hp->y = y;
hp->dx = dx;
hp->dy = dy;
board[x][y] = BLANK;
board[x+dx][y+dy] = BLANK;
board[x+dx*2][y+dy*2] = EXIST;
--restcount;
}
履歴を記録しても、実際にどう記録されているか分かったものではない。それで、履歴をプリントする関数を作ってみた。この関数は、動作テストだけなので、こんなもので充分だろう。
void printhistory( void )
{
int i, n;
for( i = totalcount ; i>restcount; --i ) {
n = totalcount-i;
printf( "%2d\t%2d,%2d\t%2d,%2d\n", n,
history[n].x, history[n].y,
history[n].dx, history[n].dy );
}
}
最後までたどり着いてから履歴をプリントするという大胆な方法もあるが、
void search( void )
{
int x, y;
if( restcount == 1 && get(3,3) == EXIST ) {
printboard();
exit(0);
}
printf( "--------------------->search\n" );
printhistory();
printboard();
for( x=0; x<7; ++x )
for( y=0; y<7; ++y ) {
move( x, y, -1, 0 );
move( x, y, 1, 0 );
move( x, y, 0, -1 );
move( x, y, 0, 1 );
}
}
以上の履歴の記憶とプリントの変更を加えたのが、 solitaire15.c である。
実行結果は次のようになった。
$ solitaire
@ @ @
@ @ @
@ @ @ @ @ @ @
@ @ @ . @ @ @
@ @ @ @ @ @ @
@ @ @
@ @ @
--------------------->search
@ @ @
@ @ @
@ @ @ @ @ @ @
@ @ @ . @ @ @
@ @ @ @ @ @ @
@ @ @
@ @ @
--------------------->search
0 1, 3 1, 0
@ @ @
@ @ @
@ @ @ @ @ @ @
@ . . @ @ @ @
@ @ @ @ @ @ @
@ @ @
@ @ @
--------------------->search
0 1, 3 1, 0
1 2, 1 0, 1
@ @ @
. @ @
@ @ . @ @ @ @
@ . @ @ @ @ @
@ @ @ @ @ @ @
@ @ @
@ @ @
--------------------->search
0 1, 3 1, 0
1 2, 1 0, 1
2 0, 2 1, 0
@ @ @
. @ @
. . @ @ @ @ @
@ . @ @ @ @ @
@ @ @ @ @ @ @
@ @ @
@ @ @
＜後略＞
$
延々と続くのだが、最初のあたりを見る限り、正しいような気がする。
ということで、最後までたどり着いたときにだけそれまでの履歴をプリントすることにしよう。
まず、解にたどり着いたとき呼ばれる関数 foundanswer() を新規に作成し、それまでの履歴と最終的な盤面を確認のためにプリントし、終了するようにした。
void foundanswer( void )
{
printf( "Found answer!\n" );
printhistory();
printboard();
exit(0);
}
これに伴い、関数search()は、foundanswer()を呼ぶようにした。 目的は、解に到達してからの処理をごちゃごちゃ書くことに後でなるだろうから、今のうちに別の関数にしただけのことである。
void search( void )
{
int x, y;
if( restcount == 1 && get(3,3) == EXIST ) {
foundanswer();
}
for( x=0; x<7; ++x )
for( y=0; y<7; ++y ) {
move( x, y, -1, 0 );
move( x, y, 1, 0 );
move( x, y, 0, -1 );
move( x, y, 0, 1 );
}
}
以上の履歴の記憶とプリントの変更を加えたのが、 solitaire16.c である。
実行結果は次のようになった。
$ solitaire
@ @ @
@ @ @
@ @ @ @ @ @ @
@ @ @ . @ @ @
@ @ @ @ @ @ @
@ @ @
@ @ @
Found answer!
0 1, 3 1, 0
1 2, 1 0, 1
2 0, 2 1, 0
3 0, 4 0,-1
4 2, 3 0,-1
5 2, 0 0, 1
6 2, 4 -1, 0
7 2, 6 0,-1
8 3, 2 -1, 0
9 0, 2 1, 0
10 3, 0 0, 1
11 3, 2 -1, 0
12 3, 4 -1, 0
13 0, 4 1, 0
14 3, 6 0,-1
15 3, 4 -1, 0
16 5, 2 -1, 0
17 4, 0 0, 1
18 4, 2 -1, 0
19 1, 2 1, 0
20 3, 2 0, 1
21 4, 4 -1, 0
22 1, 4 1, 0
23 4, 6 0,-1
24 4, 3 0, 1
25 6, 4 -1, 0
26 3, 4 1, 0
27 6, 2 0, 1
28 6, 4 -1, 0
29 4, 5 0,-1
30 5, 3 -1, 0
. . .
. . .
. . . . . . .
. . . @ . . .
. . . . . . .
. . .
. . .
$
履歴はちゃんと取れているようである。 疑わしいと思う人は、手作業で確認して欲しい。
２００１年９月２０日
