The Problem. 求解8数码问题。用最少的移动次数能使8数码还原.
Best-first search.使用A*算法来解决，我们定义一个Seach Node，它是当前搜索局面的一种状态，记录了从初始到达当前状态的移动次数和上一个状态。初始化时候，当前状态移动次数为0，上一个状态为null，将其放入优先级队列，通过不断的从优先级队列中取出Seach Node去扩展下一级的状态，直到找到目标状态。对于优先级队列中优先级的定义我们可以采用：Hamming priority function 和 Manhattan priority function，第一个表示有多少个块不在目标位置，第二个表示每一个块到他所在目标位置曼哈顿距离之和。
对于解决8数码来说，为了寻求最少步数，那么当前状态移动步数优先级需要考虑，同时选择Hamming或者Manhattan进行启发式的搜索。当目标状态出现时，我们就是使用了最少的步数。怎么证明？
A critical optimization.在搜索的过程中会遇到重复出现的状态，所以我们在进行下一个状态搜索的时候，判断不要将它相邻已经出现的状态加入到优先级队列中。
Game Tree. 搜索是一个博弈树的形式展开，每一个节点对应一个状态，树根是初始状态，在每一步中，A*算法删除优先级对联中priority最小的那个节点，然后进行处理
Detecting infeasible puzzles. 有些初始状态是无法通过移动来得到目标状态的，比如：
但是我们通过交换任意行不为空白的相邻的两个，如果按照这个初始状态来进行搜索，我们就可以得到目标状态。对于可行性的判断，可以根据初始状态和目标状态逆序数的奇偶性来进行判断，在进行移动后，应该奇偶性保持一致。但在这次Assignment中，不要求这么做，而是通过加入两个初始节点，一个是原有的，一个是进行相邻交换一次的，同时进行A*的搜索，如果原有的找到了目标解，那么就是可行，否则另一个找到了可行解，原有的就是不可行状态。
同一个初始状态到目标状态的最小移动次数是存在多解。其他还有IDA*,双向BFS等解法。
一些优化的地方，使用char[][] 比int[][]的空间更小。在进行曼哈顿距离求解的时候，我们可以用空间换时间，预存每个数字的曼哈顿距离，然后直接返回。
8数码是一个NP-Hard问题，没有有效的解存在。
完整的代码如下：
Board.java
public class Board {
private int[][] matrix; // blocks
private int N; // deimension
private int posX, posY; // 0' position
// construct a board from an N-by-N array of blocks
// (where blocks[i][j] = block in row i, column j)
public Board(int[][] blocks) {
N = blocks.length;
matrix = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = blocks[i][j];
if (matrix[i][j] == 0) {
posX = i;
posY = j;
}
}
}
}
// board dimension N
public int dimension() {
return N;
}
// number of blocks out of place
public int hamming() {
int hammingDis = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] == 0) continue;
if (i*N+j+1 != matrix[i][j]) hammingDis++;
}
}
return hammingDis;
}
// sum of Manhattan distances between blocks and goal
public int manhattan() {
int manhattanDis = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] == 0) continue;
int x, y;
if (matrix[i][j] % N == 0) {
x = matrix[i][j] / N - 1;
y = N - 1;
} else {
x = matrix[i][j] / N;
y = matrix[i][j] % N - 1;
}
manhattanDis += Math.abs(i-x) + Math.abs(j-y);
}
}
return manhattanDis;
}
// is this board the goal board?
public boolean isGoal() {
if (posX != N-1 || posY != N-1) return false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] == 0) continue;
if (i*N+j+1 != matrix[i][j]) return false;
}
}
return true;
}
// a board obtained by exchanging two adjacent blocks in the same row
public Board twin() {
int x = -1, y = -1;
int[][] tmpBlock = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j < N-1 && matrix[i][j] != 0 && matrix[i][j+1] != 0) {
x = i;
y = j;
}
tmpBlock[i][j] = matrix[i][j];
}
}
if (x == -1 && y == -1) throw new IllegalArgumentException();
int t = tmpBlock[x][y];
tmpBlock[x][y] = tmpBlock[x][y+1];
tmpBlock[x][y+1] = t;
return new Board(tmpBlock);
}
// does this board equal y?
public boolean equals(Object y) {
if (y == this) return true;
if (y == null) return false;
if (y.getClass() != this.getClass()) return false;
Board that = (Board) y;
if (this.dimension() != that.dimension()) return false;
int sz = this.dimension();
for (int i = 0; i < sz; i++) {
for (int j = 0; j < sz; j++) {
if (this.matrix[i][j] != that.matrix[i][j])
return false;
}
}
return true;
}
// all neighboring boards
public Iterable<Board> neighbors() {
Queue<Board> queue = new Queue<Board>();
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int x = posX + dx[i];
int y = posY + dy[i];
if (x < N && x >= 0 && y < N && y >= 0) {
int tmp = matrix[posX][posY];
matrix[posX][posY] = matrix[x][y];
matrix[x][y] = tmp;
queue.enqueue(new Board(matrix));
tmp = matrix[posX][posY];
matrix[posX][posY] = matrix[x][y];
matrix[x][y] = tmp;
}
}
return queue;
}
// string representation of the board (in the output format specified below)
public String toString() {
StringBuilder s = new StringBuilder();
s.append(N + "\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s.append(String.format("%2d ", matrix[i][j]));
}
s.append("\n");
}
return s.toString();
}
public static void main(String[] args) {
int[][] mat = {
{1, 2, 3},
{4, 6, 0},
{7, 8, 5}
};
//hamming
//manhattan
Board b = new Board(mat);
Board c = b.twin().twin();
StdOut.println(b.equals(c));
StdOut.print(b.toString());
for (Board it : b.neighbors()) {
StdOut.print(it.toString());
StdOut.println("hamming: " + it.hamming());
StdOut.println("manhattan: " + it.manhattan());
}
}
}
Solver.java
public class Solver {
private BoardNode targetBoardNode; // record targetBoardNode
private class BoardNode implements Comparable<BoardNode> {
private Board item;
private BoardNode prev;
private int move;
private boolean isTwin;
// compare by priority
public int compareTo(BoardNode that) {
if (that == null)
throw new NullPointerException("Input argument is null");
int thisPriority = this.move + this.item.manhattan();
int thatPriority = that.move + that.item.manhattan();
if (thisPriority < thatPriority)
return -1;
else if (thisPriority == thatPriority)
return 0;
else
return 1;
}
}
// find a solution to the initial board (using the A* algorithm)
public Solver(Board initial) {
targetBoardNode = null;
// priority queue maintain the minimum elements
MinPQ<BoardNode> minpq = new MinPQ<BoardNode>();
// initial boardnode
BoardNode bn = new BoardNode();
bn.item = initial;
bn.prev = null;
bn.move = 0;
bn.isTwin = false;
minpq.insert(bn);
// initial twin boardnode
BoardNode twinbn = new BoardNode();
twinbn.item = initial.twin();
twinbn.prev = null;
twinbn.move = 0;
twinbn.isTwin = true;
minpq.insert(twinbn);
while (!minpq.isEmpty()) {
BoardNode curbn = minpq.delMin();
if (curbn.item.isGoal()) {
if (curbn.isTwin) targetBoardNode = null;
else targetBoardNode = curbn;
break;
}
for (Board it : curbn.item.neighbors()) {
if (curbn.prev == null || !curbn.prev.item.equals(it)) {
bn = new BoardNode();
bn.item = it;
bn.prev = curbn;
bn.move = curbn.move+1;
if (curbn.isTwin)
bn.isTwin = true;
else
bn.isTwin = false;
minpq.insert(bn);
}
}
}
}
// is the initial board solvable?
public boolean isSolvable() {
return targetBoardNode != null;
}
// min number of moves to solve initial board; -1 if no solution
public int moves() {
if (isSolvable())
return targetBoardNode.move;
else
return -1;
}
// sequence of boards in a shortest solution; null if no solution
public Iterable<Board> solution() {
Stack<Board> stack = new Stack<Board>();
BoardNode tmpbn = targetBoardNode;
while (tmpbn != null) {
stack.push(tmpbn.item);
tmpbn = tmpbn.prev;
}
if (stack.isEmpty())
return null;
else
return stack;
}
// solve a slider puzzle (given below)
public static void main(String[] args) {
// create initial board from file
In in = new In(args[0]);
int N = in.readInt();
int[][] blocks = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
blocks[i][j] = in.readInt();
Board initial = new Board(blocks);
// solve the puzzle
Solver solver = new Solver(initial);
// print solution to standard output
if (!solver.isSolvable())
StdOut.println("No solution possible");
else {
StdOut.println("Minimum number of moves = " + solver.moves());
for (Board board : solver.solution())
StdOut.println(board);
}
}
}