有点难啊。。
85/100，memory测试全挂。。
总结稍后补上
Board.java
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.StdOut;
import java.util.Comparator;
public class Board {
private int n; // board dimension n
private int[] board;
private int zero; //position of zero
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)
n = blocks.length;
board = new int[n*n];
int i = 0;
for (int[] a : blocks){
for (int b:a){
if (b == 0)
zero = i;
board[i++] = b; // Assign value to board.
}
}
}
private int[][] decode (int[] board){
int count = 0;
int[][] result = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
result[i][j] = board[count++];
return result;
}
private int row(int index){
return index / n + 1;
}
private int col(int index){
return index % n + 1;
}
public int dimension(){
return n;
}
public int hamming(){
int count = 0;
for (int i = 0; i < n*n-1; i++){
if (board[i] != i+1)
count++;
}
return count;
}
public int manhattan(){
// sum of Manhattan distances between blocks and goal
int manha = 0;
int diff;
for (int i = 0; i < n*n; i++){
//bad move
if(board[i] == 0) diff = 0;
else{
diff = (Math.abs(row(i) - row(board[i]-1))
+ Math.abs(col(i) - col(board[i]-1)));
}
manha += diff;}
return manha;
}
public boolean isGoal(){
// test the board is the goal board or not
for (int i = 0; i < n*n-1 ; i++)
if (board[i] != i+1)
return false;
return true;
}
public Board twin(){
// return a board that is obtained by exch an pair of blocks;
//**Detecting unsolvable puzzles
int[] twin1d = board.clone();
int[][] twin2d = new int[n][n];
if (twin1d[0] != 0 && twin1d[1] != 0 ){
int temp = twin1d[0];
twin1d[0] = twin1d[1];
twin1d[1] = temp;
}
else {
int temp = twin1d[2];
twin1d[2] = twin1d[3];
twin1d[3] = temp;
}
int c = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
twin2d[i][j] = twin1d[c++];
return new Board(twin2d);
}
public boolean equals(Object y){
// does this board equal y ?
if (y == null) return false;
if (y == this) return true;
if (y.getClass() != this.getClass()) return false;
Board thatB = (Board)y;
if (thatB.dimension() != n) return false;
return Arrays.equals(this.board, thatB.board);
}
private void exch(int a, int b){
int temp = board[a];
board[a] = board[b];
board[b] = temp;
}
public Iterable<Board> neighbors() {
// all neighboring boards
// wtf?
MinPQ<Board> pq = new MinPQ<Board>(new Comparator<Board>() {
public int compare(Board B1, Board B2) {
if (B1.manhattan() < B2.manhattan()) return -1;
if (B1.manhattan() == B2.manhattan()) return 0;
return 1;
}
});
Board temp;
if (row(zero) != n){
temp = new Board(decode(board));
temp.exch(zero,zero+n); //zero moves down;
temp.zero = zero + n;
pq.insert(temp);
}
if (row(zero) != 1){
temp = new Board(decode(board));
temp.exch(zero,zero-n); //zero moves up
temp.zero = zero - n;
pq.insert(temp);
}
if (col(zero) != 1){
temp = new Board(decode(board));
temp.exch(zero,zero-1); //zero moves left;
temp.zero = zero - 1;
pq.insert(temp);
}
if (col(zero) != n){
temp = new Board(decode(board));
temp.exch(zero,zero+1); //zero moves right;
temp.zero = zero + 1;
pq.insert(temp);
}
return pq;
}
public String toString(){
// string representation of this board
StringBuilder sb = new StringBuilder();
sb.append(n + "\n");
for (int i = 0; i < n*n; i++){
sb.append(" " + String.format("%2d", board[i]));
if ( (i+1) % n == 0)
sb.append("\n");
}
return sb.toString();
}
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);
StdOut.println(initial.hamming());
System.out.println("Initial!:");
StdOut.println(initial);
for(Board b : initial.neighbors())
System.out.println(b);
}
}
Solver.java
import java.util.Comparator;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;
public class Solver {
private int moves = -1; // when the board is unsolvable, moves = -1;
private boolean solved = false;
private Stack gameTree;
private searchNode champion;
private boolean isSolvable = false;
private int step;
//twin test;
private MinPQ<searchNode> loserpool = new MinPQ <searchNode> (new Comparator<searchNode>(){
public int compare(searchNode o1, searchNode o2){
if (o1.priority < o2.priority) return -1;
if (o1.priority == o2.priority) return 0;
return 1;
}
});
private class searchNode{
private Board board;
private int moves;
private int priority;
private searchNode prev;
public searchNode(Board board, int moves, searchNode prev){
this.board = board;
this.moves = moves;
this.prev = prev;
this.priority = board.manhattan() + moves;
}
}
public Solver(Board initial){
if(initial == null) throw new IllegalArgumentException();
int TwinPriority = 2*initial.dimension(); // Starter Priority for Twin;
Board twin = initial.twin();
searchNode initialNode = new searchNode(initial, 0, null);
// searchNode twinNode = new searchNode(twin, 0, null); //twin test; with lower priority
searchNode twinNode = new searchNode(twin, TwinPriority, null);
loserpool.insert (initialNode);
loserpool.insert (twinNode);
if(initialNode.board.isGoal())
championship(initialNode);
if(twinNode.board.isGoal())
championship(twinNode);
while(!solved)
solve();
gameTree(initialNode.board);
}
private void solve(){
searchNode node = loserpool.delMin();
step+=1;
for (Board board: node.board.neighbors()){
if (node.prev != null && board.equals(node.prev.board)){
}else{
searchNode child = new searchNode(board, node.moves+1, node);
if(child.board.isGoal()) {
championship(child);
break;
}
loserpool.insert(child);
}
}
}
private void championship(searchNode champion){
solved = true;
this.champion = champion;
this.moves = champion.moves;
}
public boolean isSolvable(){
return isSolvable;
}
public int moves(){
// min number of moves to solve initial board; -1 if unsolvable
return moves;
}
private void SPrinter(){
Stack<Board> S = gameTree;
int move = 0;
if(!isSolvable){
System.out.println("It's unsolvable");
return;
}
while (!S.isEmpty()){
System.out.println("Move: " + move++ );
System.out.println(S.pop());
}
}
private void gameTree(Board initial){
Stack<Board> S = new Stack<Board>();
searchNode node = champion;
//test
while(node.prev != null){
S.push(node.board);
node = node.prev;
}
S.push(node.board);
//test
/*for (int i = 0; i <= champion.moves; i++){
S.push(node.board);
node = node.prev;
}*/
this.gameTree = S;
if(gameTree.peek() == initial)
isSolvable = true;
else this.moves = -1;
}
public Iterable<Board> solution(){
// sequence of boards in a shortest solution; null if unsolvable
if (isSolvable())
return gameTree;
return null;
}
public static void main(String[] args){
// solve a slider puzzle (given below)
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);
if(solver.isSolvable) StdOut.println("Solvable");
if(!solver.isSolvable) StdOut.println("Unsolvable");
System.out.println("Total move: " + solver.moves);
// print solution
System.out.println("---------------");
solver.SPrinter();
System.out.println(solver.isSolvable());
System.out.println("Step: " + solver.step);
}
}
