「CS61B」Note(5) HW4 Puzzle Solver
In this lab, the task is building an artificial intelligence that solves puzzles. The requirements are at this link.
Puzzle Solver
First, define a search node of the puzzle to be:
- a WorldState.
- the number of moves made to reach this world state from the initial state.
- a reference to the previous search node.
- an optimization: save estimatedDistanceToGoal of the WorldState in an instance variable to avoid recomputing.
private class SearchNode{
WorldState worldState;
int distanceFromInit;
SearchNode previousNode;
//second optimization : save estimatedDistanceToGoal of WorldState in an instance variable
int estimatedDistanceToGoalSN;
public SearchNode(WorldState ws, int dfi, SearchNode psn) {
worldState = ws;
distanceFromInit = dfi;
previousNode = psn;
estimatedDistanceToGoalSN = ws.estimatedDistanceToGoal();
}
}
In this lab, we need to use MinPQ class from edu.princeton.cs.algs4 for the priority queue and implement priority sorting. Because the constructor function MinPQ(Comparator<Key> comparator)takes a comparator to compare keys in the PQ, we need to write a NodeComparator :
private class NodeComparator implements Comparator<SearchNode> {
@Override
public int compare(SearchNode sn1, SearchNode sn2) {
return sn1.distanceFromInit + sn1.estimatedDistanceToGoalSN
- (sn2.distanceFromInit + sn2.estimatedDistanceToGoalSN);
}
}
Then, just instantiate the NodeComparator and put it as the input of the constructor of MinPQ:
private MinPQ<SearchNode> pq = new MinPQ<>(new NodeComparator());
Constructor which solves the puzzle, computing everything necessary for moves() and solution() to not have to solve the problem again. Solves the puzzle using the A* algorithm.
And there is 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 world state is the same as the world state of the previous search node. So check if the WorldState is its own grandparent everytime we insert it into pq.
private MinPQ<SearchNode> pq = new MinPQ<>(new NodeComparator());
private int moves;
private SearchNode minSearchNode;
/** Constructor which solves the puzzle, computing
* everything necessary for moves() and solution() to
* not have to solve the problem again. Solves the
* puzzle using the A* algorithm. Assumes a solution exists. */
public Solver(WorldState initial) {
//insert an “initial search node” into the priority queue
SearchNode initialNode = new SearchNode(initial, 0, null);
pq.insert(initialNode);
//Remove the search node with minimum priority
minSearchNode = pq.delMin();
while (!minSearchNode.worldState.isGoal()) {
for (WorldState ws : minSearchNode.worldState.neighbors()) {
//critical optimization : checks that no enqueued WorldState is its own grandparent
if (minSearchNode.previousNode == null || !ws.equals(minSearchNode.previousNode.worldState)) {
pq.insert(new SearchNode(ws,minSearchNode.distanceFromInit + 1, minSearchNode));
}
}
minSearchNode = pq.delMin();
}
moves = minSearchNode.distanceFromInit;
}
move() and solution(): For the solution(), it returns a collection of WorldStates of the solution that is iterable. We need to use previousNode of SearchNode to get all of the WorldStates, so the oder will be reversed. Using a first-in last-out stack is appropriate for this task.
/** Returns the minimum number of moves to solve the puzzle starting
* at the initial WorldState. */
int moves() { return moves; }
/** Returns a sequence of WorldStates from the initial WorldState
* to the solution. */
public Iterable<WorldState> solution() {
Stack<WorldState> stack = new Stack<>();
while (minSearchNode != null) {
stack.push(minSearchNode.worldState);
minSearchNode = minSearchNode.previousNode;
}
return stack;
}
But the solution()failed the Test Immutability of Solver on Autograder, the reason is in the code above, I changed minSearchNode when solution() runs. So the Iterable will be different everytime. The correct version is as follow:
public Iterable<WorldState> solution() {
Stack<WorldState> stack = new Stack<>();
SearchNode thisSearchNode = minSearchNode;
while (thisSearchNode != null) {
stack.push(thisSearchNode.worldState);
thisSearchNode = thisSearchNode.previousNode;
}
return stack;
}
Board
- Board(tiles): Constructs a board from an N-by-N array of tiles where tiles[i][j] = tile at row i, column j
- tileAt(i, j): Returns value of tile at row i, column j (or 0 if blank)
- size(): Returns the board size N
In the Board constructor, if you just copy the reference, someone can change the state of your Board by changing the array. For example, if we use this.tiles = tiles in the Board constructor and change the values of tiles from the outside, then the tiles of the Board is also gonna be changed. This is called swallow copy, which only pass the reference(or address) to the new object. So instead, we need to use deep copy to avoid this.
public class Board implements WorldState{
private int[][] tiles;
public Board(int[][] tiles) {
//implement deep copy of input tiles
this.tiles = new int[tiles.length][tiles.length];
for (int i = 0; i < tiles.length; i++) {
System.arraycopy(tiles[i], 0, this.tiles[i], 0, tiles.length);
}
}
public int tileAt(int i, int j) {
if (i > size() - 1 || i < 0 || j > size() - 1 || j < 0) {
throw new java.lang.IndexOutOfBoundsException();
}
return tiles[i][j];
}
public int size() {
return tiles.length;
}
For the neighbors()function, I just used the solution provided by the teacher.
Goal Distance Estimates:
- Hamming estimate: The number of tiles in the wrong position.
- Manhattan estimate: The sum of the Manhattan distances (sum of the vertical and horizontal distance) from the tiles to their goal positions.
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
public int hamming() {
int hamming = 0;
for (int i = 0; i < size(); i++) {
for (int j = 0; j < size(); j++) {
if (tiles[i][j] != 0 && tiles[i][j] != i * size() + j + 1) {
hamming ++;
}
}
}
return hamming;
}
public int manhattan() {
int manhattan = 0;
for (int i = 0; i < size(); i++) {
for (int j = 0; j < size(); j++) {
if (tiles[i][j] != 0) {
manhattan += Math.abs((tiles[i][j] - 1) / size() - i) + Math.abs((tiles[i][j] - 1) % size() - j);
}
}
}
return manhattan;
}
- estimatedDistanceToGoal(): Estimated distance to goal. This method should simply return the results of manhattan() when submitted to Gradescope.
- equals(y): Returns true if this board’s tile values are the same position as y’s.
@Override
public int estimatedDistanceToGoal() { return manhattan(); }
public boolean equals(Object y) {
return Arrays.deepEquals(this.tiles, ((Board) y).tiles);
}
equals()failed the test. The reason is I didn’t consider the situation that y isn’t a Board and is-self. Arrays.deepEquals(Object[] o1,Object[] o2)checks if each value of two multidimensional arrays is equal.
public boolean equals(Object y) {
if (y == this) return true;
if (y == null || y.getClass() != this.getClass()) return false;
return Arrays.deepEquals(this.tiles, ((Board) y).tiles);
}
