SlidingPuzzleSolver.java

import java.io.FileReader;
import java.io.BufferedReader;
import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Arrays;

public class SlidingPuzzleSolver {
    private static String solve(int w, int h, byte[] start, byte[] goal){
        Board.init(w, h, start, goal);

        for(int mode = 0; mode < Board.NUMMODES; mode++){
            MyQueue[] q = new MyQueue[2];
            q[0] = new MyQueue();
            q[1] = new MyQueue();
            Board board;

            Board.setWeight(mode);
            q[0].offer(new Board(start, true));
            q[1].offer(new Board(goal, false));

            try{
                while (true) {
                    for (int i = 0; i < 2; i++) {
                        do {
                            board = q[i].poll();
                        } while (board.obsolete);
                        if (q[1 - i].get(board) != null) {
                            String res;
                            if (i == 0) {
                                res = board.moves() +
                                        reverse(q[1].get(board).moves());
                            } else {
                                res = q[0].get(board).moves() +
                                        reverse(board.moves());
                            }
                            return res;
                        }
                        for (int d = 0; d < 4; d++) {
                            q[i].offer(board.move(d));
                        }
                    }
                }
            } catch(OutOfMemoryError e){
            }
        }
        return "";
    }

    private static String reverse(String str){
        String res = "";
        for(int i = str.length() - 1; i >= 0; i--){
            char c = str.charAt(i);
            if(c == 'L') res += 'R';
            else if(c == 'R') res += 'L';
            else if(c == 'U') res += 'D';
            else if(c == 'D') res += 'U';
        }
        return res;
    }

    public static void main(String[] args){
        if(args.length != 1){
            System.err.println("usage: java SlidingPuzzle inputfile");
            return;
        }

        try {
            int LX, RX, UX, DX, N;
            BufferedReader input = new BufferedReader(new FileReader(args[0]));
            String[] str;

            str = input.readLine().split(" ");
            if(str.length != 4){
                throw new RuntimeException("line 1 must have exactly 4 integers.");
            }
            LX = Integer.parseInt(str[0]);
            RX = Integer.parseInt(str[1]);
            UX = Integer.parseInt(str[2]);
            DX = Integer.parseInt(str[3]);
            str = input.readLine().split(" ");
            if(str.length != 1){
                throw new RuntimeException("line 2 must be a single integer.");
            }
            N = Integer.parseInt(str[0]);

            for(int n = 0; n < N; n++){
                int width, height;
                str = input.readLine().split(",");
                if(str.length != 3){
                    throw new RuntimeException("Incorrect format at line " + (3 + n));
                }
                width = Integer.parseInt(str[0]);
                height = Integer.parseInt(str[1]);
                if(str[2].length() != width * height){
                    throw new RuntimeException("Incorrect format at line " + (3 + n));
                }
                byte[] start = new byte[(width + 1) * (height + 2)];
                byte[] goal = new byte[start.length];
                Arrays.fill(goal, (byte)(width * height));
                Arrays.fill(start, (byte)(width * height));
                for(int i = 0; i < height; i++){
                    for(int j = 0; j < width; j++){
                        goal[(i + 1) * (width + 1) + j + 1] = (byte)((i * width + j + 1) % (width * height));
                    }
                }
                for(int k = 0; k < width * height; k++){
                    char c = str[2].charAt(k);
                    int index = (k / width + 1) * (width + 1) + (k % width + 1);
                    if(c == '=') start[index] = goal[index] = start[0];
                    else if(c >= '0' && c <= '9') start[index] = (byte)(c - '0');
                    else start[index] = (byte)(c - 'A' + 10);
                }
                String res = solve(width, height, start, goal);
                System.out.println(res);
            }
            input.close();
        } catch(Exception e){
            e.printStackTrace();
        }
    }
}

class MyQueue {
    private PriorityQueue<Board> queue = new PriorityQueue<Board>();
    private HashMap<Board, Board> set = new HashMap<Board, Board>();

    boolean offer(Board board){
        if(board == null) return false;
        Board b = get(board);
        if(b != null){
            if(board.compareTo(b) < 0){
                b.obsolete = true;
                set.remove(b);
            } else {
                return false;
            }
        }
        set.put(board, board);
        return queue.offer(board);
    }

    Board poll(){
        return queue.poll();
    }

    Board get(Board board){
        return set.get(board);
    }
}

class Board implements Comparable<Board> {
    static int width, height;
    static int[] dir;
    static char[] letter = {'L', 'U', 'R', 'D'};
    static int[][] dist;
    static int[][] goalPos;
    static int[][] weight;
    static int[] ways;
    static byte wall;
    static byte[][] goals = new byte[2][];

    byte[] panels;
    Board prev;
    int lastMove;
    int space;
    int g;
    int f;
    boolean obsolete = false;
    boolean fromStart;

    Board(byte[] panels, int space, Board prev, int lastMove, boolean fromStart){
        this.panels = panels;
        this.space = space;
        this.prev = prev;
        this.lastMove = lastMove;
        this.fromStart = fromStart;
        g = prev.g + 1;
        f = eval();
    }

    Board(byte[] panels, boolean fromStart){
        this.panels = panels;
        for(int i = 0; i < panels.length; i++){
            if(panels[i] == 0){
                space = i;
                break;
            }
        }
        prev = null;
        lastMove = -1;
        this.fromStart = fromStart;
        g = 0;
        f = eval();
    }

    static void init(int width, int height, byte[] start, byte[] goal){
        Board.width = width;
        Board.height = height;
        wall = (byte)(width * height);
        dir = new int[4];
        dir[0] = -1;
        dir[1] = -(width + 1);
        dir[2] = 1;
        dir[3] = width + 1;
        goalPos = new int[2][width * height + 1];
        for(int i = 0; i < start.length; i++){
            if(start[i] != wall)
                goalPos[1][start[i]] = i;
        }
        for(int i = 1; i < goalPos[0].length; i++){
            int x = (i - 1) % width;
            int y = (i - 1) / width;
            goalPos[0][i] = (y + 1) * (width + 1) + (x + 1);
        }
        goalPos[0][0] = (height + 1) * (width + 1) - 1;
        dist = new int[start.length][start.length];
        setDist(start);
        weight = new int[2][width * height + 1];
        setWeight(mode);
        ways = new int[start.length];
        for(int i = 0; i < ways.length; i++){
            if(start[i] != wall){
                for(int d = 0; d < dir.length; d++){
                    if(start[i + dir[d]] != wall) ways[i]++;
                }
            }
        }
        goals[0] = goal;
        goals[1] = start;
    }

    private static void setDist(byte[] start){
        final int INF = 10000;
        for(int i = 0; i < dist.length; i++){
            Arrays.fill(dist[i], INF);
            for(int j = 0; j < dist[i].length; j++){
                if(j == i) dist[i][j] = 0;
                else if(start[i] == wall || start[j] == wall)
                    dist[i][j] = INF;
            }
        }
        for(int k = 0; k < (width + height) * 4; k++){
            for(int i = 0; i < dist.length; i++){
                for(int j = 0; j < dist[i].length; j++){
                    if(start[i] != wall && start[j] != wall){
                        dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                        dist[i][j] = Math.min(dist[i][j], dist[i][j + width + 1] + 1);
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - width - 1] + 1);
                    }
                }
            }
        }
        for(int i = 0; i < dist.length; i++){
            for(int j = 0; j < dist[i].length; j++){
                if(dist[i][j] == INF) dist[i][j] = 0;
            }
        }
    }

    static final int NUMMODES = 8;
    static int mode = 0;
    static void setWeight(int mode){
        Board.mode = mode;
        weight[0][0] = 0;
        weight[1][0] = 0;
        for(int i = 1; i < weight[0].length; i++){
            int x = (i - 1) % width;
            int y = (i - 1) / width;

            if(mode == 0){ // uniform
                weight[0][i] = 1;
                weight[1][i] = 1;
            } else if(mode == 1){ // step
                weight[0][i] = dist[goalPos[1][0]][i] < (width + height) / 2 ? 1 : 2;
                weight[1][i] = dist[goalPos[0][0]][i] < (width + height) / 2 ? 1 : 2;
            } else if(mode <= 4){ // uniform
                weight[0][i] = mode;
                weight[1][i] = mode;
            } else if(mode == 5){ // vertical
                weight[0][i] = height - y;
                weight[1][i] = 1;
            } else if(mode == 6){ // horizontal
                weight[0][i] = width - x;
                weight[1][i] = 1;
            } else if(mode == 7){ // diagonal
                weight[0][i] = width + height - 1 - (x + y);
                weight[1][i] = 1;
            }
        }
    }

    Board move(int d){
        if(panels[space + dir[d]] == wall || (d ^ 2) == lastMove) return null;
        byte[] nextPanels = Arrays.copyOf(panels, panels.length);
        nextPanels[space] = panels[space + dir[d]];
        nextPanels[space + dir[d]] = 0;
        return new Board(nextPanels, space + dir[d], this, d, fromStart);
    }

    String moves(){
        String res = "";
        Board board = this;
        while(board.lastMove >= 0){
            res = letter[board.lastMove] + res;
            board = board.prev;
        }
        return res;
    }

    private int eval(){ // 評価関数
        int h = 0; // 評価値
        int target = fromStart ? 0 : 1; // 探索の向き
        for(int i = 1; i < panels.length; i++){ // ボードの各パネルについて
            if(panels[i] != wall && panels[i] != 0){ // 文字のパネルなら
                int hi = 0; // i 番目のパネルの評価値
                hi += dist[i][goalPos[target][panels[i]]]; // 壁を考慮した最短距離

                // 隣接するパネルの入れ替えに対するペナルティ
                if(dist[i][goalPos[target][panels[i]]] == 1 && // 目標位置までの距離が 1 で、かつ、
                        goalPos[target][panels[goalPos[target][panels[i]]]] == i){ // 目標位置にあるパネルの目標位置が i ならペナルティ
                    hi += 1;
                    if(ways[i] == 2) hi += 2; // 位置 i から動かせる方向が 2 通りしかない場合は、遠回りが必要なので追加ペナルティ
                }

                // 目標状態において隣接するはずのパネルが隣接していない場合のペナルティ
                if(ways[goalPos[target][panels[i]]] >= 2){ // 何のための条件だったか忘れた
                    int nn = 0; // 目標状態と現在の状態の両方で隣接しているパネルの数だったはずだけど結局全部数えていない
                    for(int d1 = 0; d1 < dir.length; d1++){ // 現在の状態の 4 方向と、
                        if(nn == 0 && panels[i + dir[d1]] != wall){ // 空白と壁を除外して、
                            for(int d2 = 0; d2 < dir.length; d2++){ // 目標状態の 4 方向を総当たり
                                if(panels[i + dir[d1]] == space || panels[i + dir[d1]] == goals[target][goalPos[target][panels[i]] + dir[d2]]){
                                    // 空白が隣接している、または両方の状態で同じパネルが隣接していればカウント
                                    // 今気が付いたけど、 space は空白の位置を表すので正しくは i + dir[d1] == space
                                    nn++;
                                    break;
                                }
                            }
                        }
                    }
                    if(nn == 0){ // 隣接しているパネルがなければペナルティ
                        hi += 1;
                        if(mode > 0) hi += 2; // mode == 0 （重みなし）で解けなかった場合に追加、これもある種の重み付け
                    }
                }

                // 位置 i のパネルは目標位置にあるが、周囲のパネルを揃えるために一度動かさなければならない場合のペナルティ
                // 隣接する位置 j のパネルが目標状態と異なり、 j から動かせる方向が（i を含めて） 2 通りしかないとき、
                // 位置 i のパネルを少なくとも一度動かす必要がある
                if(goalPos[target][panels[i]] == i){ // 位置 i のパネルが目標位置にある場合
                    for(int d = 0; d < dir.length; d++){
                        int j = i + dir[d]; // i に隣接する位置
                        if(ways[j] == 2 && // 位置 j から動かせる方向が 2 通りで、
                                panels[j] != 0 && // j にあるパネルが空白でなく、
                                goalPos[target][0] != j && // 目標状態の空白の位置が j でなく、
                                goalPos[target][panels[j]] != j){ // j にあるパネルの目標位置が j でない場合
                            hi += 2;
                            if(ways[i] == 2) hi += 2; // 位置 i から動かせる方向も 2 通りしかなければ追加ペナルティ
                            break;
                        }
                    }
                }
                h += hi * weight[target][panels[i]]; // 重み付け
            }
        }
        return g + h;
    }

    public int compareTo(Board b){
        if(f > b.f) return 1;
        if(f < b.f) return -1;
        return 0;
    }

    public boolean equals(Object o){
        return java.util.Arrays.equals(((Board)o).panels, panels);
    }

    public int hashCode(){
        int res = 1;
        int m = 37;
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                res += panels[(i + 1) * (width + 1) + (j + 1)];
                res *= m;
            }
        }
        return res;
    }
}