1 import edu.princeton.cs.algs4.In;  2 import edu.princeton.cs.algs4.StdOut;  3   4 import java.util.Stack;  5   6   7 public class Board {  8     private int ngrid;  9     private char[] board; 10     private int hammingCache; 11     private int manhattanCache; 12  13     public Board(int[][] blocks) { 14         ngrid = blocks.length; 15  16         if (ngrid < 2) { 17             throw new NullPointerException(); 18         } 19  20         board = new char[ngrid * ngrid]; 21         hammingCache = 0; 22         manhattanCache = 0; 23  24         for (int i = 0; i < ngrid; i++) { 25             for (int j = 0; j < ngrid; j++) { 26                 int currentValue =http://www.mamicode.com/ blocks[i][j]; 27                 board[(i * ngrid) + j] = (char) currentValue; 28  29                 if (currentValue != 0) { 30                     if (currentValue != ((i * ngrid) + j + 1)) { 31                         hammingCache++; 32                     } 33  34                     int col = (currentValue - 1) % ngrid; 35                     int row = (currentValue - col - 1) / ngrid; 36                     // StdOut.println("v:"+currentValue+"r:"+row+"c:"+col); 37                     manhattanCache += (((col > j) ? (col - j) : (j - col)) + 38                     ((row > i) ? (row - i) : (i - row))); 39                 } 40             } 41         } 42     } 43  44     public int dimension() // board dimension n 45      { 46         return ngrid; 47     } 48  49     public int hamming() // number of blocks out of place 50      { 51         return hammingCache; 52     } 53  54     public int manhattan() // sum of Manhattan distances between blocks and goal 55      { 56         return manhattanCache; 57     } 58  59     public boolean isGoal() // is this board the goal board? 60      { 61         return hammingCache == 0; 62     } 63  64     public Board twin() // a board that is obtained by exchanging any pair of blocks 65      { 66         int[][] twin = new int[ngrid][ngrid]; 67  68         for (int i = 0; i < ngrid; i++) { 69             for (int j = 0; j < ngrid; j++) { 70                 twin[i][j] = (int) board[(i * ngrid) + j]; 71             } 72         } 73  74         if ((twin[0][0] == 0) || (twin[0][1] == 0)) { 75             swap(twin, 1, 0, 1, 1); 76         } else { 77             swap(twin, 0, 0, 0, 1); 78         } 79  80         return new Board(twin); 81     } 82  83     public boolean equals(Object y) // does this board equal y? 84      { 85         if (y == this) { 86             return true; 87         } 88  89         if (y == null) { 90             return false; 91         } 92  93         if (y.getClass() != this.getClass()) { 94             return false; 95         } 96  97         Board that = (Board) y; 98         if (that.dimension() != ngrid) return false; 99         for (int i = 0; i < (ngrid * ngrid); i++) {100             if (this.board[i] != that.board[i]) {101                 return false;102             }103         }104 105         return true;106     }107 108     public Iterable<Board> neighbors() // all neighboring boards109      {110         int blankRow = 0;111         int blankCol = 0;112         Stack<Board> neighbours = new Stack<Board>();113 114         int[][] clone = new int[ngrid][ngrid];115 116         for (int i = 0; i < ngrid; i++) {117             for (int j = 0; j < ngrid; j++) {118                 clone[i][j] = (int) board[(i * ngrid) + j];119 120                 if (clone[i][j] == 0) {121                     blankRow = i;122                     blankCol = j;123                 }124             }125         }126 127         if (blankCol != 0) {128             swap(clone, blankRow, blankCol - 1, blankRow, blankCol);129             neighbours.push(new Board(clone));130             swap(clone, blankRow, blankCol - 1, blankRow, blankCol);131         }132 133         if (blankCol != (ngrid - 1)) {134             swap(clone, blankRow, blankCol + 1, blankRow, blankCol);135             neighbours.push(new Board(clone));136             swap(clone, blankRow, blankCol + 1, blankRow, blankCol);137         }138 139         if (blankRow != 0) {140             swap(clone, blankRow - 1, blankCol, blankRow, blankCol);141             neighbours.push(new Board(clone));142             swap(clone, blankRow - 1, blankCol, blankRow, blankCol);143         }144 145         if (blankRow != (ngrid - 1)) {146             swap(clone, blankRow + 1, blankCol, blankRow, blankCol);147             neighbours.push(new Board(clone));148         }149 150         return neighbours;151     }152 153     private void swap(int[][] array, int i, int j, int a, int b) {154         int temp = array[i][j];155         array[i][j] = array[a][b];156         array[a][b] = temp;157     }158 159     public String toString() // string representation of this board (in the output format specified below)160      {161         StringBuilder s = new StringBuilder();162         s.append(ngrid + "\n");163         for (int i = 0; i < ngrid; i++) {164             for (int j = 0; j < ngrid; j++) {165                 s.append(String.format("%2d ", (int) board[(i * ngrid) + j]));166             }167 168             s.append("\n");169         }170 171         return s.toString();172     }173 174     public static void main(String[] args) // unit tests (not graded)175      {176         // read in the board specified in the filename177         In in = new In(args[0]);178         int n = in.readInt();179         int[][] tiles = new int[n][n];180 181         for (int i = 0; i < n; i++) {182             for (int j = 0; j < n; j++) {183                 tiles[i][j] = in.readInt();184             }185         }186 187         // solve the slider puzzle188         Board initial = new Board(tiles);189         StdOut.printf("hamming:%d manhattan:%d \n", initial.hamming(),190             initial.manhattan());191         StdOut.println("dim:" + initial.dimension());192         StdOut.println(initial.toString());193         StdOut.println("goal:" + initial.isGoal());194         StdOut.println("twin:\n" + initial.twin().toString());195 196         StdOut.println("neighbours:");197 198         for (Board s : initial.neighbors()) {199             StdOut.println(s.toString());200         }201     }202 }

  1 import edu.princeton.cs.algs4.In;  2 import edu.princeton.cs.algs4.MinPQ;  3 import edu.princeton.cs.algs4.StdOut;  4   5 import java.util.Stack;  6   7   8 public class Solver {  9     private boolean solvable; 10     private GameNode originLast; 11  12     public Solver(Board initial) // find a solution to the initial board (using the A* algorithm) 13      { 14         if (initial == null) { 15             throw new NullPointerException(); 16         } 17  18         solvable = true; 19  20         MinPQ<GameNode> queue = new MinPQ<GameNode>(); 21  22         queue.insert(new GameNode(initial, null, 0, false)); 23         queue.insert(new GameNode(initial.twin(), null, 0, true)); 24  25         while (!queue.isEmpty()) { 26             GameNode processed = queue.delMin(); 27  28             if (!processed.isTwin) { 29                 originLast = processed; 30             } 31  32             if (processed.boardValue.isGoal()) { 33                 if (processed.isTwin) { 34                     solvable = false; 35                 } 36  37                 break; 38             } 39  40             for (Board neighbor : processed.boardValue.neighbors()) { 41                 if ((processed.prev == null) || 42                         !processed.prev.boardValue.equals(neighbor)) { 43                     queue.insert(new GameNode(neighbor, processed, 44                             processed.moves + 1, processed.isTwin)); 45                 } 46             } 47         } 48     } 49  50     public boolean isSolvable() // is the initial board solvable? 51      { 52         return solvable; 53     } 54  55     public int moves() // min number of moves to solve initial board; -1 if unsolvable 56      { 57         if (isSolvable()) { 58             return originLast.moves; 59         } else { 60             return -1; 61         } 62     } 63  64     public Iterable<Board> solution() // sequence of boards in a shortest solution; null if unsolvable 65      { 66         if (!isSolvable()) { 67             return null; 68         } 69  70         Stack<Board> solutions = new Stack<Board>(); 71         GameNode current = originLast; 72  73         while (current.prev != null) { 74             solutions.push(current.boardValue); 75             current = current.prev; 76         } 77  78         solutions.push(current.boardValue); 79  80         Stack<Board> solutions2 = new Stack<Board>(); 81  82         while (!solutions.empty()) { 83             solutions2.push(solutions.pop()); 84         } 85  86         return solutions2; 87     } 88  89     public static void main(String[] args) { 90         // create initial board from file 91         In in = new In(args[0]); 92         int n = in.readInt(); 93         int[][] blocks = new int[n][n]; 94  95         for (int i = 0; i < n; i++) 96             for (int j = 0; j < n; j++) 97                 blocks[i][j] = in.readInt(); 98  99         Board initial = new Board(blocks);100 101         // solve the puzzle102         Solver solver = new Solver(initial);103 104         // print solution to standard output105         if (!solver.isSolvable()) {106             StdOut.println("No solution possible");107         } else {108             StdOut.println("Minimum number of moves = " + solver.moves());109 110             for (Board board : solver.solution())111                 StdOut.println(board);112         }113     }114 115     private class GameNode implements Comparable<GameNode> {116         private Board boardValue;117         private GameNode prev;118         private int moves;119         private boolean isTwin;120 121         public GameNode(Board current, GameNode prev, int moves, boolean isTwin) {122             this.boardValue =http://www.mamicode.com/ current;123             this.prev = prev;124             this.moves = moves;125             this.isTwin = isTwin;126         }127 128         public int compareTo(GameNode that) {129             int priority1 = this.boardValue.manhattan() + this.moves;130             int priority2 = that.boardValue.manhattan() + that.moves;131 132             if (priority1 == priority2) {133                 return 0;134             } else if (priority1 > priority2) {135                 return 1;136             } else {137                 return -1;138             }139         }140     }141 }