今度は、あの有名な８クイーンの話である。 世の中には、万一８クイーンを知らないままパズルプログラミングを行おうという 人もいるかも知れないので、一応説明をしておこう。
まず、チェス盤だが、８×８のマスが並んだ状態になっている。
┏━┳━┳━┳━┳━┳━┳━┳━┓ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┗━┻━┻━┻━┻━┻━┻━┻━┛これが一部のブラウザではちゃんと表示されないかも知れないが、そういうことは 置いておいて、先に進もう。
さて、クイーンだが、次に示す８方向にあるマスに効きがあって、ここに置かれた 相手の駒は、クイーンに取られる運命、つまり危険にさらされている訳である。
┏━┳━┳━┳━┳━┳━┳━┳━┓ ┃ ┃ ┃●┃ ┃ ┃●┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃●┃ ┃●┃ ┃●┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃●┃●┃●┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃●┃●┃Ｑ┃●┃●┃●┃●┃●┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃●┃●┃●┃ ┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃●┃ ┃●┃ ┃●┃ ┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃●┃ ┃ ┃●┃ ┃ ┃ ┣━╋━╋━╋━╋━╋━╋━╋━┫ ┃ ┃ ┃●┃ ┃ ┃ ┃●┃ ┃ ┗━┻━┻━┻━┻━┻━┻━┻━┛が、ここではチェスという高度なゲームをやろうというのではなく、クイーンがこのように 八方に効きがあるにもかかわらず、互いに効き筋にないように、つまり同じ上下、左右、あるいは 斜めの方向にないように８×８の盤面上に８つのクイーンを置いてしまおうというのが、 ８クイーンの問題である。
時間潰しをしっかりしたい人は、コンピュータなど使わず、手作業で全部しらみ潰しに調べ上げて、 何通りあるかを出せはよいと思うが、ここでは調べ上げるプログラムを作ることにする。
まず、チェス盤を、コンピュータ上でどう表現するかが問題である。 いろいろ考えられるだろうが、ここでは、分かりやすさを第１にし、char型の配列で用意した。
char board[8][8];そして、このチェス盤の各マス、つまり char型の要素に対して、何も無いか、クイーンがあるか の２つの状態を記憶させる必要がある。ここでは、マクロで
#define QUEEN 'Q' #define BLANK '.'と定義することにし、このどちらかの値が 盤面である board の各要素に入ることとした。 Ｃ言語であるので、配列の添字は 0 始まりなので、 x方向(水平方向→)、y方向(垂直方向↓)いずれも 0から7の範囲となる。
実際にこのプログラム上の仮想盤面を初期化(クリア)する関数や、盤面の現在の状態を印字する 部分もとりあえずでっちあげた。
以上をとりあえずまとめたのが queen1.c である。
$ queen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . $
最初は、初期化したばかりの状態で、その後、クイーンを置いたり、取り除いたりしているが、 ちゃんとそのような表示になっているようである。
さて、今のプログラムでは、クイーンを盤面上に置いたり、外したりするのに、 main() の中で直接盤面を意味する配列 board の指定位置に、代入文などという直接的な方法で 処理したが、その部分を関数を用いて書き直してみたのが、 queen2.cである。
動作は queen1.c とまったく同じはずなので、結果は省略する。
２００１年９月４日