欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Coursera week4 Programming Assignment 4: 8 Puzzle

程序员文章站 2022-07-09 13:48:33
...

题目链接

8 puzzle

题意简介

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

题目解析

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

可能出bug的地方

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

注意

java 数组的clone方法需要注意:看board.javamain函数

代码

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);
	        }
	    }
	}
}