GDD2011 DevQuiz スライドパズルのすごく素直な反復深化(IDDFS)ソルバーです。

Solver.java

package net.gabuchan.devquiz.slidingpuzzle;

import java.util.Arrays;

public class Solver {
    private static final char[] pieces =
        new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
            'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
    private static final char UP    = 'U';
    private static final char DOWN  = 'D';
    private static final char RIGHT = 'R';
    private static final char LEFT  = 'L';
    private static final char SELF  = '0';
    private static final char WALL  = '=';

    private static final int MAX_LOOP_COUNT = 100000000;
    private static final int DEPTH_LIMIT = 200;

    private int width;
    private int height;
    private char[] start;
    private char[] goal;
    private char[] board;
    private int self;

    private int[] goalIndex;

    private int loop = 0;

    private int depth = 1;
    private int depthStep = 2;

    private String answer = null;
    public String getAnswer() {
        return this.answer;
    }

    public static void main(String[] args) {
        Solver solver = new Solver(args[0]);
        try {
            if (solver.solve()) {
                System.out.println(solver.getAnswer());
            } else {
                System.out.println("None answer");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public Solver(String problem) {
        setup(problem);
    }

    public boolean solve() throws Exception {
        boolean result = false;
        while (depth <= DEPTH_LIMIT) {
            System.out.println("depth = " + depth);
            if (result = solve(0, calcCost())) {
                break;
            } else {
                depth += depthStep;
            }
        }
        return result;
    }

    private boolean solve(int count, int distance) throws Exception {
        if (Arrays.equals(board, goal)) {
            answer = createAnswer();
            System.out.println("Answer: " + answer + ", depth: " + depth + ", loop: " + loop);
            return true;
        }
        if (depth == count++) return false;

        if (depth < count + distance) return false;

        if (loop++ > MAX_LOOP_COUNT) throw new Exception("Over the MAX_LOOP_COUNT");

        char[] nexts = calcNexts();
        for (int i = 0; i < 4; i++) {
            char next = nexts[i];
            if (next == 0) continue;

            int newI = self;
            int oldI = dst(next);
            int oldDistance = distance(oldI, goalIndex[board[oldI]]);
            move(board, next);
            int newDistance = distance(newI, goalIndex[board[newI]]);
            int dd = newDistance - oldDistance;
            pushPath(next);
            if (solve(count, distance + dd)) return true;
            popPath();
            back(board, next);
        }
        return false;
    }

    private boolean isBack(char last, char next) {
        switch (last) {
        case UP:
            return next == DOWN;
        case DOWN:
            return next == UP;
        case RIGHT:
            return next == LEFT;
        case LEFT:
            return next == RIGHT;
        }
        return false;
    }

    private char[] calcNexts() {
        char[] nexts = new char[4];
        char last;
        if (pathIndex == -1) {
            last = 0;
        } else {
            last = lastPath();
        }
        if (self - width >= 0 && board[self - width] != WALL && !isBack(last, UP)) {
            nexts[0] = UP;
        }
        if (self + width < board.length && board[self + width] != WALL && !isBack(last, DOWN)) {
            nexts[1] = DOWN;
        }
        if ((self + 1) % width != 0 &&  board[self + 1] != WALL && !isBack(last, RIGHT)) {
            nexts[2] = RIGHT;
        }
        if (self % width != 0 &&  board[self - 1] != WALL && !isBack(last, LEFT)) {
            nexts[3] = LEFT;
        }
        return nexts;
    }

    private int calcCost() {
        int cost = 0;
        for (int i = 0; i < board.length; i++) {
            if (board[i] == WALL || board[i] == SELF) {
                continue;
            } else {
                cost += distance(i, goalIndex[board[i]]);
            }
        }
        return cost;
    }

    private int distance(int start, int goal) {
        int startX = start % width;
        int startY = start / width;
        int goalX  = goal % width;
        int goalY  = goal / width;
        return Math.abs(goalX - startX) + Math.abs(goalY - startY);
    }

    private void setup(String problem) {
        String[] split = problem.split(",");
        width = Integer.parseInt(split[0]);
        height = Integer.parseInt(split[1]);
        start = split[2].toCharArray();
        board = start.clone();
        self = charArrayIndexOf(board, SELF);
        goal = createGoal();
        goalIndex = new int[256];
        for (int i = 0; i < goal.length; i++) {
            goalIndex[goal[i]] = i;
        }
        depth = calcCost();
    }

    private int dst(char next) {
        switch (next) {
        case UP:
            return self - width;
        case DOWN:
            return self + width;
        case RIGHT:
            return self + 1;
        case LEFT:
            return self - 1;
        }
        return -1;
    }

    private void move(char[] board, char path) {
        int dst = dst(path);
        transpose(board, self, dst);
        self = dst;
    }

    private void back(char[] board, char path) {
        switch (path) {
        case UP:
            move(board, DOWN);
            break;
        case DOWN:
            move(board, UP);
            break;
        case RIGHT:
            move(board, LEFT);
            break;
        case LEFT:
            move(board, RIGHT);
            break;
        }
    }

    private char[] createGoal() {
        char[] goal = new char[start.length];
        for (int i = 0; i < start.length; i++) {
            if (start[i] == WALL) {
                goal[i] = WALL;
            } else {
                if (i == start.length - 1) {
                    goal[i] = SELF;
                } else {
                    goal[i] = pieces[i + 1];
                }
            }
        }
        return goal;
    }

    private String createAnswer() {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i <= pathIndex; i++) {
            sb.append(pathStack[i]);
        }
        return sb.toString();
    }

    private int charArrayIndexOf(char[] cs, char search) {
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == search) return i;
        }
        return -1;
    }

    private void transpose(char[] cs, int src, int dst) {
        char tmp = cs[src];
        cs[src] = cs[dst];
        cs[dst] = tmp;
    }

    private char[] pathStack = new char[DEPTH_LIMIT];
    private int pathIndex = -1;

    private void pushPath(char c) {
        pathStack[++pathIndex] = c;
    }

    private char popPath() {
        return pathStack[pathIndex--];
    }

    private char lastPath() {
        return pathStack[pathIndex];
    }
}