【Python】エイト・クイーン問題を解いてみる

Pythonを使ってエイト・クイーン(8クイーン)問題を解いてみようという試みです。

エイト・クイーン問題を解いてみたい人やバックトラック法を勉強してみたい人は読んでみて下さい。

エイト・クイーン問題とは

エイト・クイーン問題とは、チェスを使ったパズルのことです。

8×8の盤面上に、縦横斜め自由に動くことが出来るクイーンを、お互い取り合うことが出来ない位置に8つ配置します。

そして、出来上がった盤面のパターン数を数えるというものです。

詳しくはwikiを参照してください。

実装方針

バックトラック法(後戻り法)を使用します。

バックトラック法は、全てのパターンを効率良く探索することが出来るアルゴリズムです。

分岐を残したまま最後まで探索を行なっていき、最後まで到着するとひとつ前の分岐に戻って別の枝を探索を行いを繰り返すことで全てのパターンを洗い出すことが出来ます。

早い段階で条件を満たさないことがわかるパターンは、それ以降の駒の組み合わせは見なくて済むので、単に全探索するより早くなります。

実装例

単純に全パターンを数える

実装

一部配置が与えられた時に、残りを埋めて表示する

問題

8 Queens Problem

実装

まとめ

エイト・クイーン問題をPythonで実装しました。

その際使用した手法は、バックトラック法と呼ばれるもので、全てのパターンを洗い出すのに優れた手法になります。

バックトラック法の練習に適した問題になるので、是非一度解いてみてください。