java - 8x8 骑士之旅 Java 内存不足

Question

此代码适用于 5x5、6x6、7x7，但在 8x8 中内存不足。我把内存加到2048M了还是不行。代码应该使用 Stack 类和回溯作为解决方案的一部分这是代码:

private int counter=0;
private boolean grid[][]=new boolean [ROWS][COLS];
private  Stack tour=new Stack(0,0);
private int spaces=ROWS*COLS;
private int[][] intGrid=new int[ROWS][COLS];


private static final Point[] Moves=new Point[]{
    new Point(-1, -2),
    new Point(-1, 2),
    new Point(1, -2),
    new Point(1, 2),
    new Point(-2, -1),
    new Point(-2, 1),
    new Point(2, -1),
    new Point(2, 1),
};

public void run(){
    fillIntGrid();
    tourFrom(tour.first);
    println("SOLUTION FOUND:");
    printBoard();
}

public boolean tourFrom(Point currPoint){
    counter++;
    grid[currPoint.xCoord][currPoint.yCoord] = true;
    intGrid[currPoint.xCoord][currPoint.yCoord]=counter;
    if(counter==spaces)
        return true;
    for(Point nextMove:Moves){
        int nextRow=currPoint.xCoord+nextMove.xCoord;
        int nextCol =currPoint.yCoord+nextMove.yCoord;
        tour.push(nextRow,nextCol);
        if(nextRow<0 || nextRow>=grid.length)
            continue;
        else if(nextCol<0 || nextCol>=grid.length)
            continue;
        else if(grid[nextRow][nextCol])
            continue;
        if(tourFrom(tour.first))
            return true;
        } 
    grid[currPoint.xCoord][currPoint.yCoord] = false;
    intGrid[currPoint.xCoord][currPoint.yCoord]=0;
    counter--;
    tour.pop();
    return false;
}

public void fillIntGrid(){
    for(int i=0;i<ROWS;i++){
        for (int j=0;j<COLS;j++){
            intGrid[i][j]=0;
        }
    }
}

可能出现什么问题？

Answer 1

由于这是一个编程练习...

提示:比较push的数量调用和 pop在 tourFrom 正文中进行的调用.

<小时/>

好的，这就是我用来解决这个问题的逻辑。

这不是一个无限递归问题，因为这会给出 StackOverflowError ，不是 OutOfMemoryError .

安OutOfMemoryError意味着某种存储泄漏。 (可能还有其他问题......但让我们继续探讨存储泄漏的想法。)

问:哪种数据结构的大小可能不受限制？

A:堆栈。

问:如何才能无限增长？

答:如果你的推送次数多于弹出次数。

所以看看推送和弹出代码......

<小时/>

问:但是 6x6 和 7x7(据说)是如何工作的？

答:算一下:-)

<小时/>

退后一步看看解决方案，还有其他问题。例如，您没有使用 tourFrom 返回的值。这意味着您将始终报告找到了解决方案，并且在找到解决方案时您不会停止。

我真的很怀疑>>这个<是否可以在较小的电路板尺寸上正常工作。