(課題 B_1)〜(課題 B_2) を解け. 各課題について, どのような結果が得られ
たか, 工夫した点, 苦労した点, 感想や課題に関するコメント等を書くこと. 
また, 各課題で作成したプログラムを添付すること. 




8-Queen 問題


  8-Queen とは「8×8 のチェッカーボードに 8 つのクイーンをお互いに取ら
  れないように配置せよ」という問題 (パズル) である.  一般には n×n の
  チェッカーボードを用いる「n-Queen」パズルに拡張できる.

    入力:  自然数 n

    出力: n×n の 2 次元マス目配列上に n 個の「Queen」を配置せよ.  た
          だし, マス目の縦, 横, 斜めいずれの線上にも 2 つの Queen があっ
          てはならない.

  例えば, n=4 の場合には次のような配置が答えとなる. 

          +---+---+---+---+ 
          |   |   | q |   | 
          +---+---+---+---+ 
          | q |   |   |   | 
          +---+---+---+---+ 
          |   |   |   | q | 
          +---+---+---+---+ 
          |   | q |   |   | 
          +---+---+---+---+ 

(課題 B_1) n=4 の場合の解をすべて列挙するプログラムを作成せよ. 

  盤面のクイーンの配置の表現法は色々考えられるが, 例えば, サイズ 4 の 
  1 次元の整数配列を用いて, 各列のクイーンが何行目にあるかを記憶する方
  法が考えられる.

            0   1   2   3
           列  列  列  列
          +---+---+---+---+ 
      0行 |   |   | q |   | 
          +---+---+---+---+ 
      1行 | q |   |   |   | 
          +---+---+---+---+ 
      2行 |   |   |   | q | 
          +---+---+---+---+ 
      3行 |   | q |   |   | 
          +---+---+---+---+ 

    x[] = { 1 , 3 , 0 , 2 } 

  クイーンの配置は, 下記のような 4 重のループによって探索することがで
  きる.

          x[0] = 0, 1, 2, 3 について {
            x[1] = 0, 1, 2, 3 について {
              もし x[1]の配置に問題がなければ {
                x[2] = 0 1, 2, 3 について {
                  もし x[2] の配置に問題がなければ {
                    x[3] = 0, 1, 2, 3 について {
                      もし x[3] の配置に問題がなければ {
                        解が求まったので, クイーンの配置を出力
                      }
                    }
                  }
                }
              }
            }
          }


(課題 B_2) 入力された n に対して n-queen 問題を解くプログラムを作成せ
  よ. 最初の 1 つのみ解を表示し, 後は全ての解の個数を数えて表示するよ
  うにせよ. n = 8, 9, 10, ... と n を増やし, 5分程度の計算時間でどの程
  度大きな n まで解けるか試してみよ. 

  基本的には n が固定の場合と同じだが, 「n 重のループ」は n が決まらな
  いとプログラミングできない.

  これは, 関数の再帰呼び出しにより解決できる. 

  void place_queens(int *x, int n, int k) を, n-queen 問題の「k 〜 n-1
  列クイーンの配置を求める」関数と定義する.

  n-queen 問題を解くためには, 

       place_queens(x, n, 0) 

  を呼び出せば, 0〜n-1 列のクイーンの配列が探索される. 

  さて, place_queens(x, n, k) は, 次のような仕事をする. 

     1) k 列目のクイーンの配置 (x[k]) を求める. 

     2) place_queens(x, n, k+1) を呼び出して, 残りの列 (k+1〜n 列) のクイー
       ンの配置を求める.
 
  終了条件は k==n である. すなわち, place_queens(x, n, k) が呼び出されたときに
  k==n であれば, この時点で 1〜n 列までの配置が求まっているので, 解を
  出力して探索を終了すればよい. 終了条件を忘れると, 「無限再帰呼び出し」
  に陥るので注意. 

  place_queens のおおよその構造は次のようになる. 

     void place_queens(int *x, int n, int k)
     {
        もし k==n なら解を出力して終了. 
        x[k] = 0, 1, 2, …, n-1 について {
           もし x[k] の配置に問題がなければ {
              place_queens(x, n, k+1);
           }
        }
     }

  参考までに, 対称性等を考慮せずに全解を求めた場合, 次のようになる.

       n     解の個数
     ----------------
       1          1
       2          0
       3          0
       4          2
       5         10
       6          4
       7         40
       8         92
       9        352
      10        724
      11      2,680
      12     14,200
      13     73,712
      14    365,596
      15  2,279,184
     ----------------

  対称性を考慮するれば探索空間を小さくすることができる. 例えば, 0 行目
  のクイーンの配置の探索を, 0〜7 ではなくはなく 0〜3 とすれば, 盤面上
  で上下対称なクイーンの配置を除外することができる. 他にも色々な対称性
  を考慮する方法が考えられる. 

  無駄な配置の探索を避けることにより, 計算を高速化することができる. 
  また, データの表現法によってアルゴリズムや計算の効率が大きく変わって
  くるので, データの表現法を考えることは非常に重要で本質的である. さら
  に効率的なデータ構造もあり得るので, 基本が理解できたら他のデータ構造
  も考えてみるとよい.