女王（クイーン）の配置

  1. 目的

    n*nのボードの上に、n個のクイーンを互いにチェックされないよう、配置する問題です。クイーンは将棋に類似したゲームで、クイーンは縦、横、斜め方向に自由に移動できます。配置されたクイーンの移動可能範囲に、他のクイーンを置かないよう配置することが目的です

  2. 手法


    1. 問題

      ここでの女王はチェスの駒のQueenのことで，Queenは盤上を上下左右対角方向に自由に移動できます(チェスは将棋に似たゲームで，自分の駒の移動範囲にある相手の駒を捕獲でき、King を先に捕獲した方が勝ちになります)。
      　配置問題は N*N の盤上で，N個の Queen を互いに他の女王の移動範囲に入らないよう配置する問題です．この問題は効率的な解法はなく，しらみ潰し的な手法で解を捜しますが，無駄な試行をいかに少なくするかが重要な問題です
      ．

    2. バックトラック

      すべての可能な配置は，各列にn個の位置がありますから，各行に一個づつ配置するとして，nのn乗 の可能な組み合せがあります．これではnの数が多いときは現実的でありません。
      そこで、次のように考えます。(0,0)の位置に Queen を配置した場合，１列には 0と1 行には置くことは出来ず、2 または 3行にのみ配置のみ可能となります．もし、１列の2行に配置しますと，２列に配置可能な列はありません．また、１列３行に配置した場合は，２列の１行に配置可能ですが，３列には配置不能です．したがって，０列の配置に戻り１行に変更します．
      　この場合，１列に配置可能な位置は3行のみです．このようすを，木状に表現すると図のようになります．このように，可能な枝を伸ばし，それ以上先に進めなくなったら，元に戻ってやり直す方式を木状（または樹状）探索といいます．図では、(0列,1行)、(1列,3行)、(2列,0行)、(3列,2行)に配置が進んだ段階を示しています。
      この方法の特徴は、機械的にすべての配置を試行するのでなく、先に進めなくなったら途中から引き返す（バックトラックする）ことで、以後の無駄な検索を省略できる点です。例えば、(0列,1行）、(1列,2行）に配置が進みますと、２列には配置可能な場所がありません。ここで、１列の配置の変更に戻りますから、3列の配置を考える必要がなくなります。


    4. 配置例

      ５人の女王を配置した例を示します。

  3. プロジェクト

    1. アプレット

      awtを利用したアプレットで作成します。

    2. データ構造

      Nを女王の数とします。R[i] に i 列に配置した女王の行番号を保存します。H[N],Up[2*N-1],Dn[2*N-1] は配置可能の検査に用います。
      i 行ｊ 列に新しく女王を配置できるか否かを高速に調べる必要があります。列方向には一人値しか配置しませんから、列方向の検査は不要です。女王を j 行に位置に配置したら，j 行には他の 女王 を配置できません．そこで，配列 H[] を用意し，H[j]=0 ならj 行に配置できないこととします．
      　また，i 行 j 列から右あがり対角方向の座標は i + j の値が同じになります．したがって，Up[ i+j] = 0 のとき (i､ j) には配置しないようにすれば，右対角方向の重複配置を避けることができます．
      同様に左対角方向は i - j が一定になりますが，i - j は負になるので，Dn（i - j + N-1) = 0 (Nは行列のサイズ）のとき配置不可能とします．したがって，配置可能性は H[]、Up[]，Dn[] の配列を検査すれば良いことになります

    3. 再帰呼び出し

      この探索は次のように再帰的に表現できます．ｉ列の探索をQtry(i)とします．Qtry(i) の中で Qtry(i+1)を再帰的に呼び出し、次の行の配置を求めていることに注意してください．try(i)を終了しますと、(これは try(iｰ1) から呼び出されていますから ) try(iｰ1）に戻り iｰ1 列の次の行の配置を試みることになります。 try(iｰ1）に戻る、ことがバックトラックになります。
      　　Qtry(i)
　｛
　　i 列で配置可能な行位置 j を捜す
　　配置可能の場合
　　　i < Nなら Qtry(i+1) で次の列に進む
　　 i 列 j 行 の配置を解除する　
　　i = N-1 なら解が求まったので出力する
　　i 列のすべての可能性を調べたら終了
   （i-1 列の配置に戻る）
｝

    4. レイアウト

      下にレイアウトを示します。中央に配置結果を表示するscrollPaneを作成します。これは、スクロールすることで、改行を含む長い文を表示できます。画面下の「経過表示」をクリックすると、途中の経過を表示できます。startボタンを押すと、配置を探し、見つかれば表示します。すべての解が出尽くすまで、実行は続行します。画面の右下は女王の数と、表示の待ち時間を設定します。stop ボタンを押すと表示が終了すると実行を一時停止できます。
      　経過ボタンを押すと、途中の実行経過を表示します。


    5. プログラム

      1. スレッド

        実行を制御するためTreadを継承した proc クラスを作成し、そこで、Qtry() を実行します。配置が完成するとprint()で結果を表示します。また、「経過表示」がチェックされている場合、１行の配置が成功すると、print()を呼び出します。

      2. print()

        print で配置結果を表示しますが、最後に 経過表示がチェックされていると wait() で待ち状態に入ります。step ボタンが押され、notify() が実行されるとwait()は終了します。また、stopボタン（startボタン）が押された場合も、一時停止します。

    6. 実行

      Applet1 のソースはこちら、proc のソースはこちらにあります。