N王妃問題


概要

N王妃問題をバックトラック法および分枝限定法を用いて解く.設計書を作成し,設計書のチェック終了後,コーディングを行う.
8王妃問題の解説は,ここを参照

課題

Nはマクロで指定するものとする.以下の条件でプログラム(ソースファイルはそれぞれ別にすること)を作成せよ.ただし,最低限条件1は行い,できるかぎり条件2も行うこと.条件3,4はオプションとする.

  1. 8王妃問題について,出席番号(No. n)に応じて以下の場合について答えなさい.
    出席番号1~23の学生
     位置(1, n % 8 + 1) にクイーンを置き,2段目以降は左からバックトラックを行う.
    出席番号24~45の学生
     
    位置(1, n % 8 + 1) にクイーンを置き,2段目以降は右からバックトラックを行う.
  2. すべての解(8王妃問題の場合,92個)を求め,表示する.
  3. すべての解から回転して同じになるものや対称なものを除いた解(8王妃問題の場合,12個)のみを求め,表示する.

考察

  1. 条件1において,列挙木のチェック回数(例えば,教科書p99図9.5の最後の括弧内の数字=12など)をプログラム内でカウントし,結果をレポートに書け.
  2. 条件2において,Nを8, 10, 12, 13, 14について実行し,解の個数と列挙木のチェック回数の変化を表にまとめよ.
    実行するときは解の表示に時間がかかるので,リダイレクト( 実行プログラム名 > ファイル名)を用いてファイルへ出力するようにするとよい.

レポート

実験を行ったすべてのアルゴリズムに対する結果,考察,ソースプログラム,設計書をつけること.
万が一,一つもソースプログラムが完成しない場合には,どのような不都合があったのか理由を書くこと.