ヽ｜∵｜ゝ(Fantom) の 開発blog？

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();
        }
    }
}

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();
        }
    }
}

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);
    }
}

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);
    }
}

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();
            }
        }
    }
}