## Tuesday, May 31, 2016

### 8 Puzzle - Princeton Programming Assignment 4

http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html
Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
The problem. The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board (left) to the goal board (right).
```
1  3        1     3        1  2  3        1  2  3        1  2  3
4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
7  8  6        7  8  6        7  8  6        7  8  6        7  8

initial        1 left          2 up          5 left          goal
```
Best-first search. Now, we describe a solution to the problem that illustrates a general artificial intelligence methodology known as the A* search algorithm. We define a search node of the game to be a board, the number of moves made to reach the board, and the previous search node. First, insert the initial search node (the initial board, 0 moves, and a null previous search node) into a priority queue. Then, delete from the priority queue the search node with the minimum priority, and insert onto the priority queue all neighboring search nodes (those that can be reached in one move from the dequeued search node). Repeat this procedure until the search node dequeued corresponds to a goal board. The success of this approach hinges on the choice of priority function for a search node. We consider two priority functions:
• Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the search node. Intuitively, a search node with a small number of blocks in the wrong position is close to the goal, and we prefer a search node that have been reached using a small number of moves.
• Manhattan priority function. The sum of the Manhattan distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the search node.
For example, the Hamming and Manhattan priorities of the initial search node below are 5 and 10, respectively.
```
8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
4     2        4  5  6     ----------------------    ----------------------
7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3

initial          goal         Hamming = 5 + 0          Manhattan = 10 + 0
```
We make a key observation: To solve the puzzle from a given search node on the priority queue, the total number of moves we need to make (including those already made) is at least its priority, using either the Hamming or Manhattan priority function. (For Hamming priority, this is true because each block that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each block must move its Manhattan distance from its goal position. Note that we do not count the blank square when computing the Hamming or Manhattan priorities.) Consequently, when the goal board is dequeued, we have discovered not only a sequence of moves from the initial board to the goal board, but one that makes the fewest number of moves. (Challenge for the mathematically inclined: prove this fact.)
A critical optimization. Best-first search has one annoying feature: search nodes corresponding to the same board are enqueued on the priority queue many times. To reduce unnecessary exploration of useless search nodes, when considering the neighbors of a search node, don't enqueue a neighbor if its board is the same as the board of the previous search node.
```
8  1  3       8  1  3       8  1       8  1  3     8  1  3
4     2       4  2          4  2  3    4     2     4  2  5
7  6  5       7  6  5       7  6  5    7  6  5     7  6

previous    search node    neighbor   neighbor    neighbor
(disallow)

```
Game tree. One way to view the computation is as a game tree, where each search node is a node in the game tree and the children of a node correspond to its neighboring search nodes. The root of the game tree is the initial search node; the internal nodes have already been processed; the leaf nodes are maintained in a priority queue; at each step, the A* algorithm removes the node with the smallest priority from the priority queue and processes it (by adding its children to both the game tree and the priority queue).
Detecting unsolvable puzzles. Not all initial boards can lead to the goal board by a sequence of legal moves, including the two below:
```
1  2  3         1  2  3  4
4  5  6         5  6  7  8
8  7            9 10 11 12
13 15 14
unsolvable
unsolvable

```
To detect such situations, use the fact that boards are divided into two equivalence classes with respect to reachability: (i) those that lead to the goal board and (ii) those that lead to the goal board if we modify the initial board by swapping any pair of blocks (the blank square is not a block). (Difficult challenge for the mathematically inclined: prove this fact.) To apply the fact, run the A* algorithm on two puzzle instances—one with the initial board and one with the initial board modified by swapping a pair of blocks—in lockstep (alternating back and forth between exploring search nodes in each of the two game trees). Exactly one of the two will lead to the goal board.
Board and Solver data types. Organize your program by creating an immutable data type Board with the following API:

```public class Board {
public Board(int[][] blocks)           // construct a board from an N-by-N array of blocks
// (where blocks[i][j] = block in row i, column j)
public int dimension()                 // board dimension N
public int hamming()                   // number of blocks out of place
public int manhattan()                 // sum of Manhattan distances between blocks and goal
public boolean isGoal()                // is this board the goal board?
public Board twin()                    // a board that is obtained by exchanging any pair of blocks
public boolean equals(Object y)        // does this board equal y?
public Iterable<Board> neighbors()     // all neighboring boards
public String toString()               // string representation of this board (in the output format specified below)

public static void main(String[] args) // unit tests (not graded)
}```
Corner cases.  You may assume that the constructor receives an N-by-N array containing the N2 integers between 0 and N2 − 1, where 0 represents the blank square.
Performance requirements.  Your implementation should support all Board methods in time proportional to N2 (or better) in the worst case.
Also, create an immutable data type Solver with the following API:
```public class Solver {
public Solver(Board initial)           // find a solution to the initial board (using the A* algorithm)
public boolean isSolvable()            // is the initial board solvable?
public int moves()                     // min number of moves to solve initial board; -1 if unsolvable
public Iterable<Board> solution()      // sequence of boards in a shortest solution; null if unsolvable
public static void main(String[] args) // solve a slider puzzle (given below)
}
```
To implement the A* algorithm, you must use MinPQ from algs4.jar for the priority queue(s).

Corner cases.  The constructor should throw a java.lang.NullPointerException if passed a null argument.
I'm a bit confused about the purpose of the twin() method. You will use it to determine whether a puzzle is solvable: exactly one of a board and its twin are solvable. A twin is obtained by swapping any pair of blocks (the blank square is not a block). For example, here is a board and several possible twins. Your solver will use only one twin.
```    1  3       3  1       1  3       1  3       1  3       6  3
4  2  5    4  2  5    2  4  5    4  5  2    4  2  5    4  2  5
7  8  6    7  8  6    7  8  6    7  8  6    8  7  6    7  8  1

board      twin       twin       twin       twin       twin
```
How do I reconstruct the solution once I've dequeued the goal search node? Since each search node records the previous search node to get there, you can chase the pointers all the way back to the initial search node (and consider them in reverse order).
Can I terminate the search as soon as a goal search node is enqueued (instead of dequeued)? No, even though it does lead to a correct solution for the slider puzzle problem using the Hamming and Manhattan priority functions, it's not technically the A* algorithm (and will not find the correct solution for other problems and other priority functions).
I noticed that the priorities of the search nodes dequeued from the priority queue never decrease. Is this a property of the A* algorithm? Yes. In the language of the A* algorithm, the Hamming and Manhattan distances (before adding in the number of moves so far) are known as heuristics. If a heuristic is both admissible (never overestimates the number of moves to the goal search node) and consistent (satisfies a certain triangle inequality), then this noticed property is guaranteed. The Hamming and Manhattan heuristics are both admissible and consistent. You may use this noticed property as a debugging clue: if the priority of the search node dequeued from the priority queue decreases, then you know you did something wrong.
Even with the critical optimization, the priority queue may contain two or more search nodes corresponding to the same board. Should I try to eliminate these? In principle, you could do so with a set data type such as SET in algs4.jar or java.util.TreeSet or java.util.HashSet (provided that the Board data type were either Comparable or had a hashCode() method). However, almost all of the benefit from avoiding duplicate boards is already extracted from the critical optimization and the cost of identifying other duplicate boards will be more than the remaining benefit from doing so.
Can I put the logic for detecting whether a puzzle is infeasible in Board instead of Solver? There is a elegant algorithm for determining whether a board is solvable that relies on a parity argument (and occasionally we change our API to require this solution). However, the current API requires you to detect infeasiblity in Solver by using two synchronized A* searches (e.g., using two priority queues).

``````while (!pq.min().board.isGoal()) {
cur = pq.delMin();
for (Board nb : cur.board.neighbors()) {
if (cur.prev != null && nb.equals(cur.prev.board)) continue;
pq.insert(new Node(nb, cur.moves+1, cur));
}
}``````
PQ使用了Manhattan Priority作为Comparator，Node为封装Board的单链表节点，结束后获取最短路径只需取PQ中最小Node，利用prev指针遍历。

• 用char[]存储一个Board的状态比用int[][]好太多，但使用前需要详细测试将char做数字使用与直接用int的区别；
• Board的equals()方法只需比较char[]构成的String即可，早期因图省事直接比较了toString()的返回值（one-liner），造成了很大的性能损失，最后寻找问题来源也费了不少功夫（教训：看似再简单的部分也要在脑袋里多转一转再下手，devil in the details，…，you name it）；
• Solvability: 这篇文章描述的解决方案应为checklist所述方案，但需要脆弱地依赖`toString()`反推Board内容，在本期课程的API设定中已被明确禁止，要求使用两个同步A*的方案解决（最好使用一个PQ），但未来session可能会在两方案对应API设定间切换，所以我都实现了一遍，上面出现的A*代码来自文章所述方案；
• 实现Priority的cache时需要稍多做思考，直觉想到的第一方案是储存在Node中与A*过程配合，而这将使A*代码迅速肿胀，且没有很好地利用更多规律：如checklist所指出，对相邻Board每次重新计算Priority其实也有很多重复工作，我的做法是将cache过程作为Board类一个私有构造函数，构造相邻Priority只需做对应增量操作即可，以最简洁的手段达到了目的。
public class Board {
private static final int SPACE = 0;

private int[][] blocks;

public Board(int[][] blocks) {
this.blocks = copy(blocks);
}

private int[][] copy(int[][] blocks) {
int[][] copy = new int[blocks.length][blocks.length];
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
copy[row][col] = blocks[row][col];

return copy;
}

public int dimension() {
return blocks.length;
}

public int hamming() {
int count = 0;
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (blockIsNotInPlace(row, col)) count++;

return count;
}

private boolean blockIsNotInPlace(int row, int col) {
int block = block(row, col);

return !isSpace(block) && block != goalFor(row, col);
}

private int goalFor(int row, int col) {
return row*dimension() + col + 1;
}

private boolean isSpace(int block) {
return block == SPACE;
}

public int manhattan() {
int sum = 0;
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
sum += calculateDistances(row, col);

return sum;
}

private int calculateDistances(int row, int col) {
int block = block(row, col);

return (isSpace(block)) ? 0 : Math.abs(row - row(block)) + Math.abs(col - col(block));
}

private int block(int row, int col) {
return blocks[row][col];
}

private int row (int block) {
return (block - 1) / dimension();
}

private int col (int block) {
return (block - 1) % dimension();
}

public boolean isGoal() {
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (blockIsInPlace(row, col)) return false;

return true;
}

private boolean blockIsInPlace(int row, int col) {
int block = block(row, col);

return !isSpace(block) && block != goalFor(row, col);
}

public Board twin() {
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length - 1; col++)
if (!isSpace(block(row, col)) && !isSpace(block(row, col + 1)))
return new Board(swap(row, col, row, col + 1));
throw new RuntimeException();
}

private int[][] swap(int row1, int col1, int row2, int col2) {
int[][] copy = copy(blocks);
int tmp = copy[row1][col1];
copy[row1][col1] = copy[row2][col2];
copy[row2][col2] = tmp;

return copy;
}

public boolean equals(Object y) {
if (y==this) return true;
if (y==null || !(y instanceof Board) || ((Board)y).blocks.length != blocks.length) return false;
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (((Board) y).blocks[row][col] != block(row, col)) return false;

return true;
}

public Iterable<Board> neighbors() {

int[] location = spaceLocation();
int spaceRow = location[0];
int spaceCol = location[1];

if (spaceRow > 0)               neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow - 1, spaceCol)));
if (spaceRow < dimension() - 1) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow + 1, spaceCol)));
if (spaceCol > 0)               neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow, spaceCol - 1)));
if (spaceCol < dimension() - 1) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow, spaceCol + 1)));

return neighbors;
}

private int[] spaceLocation() {
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (isSpace(block(row, col))) {
int[] location = new int[2];
location[0] = row;
location[1] = col;

return location;
}
throw new RuntimeException();
}

public String toString() {
StringBuilder str = new StringBuilder();
str.append(dimension() + "\n");
for (int row = 0; row < blocks.length; row++) {
for (int col = 0; col < blocks.length; col++)
str.append(String.format("%2d ", block(row, col)));
str.append("\n");
}

return str.toString();
}
}

public class Solver {
private class Move implements Comparable<Move> {
private Move previous;
private Board board;
private int numMoves = 0;

public Move(Board board) {
this.board = board;
}

public Move(Board board, Move previous) {
this.board = board;
this.previous = previous;
this.numMoves = previous.numMoves + 1;
}

public int compareTo(Move move) {
return (this.board.manhattan() - move.board.manhattan()) + (this.numMoves - move.numMoves);
}
}

private Move lastMove;

public Solver(Board initial) {
MinPQ<Move> moves = new MinPQ<Move>();
moves.insert(new Move(initial));

MinPQ<Move> twinMoves = new MinPQ<Move>();
twinMoves.insert(new Move(initial.twin()));

while(true) {
lastMove = expand(moves);
if (lastMove != null || expand(twinMoves) != null) return;
}
}

private Move expand(MinPQ<Move> moves) {
if(moves.isEmpty()) return null;
Move bestMove = moves.delMin();
if (bestMove.board.isGoal()) return bestMove;
for (Board neighbor : bestMove.board.neighbors()) {
if (bestMove.previous == null || !neighbor.equals(bestMove.previous.board)) {
moves.insert(new Move(neighbor, bestMove));
}
}
return null;
}

public boolean isSolvable() {
return (lastMove != null);
}

public int moves() {
return isSolvable() ? lastMove.numMoves : -1;
}

public Iterable<Board> solution() {
if (!isSolvable()) return null;

Stack<Board> moves = new Stack<Board>();
while(lastMove != null) {
moves.push(lastMove.board);
lastMove = lastMove.previous;
}

return moves;
}
}
http://blog.csdn.net/liuweiran900217/article/details/19818289
Is there an efficient way to solve the 8-puzzle and its generalizations?Finding a shortest solution to an N-by-N slider puzzle isNP-hard,so it's unlikely that an efficient solution exists.

Princeton的《Algorithm》给出了一个使用A*搜索的方式来进行解决。其思路和Coursera中另一个公开课《Generic Game Playing》的搜索树算法很像，大致思路是：对于每一个中间解，计算一个这个解是“正确的”大概期望，按照每一个中间解的期望对搜索树进行排序，优先搜索期望大的解。在本题中，所谓的“期望”就是Hamming priorityManhattan priority。对搜索树排序的方法就是Week4中的优先队列。