８クイーン

　８クイーン(8-queen problem)はチェス盤を使ったパズルの一種である。

　チェスのクイーンは、将棋の飛車と角を合わせたような動きをする。つまり、縦、横、斜めにどこまでも進むことができる。８クイーンは、チェス盤（8X8の升）に８個のクイーンを置き、いずれのクイーンもが互いに経路を邪魔しないように置く方法を全て求めるものである。

　このパズルを解くには総当たり的な方法しかなく、かの天才ガウスが数え間違えたという逸話が残っている。確かに、総当たり的な手法は、天才の頭脳よりはコンピュータに適したものと言える。

　ちなみに、８クイーンの解の総数は92個[*1]であり、対称解を一つとみなすと１２個の独立解がある。８クイーンを解くための標準的な手法はバックトラックであるが、８クイーンは比較的簡単な問題なのでバックトラックを知らなくても解けないことはない[*2]。

　８クイーンはそれ自体は役に立つという種類のものではないが、まとまった分量のアルゴリズムとしては程よい内容なので、新しい言語が開発された場合に８クイーンをその言語で解くということが良く行われる。言わば、プログラム言語の試金石の位置づけである[*3]。

[*1]	「今日の用語」で96個と書いたのは私の記憶誤り。
[*2]	上級プログラマを目指す人は、８クイーンくらいはすらすら解けて欲しいものです。
[*3]	Javaアプレット版をご覧ください。