普林斯顿算法课第四周作业_8Puzzle

作业地址：http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html

作业难点：

1、如何求一个Puzzle的解？

根据作业提示，使用MinPQ将GameTree的不同状态以hamming或manhattan方法求得优先级，加入MinPQ队列，并对min值进行分析，直到达到最后状态。需要自定义MinPQ使用的数据结构。

2、如何在有限步的情况下判断一个Puzzle是否有解？

根据作业提示，如果Twin有解那么原始Puzzle就无解，因此可以将两个Puzzle一起加入优先队列分析；在求到最终状态后，通过回溯初始状态，进而判断Puzzle是否有解。

容易扣分点：

1、manhattan()算法中的列边界；

2、twin()无效，主要是没有理解twin的定义；

3、equals()实现随意，务必留意参考类的equals()实现；

4、不能在有限步情况下求得最终结果，造成内存溢出；

5、moves()结果是原始Puzzle的还是twinPuzzle的。

部分代码参考：

manhattan():

    public int manhattan()
    {
        int mhNum = 0;
        int blockNum = 0;
        int posX = 0;
        int posY = 0;
        for (int i = 0; i < brdDim; i++) {
            for (int j = 0; j < brdDim; j++) {
                blockNum = i * brdDim + j + 1;
                if (brdBlocks[i][j] != blockNum && brdBlocks[i][j] != 0) {
                    posX = brdBlocks[i][j] / brdDim;
                    posY = brdBlocks[i][j] % brdDim - 1;
                    if (posY < 0) {
                        posY += brdDim;
                        posX -= 1;
                    }
                    mhNum += Math.abs(posY - j) + Math.abs(posX - i);
                }
            }
        }
        return mhNum;
    }

Solver():

    public Solver(Board initial)
    {
        initBoard = initial;
        moveCount = 0;
        finalNode = null;
        if (initBoard.isGoal()) {
            finalNode = new SearchNode(initBoard);
            finalNode.moves = moveCount;
            return;
        }
        pq = new MinPQ<SearchNode>();
        pq.insert(new SearchNode(initBoard));
        pq.insert(new SearchNode(initBoard.twin()));
        boolean findGoal = true;
        while (findGoal) {
            SearchNode srNode = pq.delMin();
            for (Board nbrBoard: srNode.a.neighbors()) {
                if (nbrBoard.isGoal()) {
                    finalNode = new SearchNode(nbrBoard);
                    finalNode.prev = srNode;
                    finalNode.moves = srNode.moves + 1;
                    moveCount = finalNode.moves;
                    findGoal = false;
                    break;
                } else {
                    if (srNode.prev == null || !nbrBoard.equals(srNode.prev.a)) {
                        SearchNode nextNode = new SearchNode(nbrBoard);
                        nextNode.prev = srNode;
                        nextNode.moves = srNode.moves + 1;
                        pq.insert(nextNode);
                    }
                }
            }
        }
    }

solution():

    public Iterable<Board> solution()
    {
        Stack<Board> neighbours = new Stack<Board>();
        if (finalNode == null) {
             StdOut.println("No solution possible");
             return null;
        }
        SearchNode curNode = finalNode;
        SearchNode preNode = curNode;
        do {
            neighbours.push(curNode.a);
            preNode = curNode;
            curNode = curNode.prev;
        } while (curNode != null);
        if (!preNode.a.equals(initBoard)) return null;
        return neighbours;
    }
    private static class SearchNode implements Comparable<SearchNode> {
        private final Board a;       // Board involved in event, possibly null
        private SearchNode prev;
        private int moves;
        public SearchNode(Board a) {
            this.a = a;
            prev = null;
            moves = 0;
        }
        public int compareTo(SearchNode that) {
            return Integer.compare(this.a.manhattan() + moves,
              that.a.manhattan() + that.moves);
        }
    }