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

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

程序员文章站 2022-07-09 13:47:57
...

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*算法:每一步最优
IntuitionCoursera-Algorithms,Part I-Robert Sedgewick-Programming Assignment 4