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

2015/11/04 Wed [edit]

　前回、迷路の探索を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();
    }

    //４方向探索用
    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) {      //全てのパネルが揃ったら０
                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];    //各位置にあるパネル番号(番号は１ベース)
        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];    //番号は１ベース
                }
            }
        }

        //空白と数字パネルを入れ替える（スライドする）
        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

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

　推定値は「各パネルが正しい並び(位置)に移動するのに必要な距離の総和＋手数」になっている。指で数字パネルをスライドできる方向は４方向なので、移動コスト(距離)は「マンハッタン距離」になる。その各パネルの距離を合計したものが、全パネルを揃えるのに最低でも必要な手数と考えるわけだ（よって全てが揃ったとき、全距離の総和： md = ０となる）。手数より実行速度を優先したければ、推定値は 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 で自分なりに書き換えたものと言って良い。内容的にはほぼ同じはずだが、手本はあくまでも単純な書き方（すべての機能を一続きに書くような）になっているものが多いので、今回は問題提示部分と探索部分、パズル内での動作をそれぞれにまとめ、なるべく機能分離するようにしてある。こうすると似たような構成のパズルなら、構造体（クラス）やプロパティ、メソッドを少し改造するだけで、再利用できる可能性が増えるからだ。解法を見なくてもそらで書けるようになったら、自分なりのコードも書けるようになる。前回の迷路探索とあまり変わらないのはそのためだ。色々いじってみると良いだろう。