「すべてのパターンをしらみつぶしに調べあげて、条件を満たすか どうかを確認する」だけが答を得る唯一の方法である問題があります。
そのような問題に対しては、「すべてのパターンを系統的に探索する」 必要があります。やみくもに探索を続けていては駄目で、 「探索の途中で、これ以上先に進んでも解が得られないと 判明した場合には探索を途中で打ち切り、 後戻りして別の選択肢を探索する」方法が必要です。 この方法が「バックトラック(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の実行例 |
% javac Queen.java RunQueen.java |
解を１つ見付けてもそれで終りにせずに、探索を続けると、すべての 解を求めることができます。
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... (略) |
作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。
提出した後は、正しく提出されていることを 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であり、 また、異なるカードに同一の数字が書かれていることがある。
入力は複数のデータセットからなる。 各データセットは１行で表される。 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までの素数表を作成すればよいでしょう。
| PrimeNumber.javaの実装例 |
import java.util.*;
/*
* 「エラストテネスのふるい」による素数判定
* 0以上「コンストラクタで指定した数値」以下の整数の素数判定を行う
*/
public class PrimeNumber {
boolean[] flags;
public PrimeNumber() { this(999999); }
public PrimeNumber(int max) {
flags = new boolean[max+1];
for (int i=0; i<flags.length; i++) flags[i] = true;
flags[0] = flags[1] = false;
for (int i=2; i<=flags.length/2; i++) {
if (!flags[i]) continue;
for(int j=2;j*i<flags.length; j++) flags[j*i]=false;
}
}
boolean isPrime(int x) {
if (x < 0 || x >= flags.length)
throw new IllegalArgumentException("bad number: "+x);
return flags[x];
}
}
|
数字の順列(Permutation)を作り出す方法はいろいろありますが、 下の例では「level番目のcardsの数字(cards[level])を、 nums配列の置ける場所に順番に置いてみる」方法で生成しています。 置くべきカードを選ぶのに「再帰呼出し」を、 そのカードの数字をnums配列の置ける場所に置いてみるのに「繰り返し」を使います。
| PrimeTest.javaの実装例 |
import java.util.*;
public class PrimeTest {
static final int EMPTY = -1;
static PrimeNumber prime;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
prime = new PrimeNumber(999999);
while (true) {
int n = sc.nextInt();
if (n==0) break;
int[] cards = new int[n];
for (int i=0; i<n; i++) cards[i] = sc.nextInt();
System.out.println(check(cards) ? "1":"0");
}
}
static int getInt(int[] p) {
int x = 0;
for (int i=0; i<p.length; i++)
x = x * 10 + p[i];
return x;
}
static boolean check(int[] cards) {
int[] nums =new int[cards.length];
for (int i=0; i<nums.length; i++) nums[i] = EMPTY;
return check(0,cards,nums);
}
static boolean check(int level,int[] cards,int[] nums) {
if (level == cards.length) {
// numsが全部埋まったので素数判定をする
}
// 繰返し:level番目のカードをnumsのまだ埋まっていない場所に置いてみる
// 再帰呼出し:その状態で、次のlevelを試す --> check(level+1,cards,nums)
}
}
|
% java RunQueen