Princeton Algorithm Part 1 Week 4 - 8puzzle

有点难啊。。
85/100,memory测试全挂。。
总结稍后补上

Board.java

import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.StdOut;
import java.util.Comparator;

public class Board  {
    private int n; // board dimension n
    private int[] board; 
    private int zero; //position of zero
    
    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)
        n = blocks.length;

        board = new int[n*n];
        int i = 0;
        for (int[] a : blocks){
            for (int b:a){
                if (b == 0) 
                    zero = i;
                board[i++] = b; // Assign value to board.
            }
        }
    }
    
    private int[][] decode (int[] board){
        int count = 0;
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                result[i][j] = board[count++];
        return result;
    }
    
    private int row(int index){
        return index / n + 1;
    }
    
    private int col(int index){
        return index % n + 1;
    }
    
    public int dimension(){
        return n;
    }
    
    public int hamming(){
        int count = 0;
        for (int i = 0; i < n*n-1; i++){
            if (board[i] != i+1)
                count++;
        }       
        return count;
    }
    
    public int manhattan(){
        // sum of Manhattan distances between blocks and goal
        int manha = 0;
        int diff;
        for (int i = 0; i < n*n; i++){
            //bad move
            if(board[i] == 0)       diff = 0;
            else{
                diff = (Math.abs(row(i) - row(board[i]-1)) 
                      + Math.abs(col(i) - col(board[i]-1)));
            }
            manha += diff;}
        return manha;
    }
    
    public boolean isGoal(){
        // test the board is the goal board or not
        for (int i = 0; i < n*n-1 ; i++)
            if (board[i] != i+1)
                return false;
        return true;
    }
    
    public Board twin(){
        // return a board that is obtained by exch an pair of blocks;  
        //**Detecting unsolvable puzzles
        int[] twin1d = board.clone();
        int[][] twin2d = new int[n][n];
        if (twin1d[0] != 0 && twin1d[1] != 0 ){
            int temp = twin1d[0];
            twin1d[0] = twin1d[1];
            twin1d[1] = temp;
        }
        else {
            int temp = twin1d[2];
            twin1d[2] = twin1d[3];
            twin1d[3] = temp;
        }
        
        int c = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                twin2d[i][j] = twin1d[c++];
        
        return new Board(twin2d);
    }
    
    public boolean equals(Object y){
        // does this board equal y  ?
        if (y == null)                          return false;
        if (y == this)                          return true;
        if (y.getClass() != this.getClass())    return false;

        Board thatB = (Board)y;
        if (thatB.dimension() != n)             return false;

        return Arrays.equals(this.board, thatB.board);
    }
    
    private void exch(int a, int b){
        int temp = board[a];
        board[a] = board[b];
        board[b] = temp;
    }

    public Iterable<Board> neighbors()  {
        // all neighboring boards
        // wtf?
        MinPQ<Board> pq = new MinPQ<Board>(new Comparator<Board>() {  
            public int compare(Board B1, Board B2) {  
               if (B1.manhattan() < B2.manhattan()) return -1;  
               if (B1.manhattan() == B2.manhattan()) return 0;  
               return 1;  
            }  
        });
        Board temp;
        if (row(zero) != n){

            temp = new Board(decode(board));
            temp.exch(zero,zero+n); //zero moves down;
            temp.zero = zero + n;
            pq.insert(temp);
        }
        if (row(zero) != 1){
            temp = new Board(decode(board));
            temp.exch(zero,zero-n); //zero moves up
            temp.zero = zero - n;
            pq.insert(temp);
        }
        if (col(zero) != 1){
            temp = new Board(decode(board));
            temp.exch(zero,zero-1); //zero moves left;
            temp.zero = zero - 1;
            pq.insert(temp);
        }
        if (col(zero) != n){
            temp = new Board(decode(board));
            temp.exch(zero,zero+1); //zero moves right;
            temp.zero = zero + 1;
            pq.insert(temp);
        }
        return pq;
    }
    

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

    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);  
 
        StdOut.println(initial.hamming());  
        System.out.println("Initial!:");
        StdOut.println(initial);
        for(Board b : initial.neighbors())
            System.out.println(b);
    } 
}

Solver.java

import java.util.Comparator;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;


public class Solver {
    private int moves = -1; // when the board is unsolvable, moves = -1;
    private boolean solved = false;
    private Stack gameTree;
    private searchNode champion;
    private boolean isSolvable = false;
    private int step;
    
    //twin test;
    
    private MinPQ<searchNode> loserpool = new MinPQ <searchNode> (new Comparator<searchNode>(){
        public int compare(searchNode o1, searchNode o2){
            if (o1.priority < o2.priority) return -1;
            if (o1.priority == o2.priority) return 0;
            return 1;
        }
    });
    
    private class searchNode{
        private Board board;
        private int moves;
        private int priority;
        private searchNode prev;
        
        public searchNode(Board board, int moves, searchNode prev){
            this.board = board;
            this.moves = moves;
            this.prev = prev;
            this.priority = board.manhattan() + moves;  

        }
    }
    
    public Solver(Board initial){
        if(initial == null) throw new IllegalArgumentException();
        
        int TwinPriority = 2*initial.dimension(); // Starter Priority for Twin;
        
        Board twin = initial.twin();
        searchNode initialNode = new searchNode(initial, 0, null);
    //  searchNode twinNode = new searchNode(twin, 0, null); //twin test;  with lower priority
        searchNode twinNode = new searchNode(twin, TwinPriority, null);
        
        loserpool.insert (initialNode);
        loserpool.insert (twinNode);
        
        if(initialNode.board.isGoal())  
            championship(initialNode);
        
        if(twinNode.board.isGoal())     
            championship(twinNode);
            
        while(!solved)
            solve();
        
        gameTree(initialNode.board);
    }
    
    private void solve(){
        searchNode node = loserpool.delMin();

        step+=1;

        for (Board board: node.board.neighbors()){
            if (node.prev != null && board.equals(node.prev.board)){
            }else{
            searchNode child = new searchNode(board, node.moves+1, node);

            if(child.board.isGoal()) {
                championship(child);
                break;
            }
                
            loserpool.insert(child);
            }
        }
    }
    
    private void championship(searchNode champion){
        solved = true;
        this.champion = champion;
        this.moves = champion.moves;
    }
    
    public boolean isSolvable(){
        return isSolvable;
    }
    
    public int moves(){
        // min number of moves to solve initial board; -1 if unsolvable
        return moves;
    }
    
    private void SPrinter(){
        Stack<Board> S = gameTree;
        int move = 0;
        if(!isSolvable){
            System.out.println("It's unsolvable");
            return;
        }
        while (!S.isEmpty()){
            System.out.println("Move: " + move++ );
            System.out.println(S.pop());
        }
    }
    
    private  void gameTree(Board initial){
        Stack<Board> S = new Stack<Board>();
        searchNode node = champion;
        
        //test
        while(node.prev != null){
            S.push(node.board);
            node = node.prev;
        }
        S.push(node.board);
        
        //test
        /*for (int i = 0; i <= champion.moves; i++){
            S.push(node.board);
            node = node.prev;
        }*/
        this.gameTree = S;
        if(gameTree.peek() == initial)
            isSolvable = true;
        else this.moves = -1;
    }
    
    public Iterable<Board> solution(){
        // sequence of boards in a shortest solution; null if unsolvable
        if (isSolvable())
            return gameTree;
        return null;
    }
    
    public static void main(String[] args){
        // solve a slider puzzle (given below)
        
        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);
        
        if(solver.isSolvable)  StdOut.println("Solvable");
        if(!solver.isSolvable)  StdOut.println("Unsolvable");
        System.out.println("Total move: " + solver.moves);
        // print solution
        System.out.println("---------------");
        solver.SPrinter();
        System.out.println(solver.isSolvable());
        System.out.println("Step: " + solver.step);
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容