Eight Puzzle Game

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

1 2 34 5 67 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);//DOWNif(!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);//UPif(!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);//RIGHTif(!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);//LEFTif(!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();    }}