何とか８つ置くことはできたようだが、クイーンが互いに効き筋上にないことの 確認がまったく抜けた状態である。ここは、そのチェックを加えて、ちゃんと調べられる プログラムに仕上げようと思う。
まず、左側に真横に見ていった場合に他のクイーンが無いことを確認してみよう。 つまり、同じ y 座標であって、より左側ということなので、x 座標がクイーンを置こうとしている ところよりも小さいところに他のクイーンがないということである。
文章で説明するより、プログラムの方が簡単であろう。
関数isokleft()は、引数で与えられた位置 (x,y) より左側で同じy座標のマスにクイーンが無いか
どうかを調べる。無い場合にはクイーンが置けるので、TRUE を返し、ダメなときは FALSE を返す。
クイーンを置くことが可能かどうかなので、TURE/FALSE の値はそのように取り決めた。
int isokleft( int x, int y )
{
int i;
int stat = TRUE;
while( --x >= 0 ) {
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
--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; /* 何もせずに戻る */
}
setqueen( x, y ); /* 置いた */
if( x == 7 ) { /* ８個置き終えた */
printf( "Answer\n" );
printboard();
} else { /* 一つ右側について調べる */
for( z=0; z<8; ++z ) {
tryqueen( x+1, z );
}
}
setblank( x, y ); /* 外した */
}
プログラム全体は queen8.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 . ＜後略＞なんだかうまく動いているようだ。同じ水平位置のマスにはクイーンは置かれなくなった。
では、こんどは、斜めを調べてみよう。斜めも２通りあるが、左上方向(＼)を調べてみることにする。 考え方は水平の時と同じだが、左上ということなので、x も y も１つずつ減少させながら調べる ことになる。既に x は --x にて減少させているので、
--y;という行を１行追加するだけで良いのではないかと思う。
そういう考えで 関数isokleftup() を用意した。もちろん、isokleft() をコピーして、１行書き加えて、 関数名を変えただけである。横着であるが、これで充分だろう。
int isokleftup( int x, int y )
{
int i;
int stat = TRUE;
while( --x >= 0 ) {
--y;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
これを呼び出すのは、やはりクイーンを置く前なので、以下のようにした。
void tryqueen( int x, int y )
{
int z;
if( ! isokleft( x, y ) ) { /* 効き筋(←)にあるので置けない */
return; /* 何もせずに戻る */
}
if( ! isokleftup( x, y ) ) { /* 効き筋(＼)にあるので置けない */
return; /* 何もせずに戻る */
}
setqueen( x, y ); /* 置いた */
プログラム全体は queen9.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 . . . ＜後略＞前回は、最初対角線上にクイーンが並んでいたが、それはなくなった。 よくは分からぬが、とにかく左上斜め(＼)の方向にはクイーンはいない。 たぶん、これでプログラムは予定した通り動いているようだが、まだいっぱい出て来てしまう。 これは、左下方向(／)にあるクイーンの確認をしていないからであろう。
ということで、これまた安直に、--y としていた個所を ++y に変えて、 左下方向にクイーンがないかどうか確認する関数 isokleftdown() を作った。 左方向に１つ進む(--x) と、下方向に１つ進む(++y)ことにすれば、左下方向に移動するするから、 これで完璧であろう。プログラムは、こんなに楽にできてしまう。
int isokleftdown( int x, int y )
{
int i;
int stat = TRUE;
while( --x >= 0 ) {
++y;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
これを呼び出して検査するのは同じ場所になるので、以下のような変更で充分であろう。
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 ); /* 置いた */
プログラム全体は queen10.c である。
早速実行だ。
$ queen $しかし、何も表示せず、すぐに終ってしまうようになった。何かおかしい。なぜ？
コンピュータがおかしくなってしまった。いや、プログラム。そんな馬鹿な？
２００１年９月５日