[Algo] Eight Puzzle Game 九宫格游戏

Eight Puzzle Game

九宫格游戏，给定最终状态如下，再给出一个初始状态，0代表空位，相邻的格子中的方块可以和0互换位置，求初始状态到最终状态的最小步数。

1 2 3
4 5 6
7 8 0

A*搜索

思路

典型的A*算法应用，我们将棋盘的状态抽象为类似“123456780”的字符串，其中0代表空位，然后每3位代表一行，这时候我们从起始状态开始搜索，搜索中使用一个优先队列存放边缘节点，类似于广度优先搜索，但我们每次取出来的都是函数值最小的节点。这里函数值f(n) = g(n) + h(n)，其中g(n)是到达当前节点的开销，这里也就是步数，而h(n)是指我们对这个节点计算的heuristic值，这题我们有两种可选方法计算heuristic值：

• 判断错位的格子数量，比如拍213456780中，2和1是错位的，所以h值是2

• 判断每个格子中数字和其目标状态的位置的曼哈顿距离之和

这里为了实现简单，我们采取第一种，但实际上第二种heuristic优化的时间可以达到一个数量级之上，因为这里第二种总是dominant第一种。

代码

public class EightPuzzleGame {
    
    public static final String FINAL_STATE = "123456780";
    
    public class Node{
        String state;
        Node parent;// 父亲节点，便于回溯
        int action;// 表示父亲节点到达该节点所做出的action
        int cost;// cost值，这里是步数
        int heuristic; // heuristic值
        public Node(String s, Node parent, int a, int c, int h){
            this.state = s;
            this.parent = parent;
            this.action = a;
            this.cost = c;
            this.heuristic = h;
        }
    }
    
    public int solvePuzzle(String initial){
        HashSet<String> visited = new HashSet<String>();
        int initH = getHeuristic(initial);
        Node root = new Node(initial, null, 0, 0, initH);
        PriorityQueue<Node> pq = new PriorityQueue<Node>(11, new Comparator<Node>(){
            public int compare(Node n1, Node n2){
                return (n1.cost + n1.heuristic) - (n2.cost + n2.heuristic);
            }
        });
        pq.offer(root);
        while(!pq.isEmpty()){
            Node curr = pq.poll();
            if(curr.state.equals(FINAL_STATE)){
                return curr.cost;
            }
            getAllChildrenStates(curr, pq, visited);
        }
        return -1;
    }
    
    public void getAllChildrenStates(Node curr, PriorityQueue<Node> pq, HashSet<String> visited){
        int pos = curr.state.indexOf('0');
        if(pos > 2){
            String child = move(curr.state, 1);//DOWN
            if(!visited.contains(child)){
                int childH = getHeuristic(child);
                pq.offer(new Node(child, curr, 1, curr.cost + 1, childH));
            }
        }
        if(pos < 6){
            String child = move(curr.state, 2);//UP
            if(!visited.contains(child)){
                int childH = getHeuristic(child);
                pq.offer(new Node(child, curr, 2, curr.cost + 1, childH));
            }
        }
        if(pos != 0 && pos != 3 && pos != 6){
            String child = move(curr.state, 3);//RIGHT
            if(!visited.contains(child)){
                int childH = getHeuristic(child);
                pq.offer(new Node(child, curr, 3, curr.cost + 1, childH));
            }
        }
        if(pos != 2 && pos != 5 && pos != 8){
            String child = move(curr.state, 4);//LEFT
            if(!visited.contains(child)){
                int childH = getHeuristic(child);
                pq.offer(new Node(child, curr, 4, curr.cost + 1, childH));
            }
        }
    }
    
    public int getHeuristic(String state){
        int cnt = 0;
        for(int i = 0; i < 9; i++){
            if(state.charAt(i) == FINAL_STATE.charAt(i)){
                cnt++;
            }
        }
        return cnt;
    }
    
    public String move(String original, int direction){
        int pos = original.indexOf('0');
        StringBuilder sb = new StringBuilder(original);
        switch(direction){
            case 1:
                sb.setCharAt(pos, sb.charAt(pos - 3));
                sb.setCharAt(pos - 3, '0');
                break;
            case 2:
                sb.setCharAt(pos, sb.charAt(pos + 3));
                sb.setCharAt(pos + 3, '0');
                break;
            case 3:
                sb.setCharAt(pos, sb.charAt(pos - 1));
                sb.setCharAt(pos - 1, '0');
                break;
            case 4:
                sb.setCharAt(pos, sb.charAt(pos + 1));
                sb.setCharAt(pos + 1, '0');
                break;
        }
        return sb.toString();
    }
}