アルゴリズムc 第1回


バックトラック

「すべてのパターンをしらみつぶしに調べあげて、条件を満たすか どうかを確認する」だけが答を得る唯一の方法である問題があります。

そのような問題に対しては、「すべてのパターンを系統的に探索する」 必要があります。やみくもに探索を続けていては駄目で、 「探索の途中で、これ以上先に進んでも解が得られないと 判明した場合には探索を途中で打ち切り、 後戻りして別の選択肢を探索する」方法が必要です。 この方法が「バックトラック(backtracking、後戻り)法」です。

解の発見

複数の解が存在する場合に、 という3つのパターンがあります。

8クイーン問題

チェスのクィーンは、 縦・横・斜めの8方向のどれかに一度に何マスも移動できます。 クィーンが一度に動ける範囲を「利き筋」と言います。

「N×Nのチェス盤にクィーンを N個、互いに利き筋に当たらないように配置する」 問題を、N-Queen問題と言います。

8-Queen問題の解は何通りもありますが、2つ程例を挙げておきます。 Queenが、それぞれの利き筋をはずして置かれていることを確認して下さい。

図: 8Queenの解の例

8-Queenの解を求めるには、8個のQueenを順番に盤の各行に配置してみて、 条件を満たしているかどうかをバックトラックしながら 調べることになります。

(教科書とは異なる)8-Quenのプログラム例を以下に示します。 利き筋の状態を8x8の盤上の数字で表しています。 (利いていない状態の値は0で、n個のQueenの利き筋にあればnとなるように 状態を表現しています。)

図:8方向に調べる



RunQueen.javaの実行例
% javac Queen.java RunQueen.java
% java RunQueen
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

全解探策

解を1つ見付けてもそれで終りにせずに、探索を続けると、すべての 解を求めることができます。

8-Queen問題を全解探索するプログラムは次のように書くことができます。 解を発見しても探索を終了せずに、そのまま探索を続行します。 発見した解は次々と記憶しておきます。



RunQueenAll.javaの実行例
% javac RunQueenAll.java QueenAll.java
% java RunQueenAll
number= (略)
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

Q.......
.....Q..
.......Q
..Q.....
......Q.
...Q....
.Q......
....Q...

(略)


アルゴリズムB 演習


作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを http://nw.tsuda.ac.jp/class/algoC/local/handin/ で必ず確認しておいて下さい。

課題提出〆切は次回の講義が始まる時刻です。

課題1a: 8 Queenを全解探索するプログラム

提出ファイルQueenAll.java
コメント欄:解が全部で何個あるか(回転、折り返しで一致するものでも別物として扱う)
提出先: 「宿題提出Web:アルゴリズムB:課題1a」 http://nw.tsuda.ac.jp/class/algoC/local/handin/up.php?id=kadai1a

RunQueenAll.java を動作させて、解が全部で何個あるかを確かめて下さい。 RunQueenAll.javaを動作させるためにはQueenAll.java, Queen.java も必要になります。

このプログラムは、解を発見したときに、そのまま完全一致でない盤面 (回転や折り返しによって同じ盤面となる盤面)を別物として扱い、 重複して数えることになります。

(Optional) 課題1b: 重複を排除した8 Queenを全解探索するプログラム

提出ファイルQueenAllUniq.java
コメント欄:解が全部で何個あるか(回転、折り返しで一致するものを別に数えない)
提出先: 「宿題提出Web:アルゴリズムB:課題1b」 http://nw.tsuda.ac.jp/class/algoC/local/handin/up.php?id=kadai1b

回転、折り返しで一致する解を別物として扱わない(二重に数えない) ように変更したプログラム QueenAllUniq.java を、 QueenAllクラスをextendsして作成して下さい。

図: 上下方向の折り返し
図: 反時計回りの回転

盤上の各行に置かれたQueenの状態を、変数row(整数の配列)で 表現します。




(Optional) 課題1c: 数字パズル

提出ファイルPrimeTest.java
コメント欄:自分の学生番号の最終1桁の数字を3で割った余りをN とするとき prime_dataN.txtを処理した出力結果。
提出先: 「宿題提出Web:アルゴリズムB:課題1c」 http://nw.tsuda.ac.jp/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
[サンプル入力]
2 3 5
3 2 4 7
4 1 5 6 8
4 2 2 8 9
5 2 2 3 3 9
6 1 1 2 3 4 9
6 1 2 3 4 8 9
6 1 1 2 3 4 8
3 1 1 8
0
[サンプル出力]
1
0
1
0
1
1
0
1
1

[ヒント]

最高で6桁の数を扱いますので、素数判定は「エラストテネスのふるい」で 999999までの素数表を作成すればよいでしょう。


数字の順列(Permutation)を作り出す方法はいろいろありますが、 下の例では「level番目のcardsの数字(cards[level])を、 nums配列の置ける場所に順番に置いてみる」方法で生成しています。 置くべきカードを選ぶのに「再帰呼出し」を、 そのカードの数字をnums配列の置ける場所に置いてみるのに「繰り返し」を使います。