nクイーン問題解答プログラム

nクイーン問題というのは歴史の古いパズル｢エイトクイーン｣を拡張したものです。詳しくはパズル紹介のページでどうぞ。

このプログラムは、nクイーン問題の全解を求めるプログラムです。
どういうふうに解を求めているかというと･･････

1. 1からnまでの数字を並べる順列を生成する。
   i番目の数字をjとすると、座標(i,j)にクイーンが置かれていることを意味する。

これで縦・横にクイーンの重複がない配置を得ることができます。そして次に、

2. 斜めに重複していないかチェックする。

これで全ての条件をクリアする解に絞ることができます。
ただし、全ての順列を一旦生成してからふるいにかける方式を取ると、nが大きいときに無駄な探索の数が膨大になるので、再帰的に順列を生成する過程で2.のチェックを逐次行うことで探索の効率化を図っています。

●スクリーンショット(クリックすると大きな画像が出ます)

      

プログラムとソースのダウンロード

• このプログラムは現在のところGUIプログラムではありません。コマンドプロンプトかUNIXなどのコンソールで使用してください。
• ソースはC++で書かれています。
  GCC、Borland C++ Compiler、Visual C++で正常にコンパイルできます。