8 puzzle已经提供了解决思路,早期的人工智能算法A。我只能感觉它的神奇,但是没法创造性地使用它。只能按部就班地完成这周的作业。 难点在于对过程的不理解。这个33的格子搜索算法没有尽头,随着步数的越来越多,所耗资源也越来越大。因此,判断是否可解只能交换两个格子作为twin,同时计算两个,肯定只有一个可解。
因此用数组来表示board,很多步骤实现非常难看。 Board.javaimport edu.princeton.cs.algs4.Queue;import edu.princeton.cs.algs4.StdRandom;public class Board { private int[][] blocks; private int blank_x; // index of blank block private int blank_y; // index of blank block public Board(int[][] blocks){ if(blocks == null) throw new IllegalArgumentException(); this.blocks = new int[blocks.length][blocks.length]; for(int i=0; ineighbors() { Queue que = new Queue<>(); int[][] neighbor; int[][] dirs = new int[][]{ {blank_x-1, blank_y}, {blank_x+1, blank_y}, {blank_x, blank_y-1}, {blank_x, blank_y+1} }; for(int[] dir : dirs){ if(validIdx(dir)){ neighbor = copy(); neighbor[blank_x][blank_y] = neighbor[dir[0]][dir[1]]; neighbor[dir[0]][dir[1]] = 0; que.enqueue(new Board(neighbor)); } } return que; } private void exch(int[][] blocks, int x1, int y1, int x2, int y2) { int temp = blocks[x2][y2]; blocks[x2][y2] = blocks[x1][y1]; blocks[x1][y1] = temp; } private boolean validIdx(int[] dir) { if(dir[0] >= 0 && dir[0] < dimension() && dir[1] >= 0 && dir[1] < dimension()) return true; return false; } private int[][] copy() { int [][] newBlocks = new int[dimension()][dimension()]; for(int i=0; i
Solver.java
import edu.princeton.cs.algs4.In;import edu.princeton.cs.algs4.MinPQ;import edu.princeton.cs.algs4.Queue;import edu.princeton.cs.algs4.StdOut;import java.util.Stack;public class Solver { private Queuesolutions; public Solver(Board initial) { if(initial == null) throw new IllegalArgumentException(); find(initial); } private boolean find(Board initial) { MinPQ pq, qp; pq = new MinPQ<>(); qp = new MinPQ<>(); // twin Stack process = new Stack<>(); solutions = new Queue<>(); pq.insert(new Node(initial, 0)); qp.insert(new Node(initial.twin(), 0)); while(true){ Node chosen = pq.delMin(); Node t_chosen = qp.delMin(); if(chosen.board.isGoal()) { Node end = chosen; while(end != null){ process.add(end.board); end = end.prev; } break; } if(t_chosen.board.isGoal()) { break; } for(Board neighbor : chosen.board.neighbors()) { Node n = new Node(neighbor, chosen.moves+1); n.prev = chosen; if(chosen.prev != null && neighbor.equals(chosen.prev.board)) { continue; // critical optimisation } pq.insert(n); } for(Board neighbor : t_chosen.board.neighbors()) { Node n = new Node(neighbor, t_chosen.moves+1); n.prev = t_chosen; if(t_chosen.prev != null && neighbor.equals(t_chosen.prev.board)) { continue; } qp.insert(n); } } while(! process.isEmpty()) { solutions.enqueue(process.pop()); } return !solutions.isEmpty(); } private class Node implements Comparable { public Node prev; public Board board; public int moves; public int priority; public Node(Board board, int moves) { this.board = board; this.moves = moves; priority = moves + board.manhattan(); } @Override public int compareTo(Node o) { return priority - o.priority; } } public boolean isSolvable() { return !solutions.isEmpty(); } public int moves() { return solutions.size()-1; } public Iterable solution() { if(!isSolvable()) return null; return solutions; } 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); // 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); } }}