如何修复此堆栈溢出错误？

Question

所以我有我认为是非常好的java数独解算器代码，但我需要一些关于此方法的帮助。当我将它嵌入到 main 方法中时，它会导致堆栈溢出。问题是我的方法不知道如何扭转并纠正其错误。我需要一个布尔标志（与下面代码中使用的标志不同，实际上效果更好）或让它知道何时应该返回以及何时可以再次前进并继续解决游戏的东西。感谢您可以提供的任何帮助

public void play(int r, int c){//this method throws the StackOverflowError
    if(needAtLoc(r,c).size()==9){
        int num=1+generator.nextInt(9);
        setCell(r,c,num,this);

    if(c<8){
    System.out.println(this);///////////////
    play(r, c+1);
    }
    else{
    play(r+1, 0);
    }
}
else{
    if(needAtLoc(r,c).size()==0){//no possible moves THIS IS THE PROBLEM LINE!!!
    if(c>0){
        play(r, c-1);//play last cell, in column to left
    }
    else{
        if(r==0){
        play(r,c);//first square, so must play again (can't go back)
        }
        else{
        play(r-1, 8);/*first cell of row so must go to previous row and 
                   the end column*/
        }
    }
    }

    else{//if there are possible moves
    int num=needAtLoc(r,c).remove(generator.nextInt(needAtLoc(r,c).size()));
    setCell(r,c,num,this);//set the value of the cell
    System.out.println(this);//////////////
    if(r==8 && c==8){//the end of the cell has been reached so must end recursive call
        return;
    }
    else{
        if(c<8){
        play(r, c+1);//normal, next cell
        }
        else{
        play(r+1, 0);/*last cell in row so we go to next one 
                   in the first column ("return" button)*/
        }       
    }
    }
}
}

Answer 1

我不会为您解决这个问题，而是会就如何解决这个问题提出一些建议。 9个小时足够了。

1）你的代码很难阅读。尝试将其间隔开一点。为您的变量提供有意义且清晰的名称（这有助于您和其他人阅读您的代码）。您可能犯了一个简单的错误，干净的代码将使这些错误更容易被发现。尝试将其分解为更小的方法，因为这将使其更具可读性和更易于维护。

2）当您进行太多嵌套方法调用时，会导致堆栈溢出（我通常认为），并且在递归代码中很常见。因此，请明确您的递归。确保您有一个将终止的基本情况。

很抱歉没有给您“答案”，但由于这听起来像家庭作业，我认为学习如何自己解决这个问题更有价值。希望这看起来很公平。

Answer 2

我认为你的问题出在哪里：

if(r==0)
{
    play(r,c);//first square, so must play again (can't go back)
}

那是因为你似乎没有在这里修改任何状态，并且你传递了相同的值，使你首先来到这一步。对我来说似乎是无限递归。

另外，请正确对齐您的代码，因为当代码未对齐时很难阅读，也许可以提供一些其他方法的线索。祝你好运！

Answer 3

您的代码抛出堆栈溢出异常，因为您永远不会达到结束递归的终止条件，或者至少通过阅读代码您不会明显看到您有递归终止条件。

您的代码结构不好，因此您将很难调试它。尝试重构你的代码，它将帮助你重新思考问题。另外，请评论您的代码:)

Answer 4

您递归地调用 play 而不返回，看起来好像您每次都在函数顶部初始化一组新的变量。

尝试将初始化从递归部分中分离出来。您还需要一个明确的结束条件来结束递归，例如 (if(isBoardFilled()==true)) 返回。

还要构建它，以便您向板上添加一个数字，根据约束对其进行测试，如果通过，则添加另一个数字（递归）或通过删除最后一个数字进行回溯，然后重试。

Answer 5

我认为你正在递归地调用 play() 。尝试检查你的递归​​调用是否有停止条件。

Answer 6

我同意汤姆的观点，但这里有一个提示。

没有条件和返回语句来结束递归调用。

Answer 7

我已经设法变得更简洁、更清晰，但它仍然无法运行......我只需要推过边缘，然后我就可以回家了。我在这个项目中浪费了很多时间：

public ArrayList<Integer> needAtLoc(int r, int c){
    int bc=c/3;//the column within the SudokuBoard
    int blc;

    /*The two posibilities for the column within each SudokuBlock:*/
    if(c>=0 && c<3) {
        blc=c;
    }
    else {
        blc=c%3;
    }
    int br=r/3; //the row within the SudokuBoard
    int blr;

    /*The two possiblities for the row within each SudokuBlock:*/
    if(r>=0 && r<3) {
        blr=r;
    } else {
        blr=r%3;
    }
    ArrayList<Integer> needR = new ArrayList<Integer>();
    needR=checkR(r);//
    needR.trimToSize();
    System.out.println(needR);//////////////
    ArrayList<Integer> needC=new ArrayList<Integer>();
    needC=checkC(c);
    needC.trimToSize();
    System.out.println(needC);/////////////
    ArrayList<Integer> needBl=new ArrayList<Integer>();
    needBl=this.board[br][bc].updateMissing(); //that method updates and returns an ArrayList
    needBl.trimToSize();
    ArrayList<Integer> poss=new ArrayList<Integer>();
    poss.clear();
    for(Integer e: needBl){
        if(needC.contains(e) && needR.contains(e)){
            poss.add(e);
        }
    }

    return poss;
}

//this method throws the StackOverflowError
public void play(int r, int c){
    int bc=c/3; //the column within the SudokuBoard
    int blc;
    /*The two posibilities for the column within each SudokuBlock:*/
    if(c>=0 && c<3) {
        blc=c;
    } else {
        blc=c%3;
    }
    int br=r/3; //the row within the SudokuBoard
    int blr;

    /*The two possiblities for the row within each SudokuBlock:*/
    if(r>=0 && r<3) {
        blr=r;
    } else {
        blr=r%3;
    }
    if(needAtLoc(r,c).size()==9){
        int num=1+generator.nextInt(9);
        this.board[br][bc].setValue(blr, blc, num);
        if(c<8){
            System.out.println(this);///////////////
            play(r, c+1);
        } else{
            play(r+1, 0);
        }
    } else{
        if(needAtLoc(r,c).size()==0){ //no possible moves
            if(c>0){
                bc=(c-1)/3;
                if(c>0 && c<4) {
                    blc=c-1;
                } else {
                blc = (c-1) % 3;
            }
        this.board[br][bc].setValue(blr, blc, 0);
        play(r, c-1);
    }
    else{
        blc=0;
        bc=0;
        if(r==0){
        blr=0;
        br=0;
        this.board[br][bc].setValue(blr, blc, 0);
        play(r,c);
        }
        else{
        br=(r-1)/3;
        if(r>0 && r<4) {blr=r-1;}
        else {blr=(r-1)%3;}
        this.board[br][bc].setValue(blr, blc, 0);
        play(r-1, 8);
        }
    }
    }

    else{//if there are possible moves
        int num=needAtLoc(r,c).remove(generator.nextInt(needAtLoc(r,c).size()));
        this.board[br][bc].setValue(blr, blc, num);
        System.out.println(this);//////////////
        if(r==8 && c==8){
        return;
        }
        else{
        if(c<8){
            play(r, c+1);
        }
        else{
            play(r+1, 0);
        }       
        }
    }
    }
}