典型的8 puzzle如下：
image
算法設計參照A搜索算法筒扒，即使不了解A搜索算法忘苛，題目也已經(jīng)將解法解釋的很具體了。
Best-first search：設計參照A* 搜索算法缔莲。定義一個 search node類哥纫，包含board，從初始狀態(tài)到達當前board狀態(tài)的移動權重moves痴奏，和previous search node蛀骇。
- 插入初始的search node，其board設為初始board读拆，moves設為0擅憔，previous search node設置為0
- 將初始化的search node置于MinPQ類型的優(yōu)先級隊列中
- 刪除優(yōu)先級隊列中的min節(jié)點，再將該節(jié)點的鄰居節(jié)點放入優(yōu)先級隊列中檐晕。
- 重復2和3操作直至從優(yōu)先級隊列中刪除的min節(jié)點是目標board
A* 搜索算法的優(yōu)先級判定依據(jù)是f(n) = g(n) + h(n)暑诸，g(n)是從初始節(jié)點到達當前節(jié)點的代價，h(n)是當前節(jié)點到目標節(jié)點的預估代價辟灰。
在本題中search node中的moves就是g(n)个榕，而關于h(n)題目給出了兩種候選：
Hamming priority function: 處于錯誤位置的block的個數(shù)（空白處不算block）
Manhatten priority function: 處于錯誤位置的block距離其各自目標位置的橫向和縱向距離之和
h(n)采用這兩者均可，根據(jù)題目中的圖示芥喇，顯然發(fā)現(xiàn)題目推薦采用manhatten方法西采。
至此優(yōu)先級隊列中的優(yōu)先級判斷依據(jù)就是當前search node的moves+manhatten value
A critical optimization: 上述Best-first search中可能會存在剛出隊列的節(jié)點又被當成其鄰居節(jié)點的鄰居而被放回優(yōu)先級隊列的情況，這種情況會造成很大的性能損失继控。為了阻止這種情況的發(fā)生械馆，可以在Best-first search的第3步“將該節(jié)點的鄰居節(jié)點放入優(yōu)先級隊列”時比較下這個鄰居節(jié)點的board是否與本節(jié)點的board相同。
image
例如此時{{8武通，1霹崎，3}，{4冶忱，0仿畸，2}，{7朗和，6，5}}就不應該放入優(yōu)先級隊列中簿晓。
A second optimization: 建議在search node的構造函數(shù)中計算其manhattan值眶拉，也就是在search node的構造函數(shù)中確定其優(yōu)先級。
Detecting unsolvable puzzles：如果一個board是不可解的憔儿，那么隨便在該board中選擇一對block互換位置忆植，就能將其變?yōu)榭山獾摹榇瞬捎猛瑫r對board和其互換了一對block的twindboard進行求解，如果board先實現(xiàn)目標解朝刊，那么其就是可解的耀里，相反，如果twinboard先實現(xiàn)目標節(jié)拾氓，那么該board就不可解冯挎。
import java.util.ArrayList;
public class Board {
private final int [][]blocks;
private static final int BLANK = 0;
private final int N;
public Board(int[][] blocks) // 創(chuàng)建n*n的棋盤
{
if (blocks == null)
throw new java.lang.IllegalArgumentException("the blocks is null");
N = blocks.length;
this.blocks = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
this.blocks[i][j] = blocks[i][j];
}
}
}
public int dimension() // 棋盤維度n
{
return N; // 返回列數(shù)
}
private int getIndex(int i, int j) // 二維變一維坐標
{
return i * N + j + 1;
}
private int getRow(int value) // 在目標結果中，值所對應的行數(shù)
{
return (value - 1) / N;
}
private int getCol(int value) // 在目標結果中咙鞍，值所對應的列數(shù)
{
return (value -1) % N;
}
public int hamming() // hamming優(yōu)先級=錯的位置個數(shù)+已移動次數(shù)
{
int wrongNum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]位置上的元素放錯
wrongNum++;
return wrongNum;
}
public int manhattan() // manhattan優(yōu)先級=距離目標距離+已移動次數(shù)
{
int wrongNum = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]位置上的元素放錯
{
int righti = getRow(blocks[i][j]); // blocks[i][j]位置上的元素正確的i坐標
int rightj = getCol(blocks[i][j]); // blocks[i][j]位置上的元素正確的j坐標
wrongNum = wrongNum + Math.abs(righti - i) + Math.abs(rightj -j);
}
}
return wrongNum;
}
public boolean isGoal() // 棋盤是否為目標位置
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]位置上的元素放錯
return false;
return true;
}
private int[][] copy() // 拷貝棋盤元素
{
int [][]newblocks = new int[N][N];
for (int i1 = 0; i1 < N; i1++)
for (int j1 = 0; j1 < N; j1++)
newblocks[i1][j1] = this.blocks[i1][j1];
return newblocks;
}
private Board swap(int i1, int j1, int i2, int j2) // 交換兩個棋盤元素位置
{
int [][]newblocks = copy();
int temp = newblocks[i1][j1];
newblocks[i1][j1] = newblocks[i2][j2];
newblocks[i2][j2] = temp;
return new Board(newblocks);
}
public Board twin() // 通過交換任何一對塊而獲得的板房官。
{
int i1 = 0, j1 = 0, i2 = 1, j2 = 1;
if (blocks[i1][j1] == BLANK)
{
i1 = 1;
j1 = 0;
}
if (blocks[i2][j2] == BLANK)
{
i2 = 1;
j2 = 0;
}
Board newBoard = swap(i1, j1, i2, j2);
return newBoard;
}
public boolean equals(Object y) // 判斷兩個棋盤是否相等
{
if (y == null)
return false;
if (y == this)
return true;
if (y.getClass().isInstance(this)) // y和this屬于同一類型
{
Board boardY = (Board) y;
if (boardY.N != this.N)
return false;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (this.blocks[i][j] != boardY.blocks[i][j])
return false;
}
else // y和this不屬于同一類型
{
return false;
}
return true;
}
public Iterable<Board> neighbors() // 所有的鄰居棋盤
{
ArrayList<Board> boards = new ArrayList<>();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (blocks[i][j] == BLANK) // 找到空格位置
{
// 上
if (i > 0)
{
Board upBoard = swap(i, j, i-1, j);
boards.add(upBoard);
}
// 下
if (i < N-1)
{
Board lowBoard = swap(i, j, i+1, j);
boards.add(lowBoard);
}
// 左
if (j > 0)
{
Board leftBoard = swap(i, j, i, j-1);
boards.add(leftBoard);
}
// 右
if (j < N-1)
{
Board rightBoard = swap(i, j, i, j+1);
boards.add(rightBoard);
}
}
}
}
return boards;
}
public String toString() // 此板的字符串表示形式（以下面指定的輸出格式）
{
StringBuilder sBuilder = new StringBuilder();
sBuilder.append(N + "\n");
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
sBuilder.append(blocks[i][j] +"\t");
}
sBuilder.append("\n");
}
String string = sBuilder.toString();
return string;
}
public static void main(String[] args) // unit tests (not graded)
{
int [][]blocks = new int[3][3];
blocks[0][0] = 8;
blocks[0][1] = 1;
blocks[0][2] = 3;
blocks[1][0] = 4;
blocks[1][1] = 0;
blocks[1][2] = 2;
blocks[2][0] = 7;
blocks[2][1] = 6;
blocks[2][2] = 5;
Board board = new Board(blocks);
System.out.println(board.manhattan());
System.out.println(board.toString());
for (Board it : board.neighbors()) {
System.out.println(it.toString());
}
System.out.println(board.twin().toString());
}
}
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Stack;
public class Solver {
private SearchNode currentNode;
private SearchNode currentTwinNode;
private Stack<Board> stackBoard;
private class SearchNode implements Comparable<SearchNode>
{
private final Board board; // 當前棋盤情況
private final int moves; // 當前棋盤移動步數(shù)
private SearchNode preSearcchNode = null; // 當前棋盤前身
private final int priority; // 當前狀態(tài)優(yōu)先級
public SearchNode(Board board, SearchNode pNode)
{
this.board = board;
this.preSearcchNode = pNode;
if (preSearcchNode == null)
moves = 0;
else
moves = preSearcchNode.getMoves() + 1;
priority = board.manhattan() + getMoves();
}
public int compareTo(SearchNode otherNode)
{
return Integer.compare(this.getPriority(), otherNode.getPriority());
}
public int getPriority() {
return priority;
}
public Board getBoard()
{
return board;
}
public int getMoves()
{
return moves;
}
public SearchNode getPreNode()
{
return preSearcchNode;
}
}
public Solver(Board initial) // 找到初始板的解決方案（使用A*算法）
{
if (initial == null)
throw new java.lang.IllegalArgumentException("The intial Board is null");
currentNode = new SearchNode(initial, null); // 初始
MinPQ<SearchNode> minInitialPQ = new MinPQ<>();
minInitialPQ.insert(currentNode);
currentTwinNode = new SearchNode(initial.twin(), null); // 交換兩個位置后的
MinPQ<SearchNode> minTwinNode = new MinPQ<>();
minTwinNode.insert(currentTwinNode);
boolean flag = false;
while (flag != true)
{
// 對原始棋盤進行操作
currentNode = minInitialPQ.delMin(); // 取樹中優(yōu)先級最小的值
if (currentNode.getBoard().isGoal()) // 有解
flag = true;
else
putNeighborsBoardToPQ(currentNode, minInitialPQ); // 將鄰居步驟放入樹中
// 對調整順序的棋盤進行操作
currentTwinNode = minTwinNode.delMin(); // 取樹中優(yōu)先級最小的樹
if (currentTwinNode.getBoard().isGoal())
flag = true;
else
putNeighborsBoardToPQ(currentTwinNode, minTwinNode); // 將鄰居步驟放入樹中
}
}
// 將鄰居情況插入到樹中
private void putNeighborsBoardToPQ(SearchNode currentNode, MinPQ<SearchNode> pMinPQ)
{
Iterable<Board> boards = currentNode.getBoard().neighbors(); // 所有鄰居情況
for (Board neighborsBoard : boards) {
if (currentNode.getPreNode() == null ||
neighborsBoard.equals(currentNode.getPreNode().getBoard()) != true) // 防止回退現(xiàn)象
pMinPQ.insert(new SearchNode(neighborsBoard, currentNode)); // 將鄰居情況插入樹中
}
}
public boolean isSolvable() // 初始板是可解的嗎？
{
return currentNode.getBoard().isGoal();
}
public int moves() // 求解初始板的最小移動數(shù)续滋；如果不可解翰守，則為-1
{
if (isSolvable())
return currentNode.getMoves();
else
return -1;
}
public Iterable<Board> solution() // 最短解中的板序列；若不可解則為空
{
if (isSolvable() != true)
return null;
stackBoard = new Stack<>();
SearchNode nowNode = currentNode;
while (nowNode != null) {
stackBoard.push(nowNode.getBoard());
nowNode = nowNode.getPreNode();
}
return stackBoard;
}
public static void main(String[] args) // solve a slider puzzle (given below)
{
int [][]blocks = new int[3][3];
blocks[0][0] = 8;
blocks[0][1] = 1;
blocks[0][2] = 3;
blocks[1][0] = 4;
blocks[1][1] = 0;
blocks[1][2] = 2;
blocks[2][0] = 7;
blocks[2][1] = 6;
blocks[2][2] = 5;
Board board = new Board(blocks);
Solver solver = new Solver(board);
System.out.println(solver.currentNode.getPreNode() == null);
System.out.println(solver.currentNode.getPreNode());
if (solver.isSolvable() != false) {
System.out.println("this board is can't resolve");
}
Iterable<Board> bIterable = solver.solution();
System.out.println(bIterable.toString());
System.out.println("444");
for (Board it : bIterable) {
System.out.println(it.toString());
}
}
}