java - Sudoku Solver暴力算法

Question

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

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

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

对于没有最终预定义数字的方 block ，求解器函数如下:

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 值是方 block 在棋盘上代表的值。 currentPos 变量是一个计数器，从 1 开始递增，直到达到要表示的正方形的合法值。

对于具有预定义数字的方 block ，这里有相同的函数:

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.");
    }
}

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

非常感谢任何帮助!也可以随意选择我的代码；我还在学习(哦，我们不总是这样吗？)。

___________________编辑______< em>__________

感谢提出回溯这个好主意的 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 数独 :)

你能发现我的错误吗？感谢您的帮助!

Answer 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。