0

仍在研究我的数独求解器，我又遇到了一些麻烦。我已经让数独求解器工作了，但是每当我尝试求解一个真正“硬”的数独板时，我的求解器都会告诉我，由于堆栈溢出错误，没有可能的解决方案。是的，我知道这些板确实有解决方案。

我正在使用蛮力算法——我从第一格开始（或 [0][0]，如果您愿意）并插入第一个合法值。然后我对下一个方块进行递归调用，依此类推。如果我的函数没有遍历整个棋盘，并且发现没有可能的合法值，它会移动到前一个方块并尝试增加那里的值。如果失败，它会向后移动。如果它在没有可能的解决方案的情况下结束于第一格，它就会退出。

我承认我的代码并不漂亮，而且可能非常低效，但请记住，我是一名一年级学生，正在努力做到最好。我不介意评论如何使我的代码生效:)

对于没有最终预定义数字的正方形，这里是求解器函数：

public void fillRemainderOfBoard(Square sender){

    try {

        while(true){
            if(currentPos > boardDimension){
                if(previous != null){
                    this.setNumrep(-1);
                    this.setCurrentPos(1);
                    previous.setCurrentPos(previous.getCurrentPos()+1);
                    previous.fillRemainderOfBoard(this);
                    return;
                } else if(sender == this){
                    this.setCurrentPos(1); 
                } else {
                    break;
                }
            }
            if((thisBox.hasNumber(currentPos)) || (thisRow.hasNumber(currentPos)) || (thisColumn.hasNumber(currentPos))){
                currentPos++;
            } else {
                this.setNumrep(currentPos);
                currentPos++;
                break;
            }
        }

        if(this != last){
            next.setNumrep(-1);
            next.fillRemainderOfBoard(this);
        } else {

            return;
        }
    } catch (StackOverflowError e){
        return;
    }
}

在我的代码中，numrep 值是方块在板上表示的值。currentPos 变量是一个计数器，从 1 开始并递增，直到达到正方形表示的合法值。

对于具有预定义数字的正方形，这是相同的功能：

public void fillRemainderOfBoard(Square sender){
    if((sender.equals(this) || sender.equals(previous)) && this != last){
        System.out.println(next);
        next.fillRemainderOfBoard(this);
    } else if (sender.equals(next) && this != first) {
        previous.fillRemainderOfBoard(this);
    } else {
        System.out.println("No possible solutions for this board.");
    }
}

现在，我的问题是，就像我说的，这个函数确实很好地解决了数独问题。容易的。棘手的数独，比如有许多预定义数字但只有一个解决方案的数独，只会让我的程序进入堆栈溢出并告诉我没有可能的解决方案。我假设这表明我在内存管理方面遗漏了一些东西，或者程序复制了我在递归函数中调用的对象，但我不知道如何修复它们。

任何帮助是极大的赞赏！也可以随意选择我的代码；我还在学习（哦，我们不是总是这样吗？）。

__ _ __ _ __ _ __ _ __ _ ____编辑_ __ _ __ _ __ _ __ _ __ _

感谢 Piotr 提出了回溯的好主意，我重写了我的代码。但是，我仍然无法解决任何数独问题。即使是空棋盘，它也会到达 39 号方格，然后一直返回 false。这是我当前的代码：

public boolean fillInnRemainingOfBoard(Square sender){
    if(this instanceof SquarePredef && next != null){
        return next.fillInnRemainingOfBoard(this);
    } else if (this instanceof SquarePredef && next == null){
        return true;
    }

    if(this instanceof SquareNoPredef){
        currentPos = 1;
        if(next != null){
            System.out.println(this.index);
            for(; currentPos <= boardDimension; currentPos++){
                if((thisBox.hasNumber(currentPos)) || (thisRow.hasNumber(currentPos)) || (thisColumn.hasNumber(currentPos))){
                    continue;
                } else {
                    System.out.println("Box has " + currentPos + "? " + thisBox.hasNumber(currentPos));
                    this.setNumrep(currentPos);
                    System.out.println("Got here, square " + index + " i: " + numrep);
                }

                if(next != null && next.fillInnRemainingOfBoard(this)){
                    System.out.println("Returnerer true");
                    return true;
                } else {

                }
            }
        }
        if(next == null){
            return true;
        }
    }
    System.out.println("Returning false. Square: " + index + " currentPos: " + currentPos);
    return false;
}

我不得不使事情复杂一点，因为我需要检查当前对象是否是最后一个。因此额外的 if 测试。哦，我使用 boardDimension 的原因是因为这个数独求解器可以解决任何数独问题——不仅仅是那些 9 x 9 数独 :)

你能发现我的错误吗？任何帮助表示赞赏！

4

1 回答 1

1

所以你的问题出在这里：

previous.fillRemainderOfBoard(this);

和这里

next.fillRemainderOfBoard(this);

基本上你在堆栈上有太多的函数调用，因为你要向前和向后多次。在找到答案之前，您并没有真正从任何电话中返回（或者您得到 StackOverflowError :)）。不要通过使用递归函数来增加堆栈大小，而是尝试考虑如何使用循环来解决问题（几乎总是循环比递归解决方案的性能更好）。好的，所以你可以做这样的事情（伪代码）：

boolean fillRemainderOfBoard(Square sender){
 if (num_defined_on_start) {
     return next.fillRemainderOfBoard(this);
 } else {
   for (i = 1; i < 9; ++i) {
     if (setting i a legal_move)
        this.setCurrentPos(i);
     else
        continue;
     if (next.fillRemainderOfBoard(this))
       return true;
   }
   return false;
}

堆栈大小约为 81。

于 2013-04-12T23:01:26.877 回答