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: --

【Java】ハノイの塔を解く  


 再帰的なアルゴリズムの用例としてよく使われる「ハノイの塔」を解いてみよう。実際試しに「15パズル」と同じ幅優先探索でもやってみたが、円盤の数(N)が12くらいで重くなる(約3秒)。今回の再帰は深さ優先探索というより、解法手順を直接的に操作するような方法となる。こちらの方は円盤20枚ギリギリ行けるようだ(21枚で約4秒)。

●ハノイの塔 再帰的解法
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;

public class TowerOfHanoi {

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

int N = 4; //円盤の数
Hanoi hanoi;
List<String> list = new ArrayList<String>(); //手の記録

public TowerOfHanoi() throws Exception {
hanoi = new Hanoi(N);
list.add("(init) " + hanoi.toString()); //初期位置:[0]

recursive(N, 0, 2); //A → C へ

int i = 0;
for (String e : list) {
System.out.println((i++) + " : " + e);
}
}

//再帰的解法
void recursive(int n, int from, int to) {
if (n > 0) {
int work = 3 - (from + to);
recursive(n - 1, from, work);
hanoi.move(from, to);
String log = String.valueOf((char)('A' + from)) + " -> " + String.valueOf((char)('A' + to));
log += " " + hanoi.toString();
list.add(log); //手の記録
recursive(n - 1, work, to);
}
}

//ハノイの塔 状態保持クラス
class Hanoi {
int n; //円盤の数

@SuppressWarnings("unchecked")
Deque<Integer>[] stack = new Deque[3]; //塔ごとの円盤の状態
{
for (int i = 0; i < 3; i++) {
stack[i] = new ArrayDeque<Integer>();
}
}

//コンストラクタ
public Hanoi(int n) {
this.n = n;

while (n > 0) {
push(0, n--); //初期位置は左(0)に固定
}
}

//円盤を追加(塔:0~2/円盤:1~n)
void push(int to, int no) {
stack[to].addLast(no);
}

//円盤を取り出す(塔:0~2)
int pop(int from) {
return stack[from].removeLast();
}

//円盤の移動(塔:0~2)
void move(int from, int to) {
push(to, pop(from));
}

//塔の円盤(スタック)の状態を文字列にする
@Override
public String toString() {
final StringBuilder sb = new StringBuilder(n * 9);
for (int i = 0; i < 3; i++) {
if (i > 0) {
sb.append(",");
}
if (stack[i].isEmpty()) {
sb.append("[]");
continue;
}

int j = 0;
Iterator<Integer> it = stack[i].iterator();
sb.append("[");
while (it.hasNext()) {
int v = it.next();
if (v == 0) {
break;
}
if (j++ > 0) {
sb.append(",");
}
sb.append(v);
}
sb.append("]");
}
return sb.toString();
}
}
}

0 : (init) [4,3,2,1],[],[]
1 : A -> B [4,3,2],[1],[]
2 : A -> C [4,3],[1],[2]
3 : B -> C [4,3],[],[2,1]
4 : A -> B [4],[3],[2,1]
5 : C -> A [4,1],[3],[2]
6 : C -> B [4,1],[3,2],[]
7 : A -> B [4],[3,2,1],[]
8 : A -> C [],[3,2,1],[4]
9 : B -> C [],[3,2],[4,1]
10 : B -> A [2],[3],[4,1]
11 : C -> A [2,1],[3],[4]
12 : B -> C [2,1],[],[4,3]
13 : A -> B [2],[1],[4,3]
14 : A -> C [],[1],[4,3,2]
15 : B -> C [],[],[4,3,2,1]

 ハノイの塔はスタック構造の用例としても良いので、各塔の円盤の状態を Deque(デック:双方向キュー)で実装(ArrayDeque)してある。Java には Stack というクラスもあるが、Vector クラスの拡張のため、現在では非推奨となっている(Vector を使う場合も、普通は ArrayList などを使う)。Deque(デック)はスタックらしいメソッド:push()pop()peek() なども持っているのだが、前方から追加・削除を行うので、パズルの状態を正確に再現するため、クラス内で後方から追加・削除できるメソッドに変えてある。スタックは通常の配列でも簡単に実装できるので、自分の好きなように修正しても良いだろう。また、toString() メソッドで状態を文字列に変換できるようにしてあるが、ここを修正すれば表示形式も変更できる。手の記録は再帰部分で List に追加しているだけだ。

 塔の円盤の状態を保持するクラスや手の記録をする部分を付け加えているので長く感じるが、パズルを解く中核は以下の部分になる。

void recursive(int n, int from, int to) {
if (n > 0) {
int work = 3 - (from + to);
recursive(n - 1, from, work);
hanoi.move(from, to);
recursive(n - 1, work, to);
}
}

 この再帰が何をしているのか、簡単に図にしてみよう。多少仮想的な概念を説明しているので、実際の手ではないので注意して欲しい。

 まずは円盤2枚で考えてみよう。

 実は最短の手で移動するにはパターンがあって、移動元と移動先以外の1本の塔を作業用としたとき、「移動元→作業用、移動元→移動先、作業用→移動先」(A→B, A→C, B→C)と移動すると良いのである。

 次に円盤3枚で考えてみよう。ただしここでは本当に3枚で移動するのではなく、一番下の円盤と、それ以外の円盤をまとめたものを移動すると考えてみよう。まとめた部分を▲で囲むと以下のような感じになる。


 では円盤4枚(n枚)では?。動きとしては2枚にしているようなものなのでもちろん変わらない。


 つまりよく考えれば、円盤の枚数を n 枚とするとき、その上にある ▲(n - 1) 枚も同じように「A→B」へ動かし、一番下の n を移動先へ、そしてまた ▲(n - 1) 枚を「B→C」へ移動すれば良いということがわかる。それが4枚のとき上の3枚を、3枚のとき上の2枚を・・・と入れ子になっているというわけだ。よって再帰が適用できる。もちろん1枚のときは、ただ移動先へ直接移動させれば良い。

 それと、これまでの図にも色分けされているのだが、改めて移動元と移動先、作業用の関係がどうなっているか考えてみよう。色だけを見てみれば、パターン化されているのがわかる。


 それら移動元を「from」、移動先を「to」、作業用を「work」とすると以下のように書けることがわかる。これで再帰部分が完成だ。見比べてみよう。


void recursive(int n, int from, int to) {
if (n > 0) {
int work = 3 - (from + to);
recursive(n - 1, from, work);
hanoi.move(from, to);
recursive(n - 1, work, to);
}
}

 ここでは操作手順での解法しかしてないので、数学的な証明やまだ疑問に思うことがあるなら参考ページを載せておこう。ハノイの塔は色々研究されているので、ググればもっと出てくるだろう。

(参考)
ハノイの塔に挑戦
2.2 ハノイの塔

 余談だが、参考資料や Wikipedia にも載っているが、最短手数は2n-1 となり、円盤が 64 枚のとき、18446744073709551615 手となる。1回の移動に1秒かかるとすれば、約 5845 億年かかるそうだ(笑)。そのとき世界は崩壊し終焉を迎えるというおとぎ話もある。


(関連記事)
【Java】8クイーンを解く[8クイーン問題]
【Java】15パズルを解く [A*(A-star)アルゴリズム]


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  パズル解法 
tb: 0   cm: --

【Java】15パズルを解く [A*(A-star)アルゴリズム]  


 前回、迷路の探索をA*(A-star, エースター)アルゴリズムでやったので、ついでに「15パズル」を解いてみよう。

15パズル

 パズル自体の解き方は言わば「全パターン総当り方式(全探索)」である。ただ、3x3 サイズの 8パズルでなら、全探索でも問題なく解けるのだが、4x4 サイズの 15パズルになると、単純な全探索では、答えの手数が大きいときにフリーズしたような状態になってしまい、いずれキューのバッファオーバーフローでプログラムが停止してしまう。なので、A*(A-star) のような枝刈りアルゴリズムが必須になる。
 
 A*(A-star, エースター)アルゴリズムの解説はWikipediaなどを見るか、前回の「A*(A-star, エースター)アルゴリズムで迷路を探索する」で簡単な考え方を解説している。「推定値」の使い方だけ覚えれば十分だろう。

●15パズル解法 [A*(A-star)アルゴリズム]
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.HashSet;

public class FifteenPuzzleAstar {

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

//4方向探索用
static final int[] dx = { 0, 1, 0, -1};
static final int[] dy = {-1, 0, 1, 0};
static final char[] dir = {'u', 'r', 'd', 'l'};

static final int N = 4; //盤サイズ
static final int NN = N * N; //パネル総数

//各パネルのマンハッタン距離のテーブル
static final int[][] MDTable = new int[NN][NN];
static {
for (int i = 0; i < NN; i++) {
for (int j = 0; j < NN; j++) {
MDTable[i][j] = getManhattanDistance(i % N, i / N, j % N, j / N);
}
}
}

//マンハッタン距離を求める
static int getManhattanDistance(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

public FifteenPuzzleAstar() {

int[][] board = new int[][]{ //初期の盤の状態
{ 1, 7, 2, 4},
{ 6, 0,14, 3},
{13,10,11, 8},
{ 5, 9,15,12},
}; //rrdllldruuurdllddrurrd 22(手)

String ans = astar(board);
System.out.println(ans);
System.out.println(ans.length());
}

//A*(A-star)で15パズルを解く
String astar(int[][] board) {
Set<String> done = new HashSet<String>(); //既出パターンチェック用
Queue<Puzzle> q = new PriorityQueue<Puzzle>();

Puzzle p = new Puzzle();
p.setBoard(board); //初期の盤の状態をセットする
p.estimate = p.md; //推定値
q.add(p);
done.add(p.toString());

while (!q.isEmpty()) {
p = q.poll();
if (p.md == 0) { //全てのパネルが揃ったら0
return p.path; //空白の移動経路
}

done.add(p.toString());
int sx = p.space % N; //空白の位置
int sy = p.space / N;

for (int i = 0; i < dx.length; i++) {
int nx = sx + dx[i]; //空白の移動位置
int ny = sy + dy[i];
if (nx < 0 || N <= nx || ny < 0 || N <= ny) { //範囲外
continue;
}

Puzzle p2 = p.clone();
p2.changeSpace(nx, ny); //空白と数字パネルを入れ替える(スライドする)
if (!done.contains(p2.toString())) { //既出パターンチェック
p2.cost++; //手数
p2.estimate = p2.md + p2.cost; //推定値
//p2.estimate = p2.md; //推定値(実行速度を優先したいときはこっちにする)
p2.path += dir[i]; //空白の移動経路(移動方向の記録)
q.add(p2);
}
}
}

return "unsolvable"; //完成できなかったとき
}

//パズルの状態を保存する構造体(クラス)
class Puzzle implements Cloneable, Comparable<Puzzle> {
int[] panel = new int[NN]; //各位置にあるパネル番号(番号は1ベース)
int space; //空白のインデクス
int md; //全パネルのマンハッタン距離の合計
int cost; //手数
int estimate; //推定値
String path = ""; //空白の移動経路(移動方向の記録)

//盤の並びをセットする
void setBoard(int[][] board) {
int p = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 0) { //空白
panel[p] = NN; //空白は最大値にする
space = p; //空白のインデクス
} else {
panel[p] = board[i][j];
}
p++;
}
}

calcMD(); //全パネルのマンハッタン距離の合計を求める
}

//全パネルのマンハッタン距離の合計を求める
void calcMD() {
md = 0;
for (int i = 0; i < NN; i++) {
if (panel[i] != NN) { //空白は除外する
md += MDTable[i][panel[i] - 1]; //番号は1ベース
}
}
}

//空白と数字パネルを入れ替える(スライドする)
void changeSpace(int x, int y) {
int index = x + y * N; //インデクスに変換
md += MDTable[space][panel[index] - 1]; //全パネル距離合計から移動後の数字パネル距離を足す(差分計算)
md -= MDTable[index][panel[index] - 1]; //全パネル距離合計から現在の数字パネル距離を引く
panel[space] = panel[index]; //数字パネルを交換(スライド)
panel[index] = NN; //空白を交換
space = index; //空白のインデクス更新
}

//比較関数
@Override
public int compareTo(Puzzle o) {
return this.estimate - o.estimate; //推定値で小さい順
}

//盤の状態を文字列にする(既出パターンのキーとしても利用)
@Override
public String toString() {
StringBuilder sb = new StringBuilder(NN * 3);
for (int i = 0; i < NN; i++) {
if (i > 0) {
if (i % N == 0) {
sb.append("\n");
} else {
sb.append(" ");
}
}
sb.append(panel[i]);
}
return sb.toString();
}

//盤の状態を複製する
@Override
public Puzzle clone() {
try {
Puzzle obj = (Puzzle)super.clone();
obj.panel = this.panel.clone();
return obj;
} catch (CloneNotSupportedException e) {
throw new RuntimeException();
}
}
}
}

rrdllldruuurdllddrurrd

 答えとなる移動経路の文字列は空白の移動のものなので、人の指で数字パネルを動かす方向(スライド)は逆となる(空白が右に動くということは、数字パネルは左に動く)。スライド方向で表示したいときは上下左右を反転するメソッドでも付け加えると良いだろう。

 推定値は「各パネルが正しい並び(位置)に移動するのに必要な距離の総和+手数」になっている。指で数字パネルをスライドできる方向は4方向なので、移動コスト(距離)は「マンハッタン距離」になる。その各パネルの距離を合計したものが、全パネルを揃えるのに最低でも必要な手数と考えるわけだ(よって全てが揃ったとき、全距離の総和: md = 0となる)。手数より実行速度を優先したければ、推定値は md だけでも良い。

 グローバル変数の静的ブロックで「MDTable」(ManhattanDistanceTable)というものを作っているが、15 パズルはパネルが 16 個固定なので、各パネルの距離を一覧表として作成してあるだけである。リアルタイムで計算しても良いが、どうせ同じ答えになるのなら、このように配列化しておくと実行速度が速い。推定値の比較はパズルの状態を保存する構造体(Puzzle)に Comparable インタフェースを噛ませて、PriorityQueueで比較している。探索の優先順位などを変えたければここをいじるのが一番手っ取り早いだろう。

 空白と数字パネルを入れ替えるメソッド「Puzzle.changeSpace()」では、数字パネルの移動による md (ManhattanDistance) の差分を計算しているが、わかりにくければ、空白と数字パネルを入れ替え、空白のインデクス更新した後に、全パネルのマンハッタン距離の合計を求めるメソッド「Puzzle.calcMD()」を呼び出す方法でも良い。実行速度を優先したければ、差分の計算のままが良いだろう。

 既出パターン(パネルの並び方)の検出に Set(重複要素のないコレクション) を使っているが、Map(連想配列)でも良い。他の言語に移植するときは連想配列の方が互換性が高いかも知れない(今回は存在チェックだけで値を必要としないので、Set にした)。また、既出パターンのキーをデバッグ用の全パネルの数字を表示するメソッド「Puzzle.toString()」(System.out.println(p) などで並びを表示できる)の文字列を、手抜き(笑)でそのまま使ってしまっているが、パネルは15個(16)なので、16進数にするなど別の文字列に置き換えても良いだろう。少しだけメモリ節約になるかも知れない。


 また、今回の元ネタは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」という本に載っている C++ での解法だ。それを Java で自分なりに書き換えたものと言って良い。内容的にはほぼ同じはずだが、手本はあくまでも単純な書き方(すべての機能を一続きに書くような)になっているものが多いので、今回は問題提示部分と探索部分、パズル内での動作をそれぞれにまとめ、なるべく機能分離するようにしてある。こうすると似たような構成のパズルなら、構造体(クラス)やプロパティ、メソッドを少し改造するだけで、再利用できる可能性が増えるからだ。解法を見なくてもそらで書けるようになったら、自分なりのコードも書けるようになる。前回の迷路探索とあまり変わらないのはそのためだ。色々いじってみると良いだろう。


(関連記事)
【Java】A*(A-star, エースター)アルゴリズムで迷路を探索する
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)
【Java】ハノイの塔を解く
【Java】8クイーンを解く[8クイーン問題]


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  最短経路  幅優先探索  パズル解法 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop