さて、何も表示されなくなってしまった。 デバッガを起動して、ちょこちょこ追っかけるのも面倒なので、とりあえずどこか適当な場所に、 そこを通過する時点での盤面の状態を印字することにしてみよう。
場所であるが、いままでは８個置けた場合に印字していたが、今度はクイーンを１つ置く度に 印刷することにしよう。ということで、 setqueen() を呼んでクイーンを置く直前に盤面の印字をする printboard() を呼び出そう。
--x とやりながら比較しているが、引数として与えられた x, y はこのプログラム中でいくら 変えても影響ないので、変えながらやっている。x が 0 まで調べ尽くしてどこにも クイーンが ない場合には whileの条件が不成立になって抜ける。QUEEN があった場合には、stat にFALSE を入れて、while ループをすぐに抜けるようにしてある。
これで、クイーンが見つかったら FALSE、クイーンが見つからなかったら TURE になり、 目論んだ通りにプログラムできたと思う。
この左側(←)検査関数 isokleft() を使う場所は、tryqueen() の中であろう。 setqueen() がクイーンを置いてしまう関数なので、その前に調べなければなるまい。 ということで、tryqueen() を次のように変更した。
void tryqueen( int x, int y )
{
int z;
if( ! isokleft( x, y ) ) { /* 効き筋(←)にあるので置けない */
return; /* 何もせずに戻る */
}
if( ! isokleftup( x, y ) ) { /* 効き筋(＼)にあるので置けない */
return; /* 何もせずに戻る */
}
if( ! isokleftdown( x, y ) ) { /* 効き筋(／)にあるので置けない */
return; /* 何もせずに戻る */
}
setqueen( x, y ); /* 置いた */
printboard(); /* ■動作確認のためにプリント */
if( x == 7 ) { /* ８個置き終えた */
プログラム全体は queen11.c である。
早速実行し、原因を探そう。
$ queen Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ＜後略＞ということなんだが、これだけでは実は充分でない。 こちらに、全体の出力 queen11.txt があるので見て欲しい。 なお、8136行もあるので、かなり大変かもしれない。
で、特徴だが、せいぜい７つ位置いたところで、戻ってしまうのである。 要するに、チェックがされすぎているというか、何かチェックに間違いでもあったらしい。
ということでデバッグするのが普通だろうが、頭を切替えて、引数で与えられた座標値(x,y)が
盤面に収まっているかどうかの判定をする関数 ison() を用意してみた。
int ison( int x, int y )
{
if( x<0 || x>=8 )
return FALSE;
if( y<0 || y>=8 )
return FALSE;
return TRUE;
}
x座標、y座標が範囲内かどうかを判定するだけなので極めて簡単である。
盤面上なら TRUE 、 盤外なら FALSE を返す。
他のクイーンの効き筋にあたるかを調べる３つの関数 isokleft(), isokleftup(), isokleftdown() について、盤面上か盤外かの判定には全て ison() を使うように変えてみた。 どの場合も、for(;;) で永久ループを作り、盤面から外れたところで break してforループを 終了するように作った。
int isokleft( int x, int y )
{
int i;
int stat = TRUE;
for(;;) {
--x;
if( ! ison( x, y ) )
break;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
int isokleftup( int x, int y )
{
int i;
int stat = TRUE;
for(;;) {
--x;
--y;
if( ! ison( x, y ) )
break;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
int isokleftdown( int x, int y )
{
int i;
int stat = TRUE;
for(;;) {
--x;
++y;
if( ! ison( x, y ) )
break;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
プログラム全体は queen12.c である。
早速実行だ。
$ queen Answer Q . . . . . . . . . . . . . Q . . . . . Q . . . . . . . . . . Q . Q . . . . . . . . . Q . . . . . . . . . Q . . . . Q . . . . . Answer Q . . . . . . . . . . . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . Q . Q . . . . . . . . . . Q . . . . . Q . . . . . Answer Q . . . . . . . . . . . . Q . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . Q . . . . . Q . . . . . . . . . . Q . . . Answer Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . ＜後略＞全部は長くなってしまうので、 こちらに、全体の出力 queen12.txt があるので見て欲しい。 なんだが正しいような気がする。
一応正しいみたいなのだが、どうしてそうなってしまったのだろうか。 今回変えたのは、盤外になってしまったときの判定部分である。 いままでは、プログラムの中で直接条件判定文で大小比較でやっていたが、 盤上、盤外というのをきっちりと１つの関数として実現した。 ようするに、そういう概念を１つの関数にしたのであり、まあこれが良かったのであろう。 やはり、関数は概念の単位できちんとまとめるとバグも勝手に逃げて行くようだ。
しかし、これでは、まだ正しいかどうかよく分からない。 どりあえず、解の総数を調べることにしよう。 そのためには、解が１つ求まる度に何番目かも印字することにしよう。
そのために、解の総数をカウントするための変数を作ろう。
int answercount;これをカウントアップする場所は、８個置き終えた場合であるので、次のようにしてみた。
if( x == 7 ) { /* ８個置き終えた */
++answercount;
printf( "Answer %d\n", answercount );
printboard();
} else { /* 一つ右側について調べる */
もちろん、最初に answercount を 0 に初期化しなければならない。ということで、
main()の前の最初で 0 にしてみた。もちろん、他の適当なやりかたもあろう。
int main( int argc, char **argv )
{
int y, z;
answercount = 0;
initboard();
for( y=0; y<8; ++y ) {
プログラム全体は queen13.c である。
早速実行だ。
$ queen Answer 1 Q . . . . . . . . . . . . . Q . . . . . Q . . . . . . . . . . Q . Q . . . . . . . . . Q . . . . . . . . . Q . . . . Q . . . . . Answer 2 Q . . . . . . . . . . . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . Q . Q . . . . . . . . . . Q . . . . . Q . . . . . Answer 3 Q . . . . . . . . . . . . Q . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . Q . . . . . Q . . . . . . . . . . Q . . . ＜中略＞ Answer 91 . . Q . . . . . . . . . Q . . . . Q . . . . . . . . . . . . . Q . . . . . Q . . . . . Q . . . . . . . . . . Q . Q . . . . . . . Answer 92 . . Q . . . . . . . . . . Q . . . . . Q . . . . . Q . . . . . . . . . . . . . Q . . . . Q . . . . . . . . . Q . Q . . . . . . . $ということで、解は92個ということがこのプログラムで判明した。 この数は、インターネット上で公開されている多数の８クイーンの解の総数と一致するので、 たぶんこれでOKであろう。何とか、完成である。めでたし、めでたし。
２００１年９月５日