0

我正在编写一个滑块求解器,它有一个块对象列表(其中包含块大小和左上角的位置)和一个表示托盘的二维数组。只要有块,数组中的那个位置就指向块对象,否则为空。

在我的求解器中,我正在生成尚未见过的可能移动,将它们散列,然后选择一个来做(这会改变托盘布局)并在新的托盘布局上递归调用求解器。当在我返回调用之前没有更多可能的移动布局时,反转上一个移动并继续检查上一个调用,依此类推,直到它被解决或者我用完移动(没有解决方案)。

问题是,当我移动时,我得到了一个空指针异常。奇怪的是,它只发生在相当多的递归调用之后。该程序很好地运行了几次调用/移动,然后它似乎搞砸了。

generateMoves() 通过调用 move() 测试之前是否看到过移动,然后在检查后反转移动。我认为空指针在调用 move() 之后发生,并且 move() 正在设置 toMove = layout[][]。显然,它正在数组中查找一个为空的位置,而不是块中的一个位置。块列表和托盘数组之间似乎存在差异......因为当 move() 然后调用 setTrayAfterMove() 时,它会引发异常。我无法弄清楚为什么它适用于对 solveHelper() 的多次递归调用但随后中断。

import java.io.*; 
import java.util.*; 

public class Solver { 
    Tray initial; 
    Tray goal; 
    HashSet<Integer> visited; 
    LinkedList<Integer> movesToSolution; // list of moves leading to solution 
    int recursionCounter; 
    boolean isSolved; 

    public Solver(String initial, String goal) { 
        this.initial = new Tray(initial); 
        this.goal = new Tray(this.initial, goal); 
        visited = new HashSet<Integer>(); 
        movesToSolution = new LinkedList<Integer>(); 
        recursionCounter = 0; 
        isSolved = false; 
    } 

    public void solve() { 
        if (goal.equals(initial)) { 
            System.out.println("Solver finished no moves"); 
            return; 
        } 
        solveHelper(initial); 
        if (movesToSolution.isEmpty()) { 
            System.out.println("No solution"); 
            System.exit(1); 
        } 
        printMoves(); 
        System.out.println("Solver finished"); 
    } 

    private void solveHelper(Tray t) { 
        Stack<Integer> possibleMoves = new Stack<Integer>(); 
        int lastMoveMade = 0; 
        if (recursionCounter > 5000 || isSolved) { 
            return; 
        } 
        if (goal.equals(t)) { 
            isSolved = true; 
            // movesToSolution.addFirst(lastMoveMade); 
            return; 
        } 
        recursionCounter++; 

        LinkedList<Integer> movesToAdd = t.generateMoves(); 
        Iterator<Integer> movesIter = movesToAdd.iterator(); 
        while (movesIter.hasNext()) { 
            possibleMoves.push(movesIter.next()); 
        } 

        while (!possibleMoves.isEmpty()) { 
            lastMoveMade = possibleMoves.pop(); 
            boolean isMoved = t.move(lastMoveMade, false); 

            if (isMoved) { 
                int moveHash = t.hashCode(); 
                visited.add(moveHash); 
                solveHelper(t); 
            } 

            if (isSolved) { 
                movesToSolution.addFirst(lastMoveMade); 
                return; 
            } 
        } 
        t.move(lastMoveMade, true); 
        return; 
    } 

    public void printMoves() { 
        for (Integer move : movesToSolution) { 
            System.out.println(move); 
        } 
    }      

    public class Tray { 
        private int length; // number of rows 
        private int width; // number of columns 
        private LinkedList<Block> blocks; 
        private Block[][] layout; 

        public Tray(String file) { 
            blocks = new LinkedList<Block>(); 
            try { 
                Scanner s = new Scanner(new FileReader(file)); 
                length = s.nextInt(); 
                width = s.nextInt(); 
                layout = new Block[width][length]; 

                while (s.hasNextLine()) { 
                    int l = s.nextInt(); 
                    int w = s.nextInt(); 
                    int r = s.nextInt(); 
                    int c = s.nextInt(); 
                    Block b = new Block(l, w, r, c); 
                    blocks.add(b); 

                    for (int blockX = b.col; blockX < b.col + b.width; blockX++) { 
                        for (int blockY = b.row; blockY < b.row + b.length; blockY++) { 
                            layout[blockX][blockY] = b; 
                        } 
                    } 
                    s.nextLine(); 
                    // isOK(); 
                } 
            } catch (FileNotFoundException e) { 
                System.out.println("File not found"); 
            } 
        } 

        public Tray(Tray t, String file) { 
            blocks = new LinkedList<Block>(); 
            try { 
                this.length = t.length; 
                this.width = t.width; 
                Scanner s = new Scanner(new FileReader(file)); 
                layout = new Block[this.width][this.length]; 

                while (s.hasNextLine()) { 
                    int l = s.nextInt(); 
                    int w = s.nextInt(); 
                    int r = s.nextInt(); 
                    int c = s.nextInt(); 
                    Block b = new Block(l, w, r, c); 
                    blocks.add(b); 

                    for (int blockX = b.col; blockX < b.col + b.width; blockX++) { 
                        for (int blockY = b.row; blockY < b.row + b.length; blockY++) { 
                            layout[blockX][blockY] = b; 
                        } 
                    } 
                    s.nextLine(); 
                    // isOK(); 
                } 
            } catch (FileNotFoundException e) { 
                System.out.println("File not found"); 
            } 
        } 

        public void print() { 
            for (Block b : blocks) { 
                System.out.println(b.length + " " + b.width + " " + b.col + " "
                        + b.row); 
            } 
        } 

        public boolean equals(Object o) { 
            for (int x = 0; x < this.width; x++) { 
                for (int y = 0; y < this.length; y++) { 
                    if (this.layout[x][y] != null
                            && (((Tray) o).layout[x][y] == null || !((Tray) o).layout[x][y] 
                                    .equals(this.layout[x][y]))) { 
                        return false; 
                    } 
                } 
            } 
            return true; 
        } 

        public int hashCode() { 
            // TODO come up with hashcode unique to layout taking in 
            // consideration block at each coordinate, size of block 
            int hashCode = 0; 
            for (Block b : blocks) { 
                hashCode += (17 * (b.width * b.col)) + (7 * (b.length * b.row)); 
            } 
            return hashCode; 
        } 

        public boolean isOK() { 
            Block[][] trayChecker = new Block[width][length]; 
            Iterator<Block> blockIter = blocks.iterator(); 

            while (blockIter.hasNext()) { 
                Block b = blockIter.next(); 
                for (int x = b.col; x < x + b.width; x++) { 
                    for (int y = b.row; y < y + b.length; y++) { 
                        if (trayChecker[x][y] != null) { 
                            throw new IllegalStateException( 
                                    "Two blocks cannot be in the same location"); 
                        } 
                        if (x < 0 || x > width || y < 0 || y > length) { 
                            throw new IllegalStateException( 
                                    "Block must be completely on the board"); 
                        } 
                        trayChecker[x][y] = b; 
                    } 
                } 
            } 
            return true; 
        } 

        // only returns possible valid moves that haven't been seen before 
        public LinkedList<Integer> generateMoves() { 
            LinkedList<Integer> movesToTry = new LinkedList<Integer>(); 
            // TODO: generate moves that haven't been seen 
            int[] moveDir = { -10, 10, -1, 1 }; 
            for (Block b : blocks) { 
                for (int m : moveDir) { 
                    if (canMove(b, m)) { 
                        int trayMove = createMove(b, m); 
                        move(trayMove, false); 
                        if (!visited.contains(hashCode())) { 
                            movesToTry.add(trayMove); 
                        } 
                        move(trayMove, true); // reverse the move 
                    } 
                } 
            } 
            return movesToTry; 
        } 

        public boolean canMove(Block b, int dir) { 
            int tmp = Math.abs(dir); 
            int y = tmp % 10; 
            int x = tmp / 10; 
            if (dir < 0) { 
                x = -x; 
                y = -y; 
            } 

            if ((b.col + x < 0 || b.col + b.width + x > this.width) 
                    || (b.row + y < 0 || b.row + b.length + y > this.length)) { 
                return false; 
            } 

            if (x == 0) { 
                for (int xBlock = b.col; xBlock < b.col + b.width; xBlock++) { 
                    if (layout[xBlock][b.row + y] != null) { 
                        return false; 
                    } 
                    // } else if(x > 0 && layout[xBlock][b.row + y + b.length - 
                    // 1] != null) { 
                    // return false; 
                    // } 
                } 
            } 

            if (y == 0) { 
                for (int yBlock = b.row; yBlock < b.row + b.length; yBlock++) { 
                    if (layout[b.col + x][yBlock] != null) { 
                        return false; 
                    } 
                    // } else if(x > 0 && layout[b.col + x + b.width - 
                    // 1][yBlock] != null) { 
                    // return false; 
                    // } 
                } 
            } 

            return true; 
        } 

        // only takes valid input 
        public boolean move(int moveDirections, boolean reverse) { 
            Block toMove = null; 
            if (moveDirections == 0) { 
                return false; 
            } 

            // System.out.println(moveDirections + " " + recursionCounter); 
            int tmp = Math.abs(moveDirections); 
            int moveY = tmp % 10; 
            tmp /= 10; 
            int moveX = tmp % 10; 
            tmp /= 10; 
            int blockY = tmp % 1000; 
            tmp /= 1000; 
            int blockX = tmp; 
            System.out.println(blockX + " + " + blockY); 

            if (reverse) { 
                if (moveDirections > 0) { 
                    toMove = layout[blockX + moveX][blockY + moveY]; 
                } else { 
                    toMove = layout[blockX - moveX][blockY - moveY]; 
                } 
                setTrayAfterMove(toMove, true); 
                if (moveDirections < 0) { 
                    toMove.col += moveX; 
                    toMove.row += moveY; 
                } else { 
                    toMove.col -= moveX; 
                    toMove.row -= moveY; 
                } 

                setTrayAfterMove(toMove, false); 
            } else { 
                toMove = layout[blockX][blockY]; 
                setTrayAfterMove(toMove, true); 
                if (moveDirections < 0) { 
                    toMove.col -= moveX; 
                    toMove.row -= moveY; 
                } else { 
                    toMove.col += moveX; 
                    toMove.row += moveY; 
                } 
                setTrayAfterMove(toMove, false); 
            } 
            return true; 
            // 256x256 
            // 1x256 23x256 
            // 100x01 100x001 100x100 
            // 1x01 1x001 1x100 
            // 10x01 10x001 10x100 
        } 

        private int createMove(Block b, int dir) { 
            // multiply b.x to get 8 digits 
            // multiply bh .y to get 5 digits 
            int move = b.col * 100000; 
            move += (b.row * 100); 
            move += Math.abs(dir); 
            if (dir < 0) { 
                move *= -1; 
            } 
            return move; 
        } 

        private void setTrayAfterMove(Block b, boolean isBeforeMove) { 
            for (int blockX = b.col; blockX < b.col + b.width; blockX++) { 
                for (int blockY = b.row; blockY < b.row + b.length; blockY++) { 
                    if(isBeforeMove) { 
                        layout[blockX][blockY] = null; 
                    } else { 
                        layout[blockX][blockY] = b; 
                    } 
                } 
            } 
        } 
    } 

    public class Block { 
        private int length; 
        private int width; 
        private int row; 
        private int col; 

        public Block(int l, int w, int r, int c) { 
            length = l; 
            width = w; 
            row = r; 
            col = c; 
        } 

        public boolean equals(Block b) { 
            return this.length == b.length && this.width == b.width 
                    && this.row == b.row && this.col == b.col; 
        } 
    } 

    public static void main(String[] args) { 
        if (args.length < 2 || args.length > 3) { 
            throw new IllegalArgumentException( 
                    "Must have at least 2 and no more than 3 arguments"); 
        } 

        String initialLayout = args[0]; 
        String goalLayout = args[1]; 
        String debug = ""; 

        if (args.length == 3) { 
            if (args[0].substring(0, 2).equals("-o")) { 
                debug = args[0].substring(2, args[0].length()); 
                switch (debug) { 
                // cases for debugging arguments go here 
                } 
            } else { 
                throw new IllegalArgumentException( 
                        "First argument must start with -o"); 
            } 
            initialLayout = args[1]; 
            goalLayout = args[2]; 
        } 

        Solver s = new Solver(initialLayout, goalLayout); 
        s.solve(); 
    } 
} 

有人可以看看我的代码吗?也欢迎就如何提高效率提出建议。谢谢!

4

1 回答 1

1

让我给你一些建议,而不是解决你的问题,你如何自己解决这个问题。

  • 你在和IDE中开发吗?如果你不是,现在就开始吧。
  • 你用过调试器吗?如果没有,请立即开始。
  • 你有没有设置过条件断点?如果没有,请立即开始。

在为空的变量上设置条件断点,条件是该变量为空。在调试模式下运行你的程序,看看发生了什么。

如果社区为您解决了这个问题,那么您还没有学到任何关于成为更好的程序员的知识。一定要自己解决这个问题——否则你只是在推迟不可避免的事情:成为一个平庸的程序员。

于 2012-08-04T19:56:38.090 回答