FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »深さ優先探索
このページの記事一覧

【Java】8クイーンを解く[8クイーン問題]  


 もう1つ、再帰の用例としてよく挙げられる「8クイーン(エイト・クイーン)」というパズル(チェス)がある。こちらは「ハノイの塔」と違って、オーソドックスな深さ優先探索という感じで、「バックトラック法」や、マスの襲撃状態を、行や列・斜め方向など効率的に調べる例としても有用なので、よく使われるのだろう。この手法は色々と応用できるので、覚えておいて損はない。

●8クイーン問題 深さ優先探索での解法
public class EightQueensProblem {

public static void main(String[] args) throws Exception {
new EightQueensProblem();
}

static final int N = 8; //ボードのサイズ
int[][] input; //与えられたクイーン(初期配置)

QueensBoard board = new QueensBoard();

public EightQueensProblem() {
input = new int[][]{
{2, 2},
{5, 3},
};// y x (0~N-1)

dfs(0);
}

//深さ優先探索
boolean dfs(int y) {
if (y == N) {
if (board.checkInput(input)) {
System.out.println(board);
return true;
}
return false;
}

for (int x = 0; x < N; x++) {
if (!board.isAttacked(x, y)) {
board.setQueen(x, y, true);
if (dfs(y + 1)) {
return true;
}
board.setQueen(x, y, false);
}
}
return false;
}

//クイーンの配置ボード クラス
class QueensBoard {
boolean[] row = new boolean[N]; //行(─)の襲撃を表す
boolean[] col = new boolean[N]; //列(│)の襲撃を表す
boolean[] pos = new boolean[2 * N - 1]; //斜め(/)の襲撃を表す
boolean[] neg = new boolean[2 * N - 1]; //逆斜め(\)の襲撃を表す
boolean[][] board = new boolean[N][N]; //クイーンの配置を表す

//配置によるフラグのセット
void setQueen(int x, int y, boolean flg) {
row[y] = flg;
col[x] = flg;
pos[y + x] = flg;
neg[y - x + N - 1] = flg;
board[y][x] = flg;
}

//既に襲撃フラグがあるか?
boolean isAttacked(int x, int y) {
if (row[y] || col[x] || pos[y + x] || neg[y - x + N - 1]) {
return true;
}
return false;
}

//与えられたクイーン配置と照合する
boolean checkInput(int[][] input) {
for (int i = 0; i < input.length; i++) {
int y = input[i][0];
int x = input[i][1];
if (!board[y][x]) {
return false;
}
}
return true;
}

//クイーン配置を文字列化
@Override
public String toString() {
final StringBuilder sb = new StringBuilder(N * N + N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(board[i][j] ? "Q" : ".");
}
sb.append("\n");
}
return sb.toString();
}
}
}

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

 今回の例では答えは1つのパターンとしているので、解が見つかったら探索を強制終了している。複数の解を見つけたいなら、「dfs()」の戻値をすべて「false」にしてしまうのも良いだろう。また入力として、初めから配置してあるクイーンを input[][] という配列で設定し、照合するようにしてある。すべての解を見つけるなら照合する必要はない(board.checkInput() を呼び出している部分をコメントアウトなどすれば良い)。

 あとは先に述べた襲撃状態の探索の効率化も考えてみよう。この8クイーンは深さ優先探索でのバックトラックでマスに置けるか調べているわけだが、1つ1つのマスで、既に置かれているクイーンから襲撃を受けているか否かを調べていたら非常に骨が折れる(例えば配置したい位置から8方向にループで他のクイーンから襲撃を受けているかを調べていたら、手間がかかる)。だから、襲撃を表す8方向についてフラグを設定することによって、効率化を図っているというわけだ。フラグを設定している QueensBoard.setQueen() は何を意味しているか図に表してみよう。




 つまりクイーンを置く(x, y) に対応する col[i]、row[i]、pos[i]、neg[i] の配列のインデクス i を図に対応するように計算して、8方向への襲撃状態を表現すれば、各マスに対する他のクイーンからの襲撃も容易に取得できる。上下左右斜めの探索は不要になるというわけだ。

 今回は非常にオーソドックスな手法で書いているので、バックトラック法や更なる高速化などをもっと知りたければ、参考資料も載せておこう。N クイーンとして、高速化してどこまで N を上げられるか?なんてこともよく研究されている。ちなみにこのサンプルコードでは N = 15(ボードサイズが 15)で約 1.5 秒ほど、N = 16 で約 8 秒かかる(Windows10/Intel Core i5 x64 2.9GHz)。ビット演算などで高速化もできるそうなので、余力があったらやってみるのも良いだろう。

(参考)
バックトラック法
Puzzle DE Programming (N Queens Problem)


(関連記事)
【Java】ハノイの塔を解く
【Java】15パズルを解く [A*(A-star)アルゴリズム]


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  深さ優先探索  パズル解法 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop