Coursera week4 Programming Assignment 4: 8 Puzzle

题目链接

8 puzzle

题意简介

拼图游戏，该拼图板是一个n*n的方格，但是只放了n*n-1个卡片，有一个空卡片便于我们移动，要求最后把拼图按照从上到下从左到右的顺序放卡片(1~n*n-1)，求最少的步数。

题目解析

1、使用A*搜索算法，其实就是BFS的变体，每次选择优先级最高的节点出队列。我们直接使用老师提供的MinPQ数据结构即可。
2、剪枝。代码中设计了一个数据结构，一个私有类——Node，保存三元组{当前的Board， 到当前这个board移动的步数，前一个搜索节点 }，为了避免重复搜索，若果要当前节点的邻居节点和当前节点的前序节点一样，那就放弃该邻居节点，避免重复计算（题目中说的很清楚）。
注: 刚开始我使用的Node保存的是如上所说的三元组，但是后台time测试一直不通过，后来发现，在我的Node类实现的Comparable接口中，在计算优先级的时候，都调用Board的manhattan 函数（复杂度为n的平方）来进行计算，但是在优先队列中，因为其低层实现是堆，因此每次调整堆都要再次调用Comparable接口函数，导致manhattan 函数被调用了很多次，导致超时，因此，我将Node类增加了第4个元素，即priority，其等于manhattan 函数的值加上走的步数，然后在Comparable接口中改为对priopity的比较。最后time检测也通过了。（如果Time检测没通过，很可能是这个原因。如果您看不懂我的描述，直接看代码即可，代码比较好懂（请原谅笔者的组织语言水平~））

可能出bug的地方

1、Board的toString()函数，该函数记得格式化字符串为"%2d "。
2、 Solver的Solution函数不满足immutable性质。解决方法：在solution函数中，更改过的状态，记得还原。
3、超时问题，time检测不通过。解决方法：上面已经介绍。

注意

java 数组的clone方法需要注意：看board.java的main函数

代码

Board.java

package part1.week4.PriorityQueue.Assigment;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class Board {
	
	private int n;
	private final int BLANK = 0;
	private int[][] board = null;

	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)
		if(null == blocks) {
			throw new IllegalArgumentException();
		}
		n = blocks.length;
		assert(n >= 2 && n < 128);
		board = clone(blocks);
	}

	

	public int dimension() { // board dimension n
		return n;
	}

	public int hamming() { // number of blocks out of place
		int res = 0;
		int count = 1;
		// compare the goal with every block in the board except the last one
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(count == n * n) {
					return res;
				}
				if(board[i][j] != count) {
					res++;
				}
				count++;
			}
		}
		return res;
	}

	public int manhattan() { // sum of Manhattan distances between blocks and goal
		int count = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(board[i][j] != BLANK) {
					int x = (board[i][j] - 1)/ n;
					int y = (board[i][j] - 1) % n;
					count += Math.abs(x - i);
					count += Math.abs(y - j);
				}
			}
		}
		return count;
	}

	public boolean isGoal() { // is this board the goal board?
		return manhattan() == 0;
	}

	public Board twin() { // a board that is obtained by exchanging any pair of blocks
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n -1 ; j++) {
				if(board[i][j] != 0 && board[i][j+1] != 0) {
					return getSwapBoard(i, j, i, j + 1);
				}
			}
		}
		return null;
	}
	
	private int[][] clone(int[][] src) {
		int[][] dst = new int[src.length][src[0].length];
		for(int i = 0; i < src.length; i++) {
			for(int j = 0; j < src[0].length; j++) {
				dst[i][j] = src[i][j];
			}
		}
		return dst;
	}
	
	private Board getSwapBoard(int firstX, int firstY, int secondX, int secondY) {
		if(!indexValid(firstX) || !indexValid(firstY) || !indexValid(secondX) || !indexValid(secondY)) {
			return null;
		}
		int[][] tempBoard = clone(board);
		int temp = tempBoard[firstX][firstY];
		tempBoard[firstX][firstY] = tempBoard[secondX][secondY];
		tempBoard[secondX][secondY] = temp;
		return new Board(tempBoard);
	}
	
	private boolean indexValid(int x) {
		return x >= 0 && x < n;
	}

	public boolean equals(Object y) { // does this board equal y?
		if(y == this) {
			return true;
		}
		if(y == null) {
			return false;
		}
		if(!(y instanceof Board) ) {
			return false;
		}
		return y.toString().equals(this.toString());
	}

	public Iterable<Board> neighbors() { // all neighboring boards
		// find the blank block position
		int i = 0;
		int j = 0;
		boolean flag = false;
		for(i = 0; i < n; i++) {
			for(j = 0; j < n; j++) {
				if(board[i][j] == BLANK) {
					flag = true;
					break;
				}
			}
			if(flag) {
				break;
			}
		}
		
		List<Board> list = new ArrayList<Board>();
		if(indexValid(i-1) && indexValid(j)) {
			list.add(getSwapBoard(i-1, j, i, j));
		}
		if(indexValid(i + 1) && indexValid(j)) {
			list.add(getSwapBoard(i+1, j, i, j));
		}
		if(indexValid(i) && indexValid(j - 1)) {
			list.add(getSwapBoard(i, j - 1, i, j));
		}
		if(indexValid(i) && indexValid(j + 1)) {
			list.add(getSwapBoard(i, j + 1, i, j));
		}
		return list;
	}

	public String toString() { // string representation of this board (in the output format specified below)
		StringBuilder sb = new StringBuilder();
		sb.append(n);
		sb.append("\n");
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				sb.append(String.format("%2d ", board[i][j]));
			}
			sb.append("\n");
		}
		return sb.toString();
	}

	public static void main(String[] args) { // unit tests (not graded)
		Board board = new Board(new int[][]{{8, 1, 3}, {4, 0, 2}, {7, 6, 5}});
		System.out.println(board.hamming());
		System.out.println(board.manhattan());
		
		
		int[][] src = new int[][]{{1,2,3}, {4,5,6}, {7,8,9}};
		int[][] dst = src.clone();
		dst[0][0] = 1000;
		
		System.out.println(Arrays.deepToString(src)); // src[0][0] = 1000
		System.out.println(Arrays.deepToString(dst)); // dst[0][0] = 1000
		System.out.println(src == dst); // false
	}
}

Solver.java

package part1.week4.PriorityQueue.Assigment;



import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.StdOut;

public class Solver {
	
	private Node lastNode;
	
	private class Node implements Comparable<Node>{
		private int currMove = 0;
		private Board board = null;
		private Node preNode = null;
		private int priority = Integer.MAX_VALUE;
		
		public Node(Board inital) {
			this.currMove = 0;
			this.board = inital;
			this.preNode = null;
			this.priority = board.manhattan();
		}
		
		public Node(Board curr, Node pre) {
			this.currMove = pre.currMove + 1;
			this.board = curr;
			this.preNode = pre;
			this.priority = board.manhattan() + currMove;
		}

		@Override
		public int compareTo(Node that) {
			return this.priority - that.priority;
		}
	
	}
	
	public Solver(Board initial) { // find a solution to the initial board (using the A* algorithm)
		if(null == initial) {
			throw new IllegalArgumentException();
		}
		
		MinPQ<Node> mySearchNode = new MinPQ<Solver.Node>();
		mySearchNode.insert(new Node(initial));
		
		MinPQ<Node> yourSearchNode = new MinPQ<Solver.Node>();
		yourSearchNode.insert(new Node(initial.twin()));
		
		while(true) {
			lastNode = getNextNodes(mySearchNode);
			// if any of twins find the goal, the game is ended.
			if(lastNode == null && getNextNodes(yourSearchNode) == null) {
				
			}else {
				break;
			}
			
			// System.out.println("hahah");
		}
	}
	
	
	private Node getNextNodes(MinPQ<Node> nodes) {
		if(nodes.isEmpty()) {
			return null;
		}
		Node curr = nodes.delMin();
		if(curr.board.isGoal()) {
			return curr;
		}
		
		for(Board neighbor : curr.board.neighbors()) {
			if(curr.preNode == null || !neighbor.equals(curr.preNode.board)) {
				nodes.insert(new Node(neighbor, curr));
			}
		}
		
		return null;
	}

	public boolean isSolvable() { // is the initial board solvable?
		return lastNode != null;
	}

	public int moves() { // min number of moves to solve initial board; -1 if unsolvable
		if(isSolvable()) {
			return lastNode.currMove;
		}else {
			return -1;
		}
	}

	public Iterable<Board> solution() { // sequence of boards in a shortest solution; null if unsolvable
		if(!isSolvable()) {
			return null;
		}
		Node tempNode = lastNode;
		Stack<Board> res = new Stack<Board>();
		while(lastNode != null) {
			res.push(lastNode.board);
			lastNode = lastNode.preNode;
		}
		List<Board> boards = new ArrayList<Board>();
		while(!res.isEmpty()) {
			boards.add(res.pop());
		}
		lastNode = tempNode;
		return boards;
	}

	public static void main(String[] args) { // solve a slider puzzle (given below)

		System.out.println(args[0]);
		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);
		
		// print solution to standard output
	    if (!solver.isSolvable())
	        StdOut.println("No solution possible");
	    else {
	        StdOut.println("Minimum number of moves = " + solver.moves());
	        for (Board board : solver.solution()) {
	        	StdOut.println(board);
	        }
	    }
	}
}