アルゴリズムc 第1回

バックトラック

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

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

解の発見

• (どれでも構わないので)解を1個だけ求める
• 条件に合う解を1個だけ求める
• 全ての解を求める

8クイーン問題

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

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

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

図: 8Queenの解の例

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

図: 8Queenの探索木

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

図:8方向に調べる

% javac Queen.java RunQueen.java 
% java RunQueen 
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

全解探策

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

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

% javac RunQueenAll.java QueenAll.java
% java RunQueenAll
number= (略)
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

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

(略)

アルゴリズムc 演習

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

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

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

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

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

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

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

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

図: 上下方向の折り返し

図: 反時計回りの回転

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

• 盤を「上下方向に折り返し(折り返しの軸は水平方向)」させた場合の 盤の状態を返すメソッド int[] flip(int[])を作成して下さい。
• 盤を「反時計回りに90°だけ回転」させた場合の 盤の状態を返すメソッド int[] rot(int[])を作成して下さい。
• 解を発見したときに、「その解を折り返したり、回転させたパターン」が 既に記憶した解の中に存在するかどうかを調べ、存在する場合は 新たに記憶しないように void saveAnswer(int[]) メソッドを変更して下さい。

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

1から9までの数字が書かれたカードがN枚与えられたとき、 それらのカードを並べ替えてN桁の素数が作れるかどうかを 答えるプログラムを作成しなさい。 ただし2≦N≦6であり、 また、異なるカードに同一の数字が書かれていることがある。

入力は複数のデータセットからなる。 各データセットは１行で表される。 i番目の行の先頭はカードの枚数を表す自然数N_i であり、 その後ろにカードの表面に書かれている数字 C _i,jが空白文字を1個ずつはさんで表される(1≦j≦N_i )。

入力の終わりは、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までの素数表を作成すればよいでしょう。

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配列の置ける場所に置いてみるのに「繰り返し」を使います。

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)

    }
}