「すべてのパターンをしらみつぶしに調べあげて、条件を満たすか どうかを確認する」だけが答を得る唯一の方法である問題があります。
そのような問題に対しては、「すべてのパターンを系統的に探索する」 必要があります。やみくもに探索を続けていては駄目で、 「探索の途中で、これ以上先に進んでも解が得られないと 判明した場合には探索を途中で打ち切り、 後戻りして別の選択肢を探索する」方法が必要です。 この方法が「バックトラック(backtracking、後戻り)法」です。
チェスのクィーンは、 縦・横・斜めの8方向のどれかに一度に何マスも移動できます。 クィーンが一度に動ける範囲を「利き筋」と言います。
「N×Nのチェス盤にクィーンを N個、互いに利き筋に当たらないように配置する」 問題を、N-Queen問題と言います。
8-Queen問題の解は何通りもありますが、2つ程例を挙げておきます。 Queenが、それぞれの利き筋をはずして置かれていることを確認して下さい。
![]() |
![]() |
図: 8Queenの解の例 |
8-Queenの解を求めるには、8個のQueenを順番に盤の各行に配置してみて、 条件を満たしているかどうかをバックトラックしながら 調べることになります。
![]() |
図: 8Queenの探索木 |
(教科書とは異なる)8-Quenのプログラム例を以下に示します。 利き筋の状態を8x8の盤上の数字で表しています。 (利いていない状態の値は0で、n個のQueenの利き筋にあればnとなるように 状態を表現しています。)
![]() |
図:8方向に調べる |
RunQueen.javaの実行例 |
|
解を1つ見付けてもそれで終りにせずに、探索を続けると、すべての 解を求めることができます。
8-Queen問題を全解探索するプログラムは次のように書くことができます。 解を発見しても探索を終了せずに、そのまま探索を続行します。 発見した解は次々と記憶しておきます。
RunQueenAll.javaの実行例 |
|
作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。
提出した後は、正しく提出されていることを http://ynitta.com/class/algoC/local/handin/ で必ず確認しておいて下さい。
課題提出〆切は次回の講義が始まる時刻です。
提出ファイル | QueenAll.java |
---|---|
コメント欄: | 解が全部で何個あるか(回転、折り返しで一致するものでも別物として扱う) |
提出先: | 「宿題提出Web:アルゴリズムB:課題1a」 http://ynitta.com/class/algoC/local/handin/up.php?id=kadai1a |
RunQueenAll.java を動作させて、解が全部で何個あるかを確かめて下さい。 RunQueenAll.javaを動作させるためにはQueenAll.java, Queen.java も必要になります。
このプログラムは、解を発見したときに、そのまま完全一致でない盤面 (回転や折り返しによって同じ盤面となる盤面)を別物として扱い、 重複して数えることになります。
提出ファイル | QueenAllUniq.java |
---|---|
コメント欄: | 解が全部で何個あるか(回転、折り返しで一致するものを別に数えない) |
提出先: | 「宿題提出Web:アルゴリズムB:課題1b」 http://ynitta.com/class/algoC/local/handin/up.php?id=kadai1b |
回転、折り返しで一致する解を別物として扱わない(二重に数えない) ように変更したプログラム QueenAllUniq.java を、 QueenAllクラスをextendsして作成して下さい。
![]() |
図: 上下方向の折り返し |
![]() |
図: 反時計回りの回転 |
盤上の各行に置かれたQueenの状態を、変数row(整数の配列)で 表現します。
提出ファイル | PrimeTest.java |
---|---|
コメント欄: | 自分の学生番号の最終1桁の数字を3で割った余りをN とするとき prime_dataN.txtを処理した出力結果。
|
提出先: | 「宿題提出Web:アルゴリズムB:課題1c」 http://ynitta.com/class/algoC/local/handin/up.php?id=kadai1c |
1から9までの数字が書かれたカードがN枚与えられたとき、 それらのカードを並べ替えてN桁の素数が作れるかどうかを 答えるプログラムを作成しなさい。 ただし2≦N≦6であり、 また、異なるカードに同一の数字が書かれていることがある。
入力は複数のデータセットからなる。 各データセットは1行で表される。 i番目の行の先頭はカードの枚数を表す自然数Ni であり、 その後ろにカードの表面に書かれている数字 C i,jが空白文字を1個ずつはさんで表される(1≦j≦Ni )。
入力の終わりは、1個の数字0である。 入力の終わりを表す行はデータセットではない。
各データセットに対して、素数が生成できる場合は1を、 できない場合は0を含んだ行を出力しなさい。 余分な文字を出力に含んではならない。
[入力形式] N1 C1,1 C1,2 ... C1,N1 ... Nk Ck,1 Ck,2 ... Ck,Nk 0
[サンプル入力] |
|
[サンプル出力] |
|
最高で6桁の数を扱いますので、素数判定は「エラストテネスのふるい」で 999999までの素数表を作成すればよいでしょう。
PrimeNumber.javaの実装例 |
|
数字の順列(Permutation)を作り出す方法はいろいろありますが、 下の例では「level番目のcardsの数字(cards[level])を、 nums配列の置ける場所に順番に置いてみる」方法で生成しています。 置くべきカードを選ぶのに「再帰呼出し」を、 そのカードの数字をnums配列の置ける場所に置いてみるのに「繰り返し」を使います。
PrimeTest.javaの実装例 |
|