3

所以我有我认为在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)*/
        }       
    }
    }
}
}
4

7 回答 7

26

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

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

2）当您进行太多嵌套方法调用并且在递归代码中很典型时，会导致堆栈溢出（通常我相信）。因此，使您的递归清晰。确保您有一个将终止的基本案例。

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

于 2009-12-17T06:20:02.870 回答
3

我认为你的问题是你有：

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

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

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

于 2009-12-17T11:37:15.120 回答
1

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

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

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

于 2009-12-17T06:56:10.343 回答
1

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

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

于 2009-12-17T06:30:15.657 回答
0

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

于 2009-12-17T06:25:24.607 回答
0

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

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

于 2009-12-17T06:35:52.713 回答
0

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

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);
        }       
        }
    }
    }
}
于 2009-12-17T09:40:32.593 回答