課題

C

８クイーンの問題

１．バックトラック法とは

　今回はプログラムの仕様の説明の前に、バックトラック法と８クイーンの説明をしておきます。 バックトラック法(backtracking)と言ってもあまり聞いたことがないと思いますが、次のような手法を指します。

　複雑な迷路での曲がり角、分かれ道などのポイントでは、この先どこを通って行けば出口にたどり着くのかを考えることになります。 このようなポイントでは、こちらの道は一度通ったか、通らないかをメモして、まずは一つの道を選んで進んで行くと思います。進んで行くうちに、迷路では行き止まりの箇所が出現してきます。 ここで一つ前のポイントに戻り、この道は通ってはいけないことをメモしてから、次の道に進んで行くことになります。 このメモを頼りに何回も後戻りしては試行錯誤を繰り返しながら出口にたどり着くことになります。

　このように「全てのパターンを系統的に探索して解答を得る手法」をバックトラック法といいます。
　なんだ最初から堅苦しい言葉を使わずに説明しろと言われそうですが、このバックトラック法を利用して、迷路ではないけど８クイーンという問題を解析します。

２．８クイーンとは

　８クイーン(eight queens)とは「8×8のチェス盤上に、8個のクイーンをお互いの利き筋に当たらないように配置する」という問題です。 チェスでのクイーンは、上下左右、斜めに自由に動くことができます。つまり8個のクイーンが互いにどこを動かそうと、取ることも取られることもないように配置するということです。
　この問題は昔からよく知られており、1890年頃に数学者のガウスが研究に関わったと言われています。 但し、解答を得る為のアルゴリズムなどはなく、バックトラック法で試行錯誤の探索で解くしかありません。

　なお今回は８クイーンに限らず、n×nのチェス盤上にn個のクイーンを配置することにします。 n×nのチェス盤が巨大化しても、記述するプログラムは8をnにするだけで大きな変化はありません。