Coursera-Algorithms,Part I-Robert Sedgewick-Programming Assignment 4

Programming Assignment 4: 8 Puzzle

问题描述

Board.java

import edu.princeton.cs.algs4.Stack;
public class Board {
    private final int[][] board;
    private final int dimension;
    private int iBlank;
    private int jBlank;
    private int hamming;
    private int manhattan;
    public Board(int[][] blocks)           // construct a board from an n-by-n array of blocks
                                           // 1.store blocks, 2.find blank(0), 
                                           // 3.compute hamming and manhattan
    {
        dimension = blocks.length;
        board = new int[dimension][dimension];

        hamming = 0;
        manhattan = 0;

        int temp;
        for (int i = 0; i < dimension; i++)
        {
            for (int j = 0; j < dimension; j++)
            {
                temp = blocks[i][j];
                board[i][j] = temp;
                if (temp == 0) 
                {
                    iBlank = i;
                    jBlank = j;
                }
                else
                {
                    if(temp != i * dimension + j + 1)
                        hamming++;
                    manhattan += Math.abs(i-(temp-1)/dimension) + Math.abs(j-(temp-1)%dimension);
                }
            }
        }       
    }                                      // (where blocks[i][j] = block in row i, column j)

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

    public int hamming()                   // number of blocks out of place
    {   return hamming; }

    public int manhattan()                 // sum of Manhattan distances between blocks and goal
    {   return manhattan;   }

    public boolean isGoal()                // is this board the goal board?
    {
        for (int i = 0; i < dimension; i++)
        {
            for (int j = 0; j < dimension; j++)
            {
                if( i == dimension - 1 && j == dimension - 1) return true;
                if( board[i][j] != i * dimension + j + 1) return false;
            }
        }
        return true;
    }

    public Board twin()                    // a board that is obtained by exchanging any pair of blocks
    {
        // Need a new int array to construct the new board  
        int[][] twinBlocks = new int[dimension][dimension];
        for (int i = 0; i < dimension; i++)
        {
            for (int j = 0; j < dimension; j++)
                twinBlocks[i][j] = board[i][j];  
        }

        // Always exchange the two blocks in the left-up corner, unless one of them is blank
        if (twinBlocks[0][0] == 0 || twinBlocks[0][1] == 0)
            exch(twinBlocks, 1, 0, 1, 1);
        else exch(twinBlocks, 0, 0, 0, 1);
        Board twin = new Board(twinBlocks);
        return twin;
    }

    private void exch(int[][] board,int i1, int j1, int i2, int j2)
    {
        int swap = board[i1][j1];
        board[i1][j1] = board[i2][j2];
        board[i2][j2] = swap;
    }

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

        Board that = (Board) y;
        if (this.dimension != that.dimension) return false;
        for (int i =0; i < dimension; i++)
        {
            for (int j = 0; j < dimension; j++)
            {
                if (board[i][j] != that.board[i][j]) 
                    return false;
            }
        }
        return true;
    }

    // A kind of data structure that stores the neighbors and that has the iterator() method 
    public Iterable<Board> neighbors()     // all neighboring boards
    {   
        // Use a stack
        Stack<Board> stack = new Stack<Board>();

        // Need a new int array to construct new boards
        int neighborBlocks[][] = new int[dimension][dimension];
        for (int i = 0; i < dimension; i++)
        {
            for (int j = 0; j < dimension; j++)
                neighborBlocks[i][j] = board[i][j];  
        }

        // Find neighbors in four directions, if exists, push
        if (iBlank > 0) 
            // If there exists an upper block, we can get a neighbor by moving the upper block downward.  
            // After storing this situation, remember to move it back for later examining.
            pushNeighbor(stack, neighborBlocks, iBlank, jBlank, iBlank-1, jBlank);
        if (iBlank < dimension - 1) 
            pushNeighbor(stack, neighborBlocks, iBlank, jBlank, iBlank+1, jBlank);
        if (jBlank > 0) 
            pushNeighbor(stack, neighborBlocks, iBlank, jBlank, iBlank, jBlank-1);
        if (jBlank < dimension - 1) 
            pushNeighbor(stack, neighborBlocks, iBlank, jBlank, iBlank, jBlank+1);

        return stack;   
    }
    // Perform single-step move (exchange). Push it. 
    // Then recover to initial state (exchange back) for later examining.
    private void pushNeighbor(Stack<Board> stack, int[][] blocks, int iBlank, int jBlank, int iBlankNew, int jBlankNew)
    {
        exch(blocks, iBlank, jBlank, iBlankNew, jBlankNew);
        Board neighbor = new Board(blocks);
        stack.push(neighbor);
        exch(blocks, iBlank, jBlank, iBlankNew, jBlankNew); 
    }

    public String toString()               // string representation of this board (in the output format specified below)
    {
        String info = dimension + "\n";
        for (int i =0; i < dimension; i++)
        {
            for (int j = 0; j < dimension; j++)
                info += " " + board[i][j];
            info += "\n";
        }
        return info;
    }

    public static void main(String[] args) // unit tests (not graded)
    {
        System.out.println("client starts:");
    }

}

Solver.java

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

public class Solver {
    private final boolean isSolvable;
    private final int moves; 
    private final Node reachedGoal;
    public Solver(Board initial)           // find a solution to the initial board (using the A* algorithm)
    {
        if (initial == null) throw new java.lang.IllegalArgumentException();

        MinPQ<Node> pqOrig = new MinPQ<Node>();
        MinPQ<Node> pqTwin = new MinPQ<Node>(); // Twins are used for knowing if solvable

        pqOrig.insert(new Node(initial, null));
        pqTwin.insert(new Node(initial.twin(), null));

        Node fetchOrig;
        Node fetchTwin;

        // Find result simultaneously in both origin pq and twin pq 
        // Either reached its goal, loop ends, 
        // By checking which reached its goal, we know whether solvable
        while (true)
        {
            fetchOrig = pqOrig.delMin();
            fetchTwin = pqTwin.delMin();

            if (fetchOrig.isGoal() || fetchTwin.isGoal()) break;

            Iterable<Board> neighborsArrayOrig = fetchOrig.neighborsArray();
            Iterable<Board> neighborsArrayTwin = fetchTwin.neighborsArray();

            for (Board n: neighborsArrayOrig)
            {
                if (fetchOrig.moves==0 || !fetchOrig.isGoingBack(n))  // optimization
                    pqOrig.insert(new Node(n, fetchOrig));
            }

            for (Board n: neighborsArrayTwin)
            {
                if (fetchTwin.moves==0 || !fetchTwin.isGoingBack(n)) 
                    pqTwin.insert(new Node(n, fetchTwin));
            }
        }
        if (fetchOrig.isGoal())
        {
            isSolvable = true;
            moves = fetchOrig.moves;
            reachedGoal = fetchOrig;
        }
        else
        {
            isSolvable = false;
            moves = -1;
            reachedGoal = null;
        }
    }

    // Node: storing information of each step of the game
    private class Node implements Comparable<Node>
    {
        private final Board board;
        private final Node previous;
        private final int moves;
        private final int priority;

        public Node(Board board,Node previous)
        {
            this.board = board;
            this.previous = previous;
            if (previous == null)
                this.moves = 0;
            else
                this.moves = previous.moves + 1;
            priority = board.manhattan() + moves;
        }
        public Iterable<Board> neighborsArray()
        {   return board.neighbors();   }

        public boolean isGoal()
        {   return board.isGoal();  }

        public boolean isGoingBack(Board that)
        {   return previous.board.equals(that); }

        public int compareTo(Node that)
        {   return Integer.compare(Integer.valueOf(this.priority), Integer.valueOf(that.priority)); }
    }

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

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

    public Iterable<Board> solution()      // sequence of boards in a shortest solution; null if unsolvable
    {   
        if (!isSolvable) return null;

        Stack<Board> stack = new Stack<Board>(); 

        Node current = reachedGoal;
        while(current != null)
        {
            stack.push(current.board);
            current = current.previous;
        }
        return stack;   
    }

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

}

关于A*算法：每一步最优
Intuition