运行27次后的StackOverflow

Question

当运行我的数独生成器时，在得到堆栈溢出27次之后。

void start(int todel){
int number;
for (int x=0; x<9; x++) {
    for (int y=0; y<9; y++) {

        number = GenN(x, y);
        osudoku[x][y]=number;
    }
}
replace(todel);
output();
}


int GenZ(int x, int y){
    int number;
    bool duplication = true;
    Randomize();
    number = Random(9)+1;
    duplication = check(number,x,y);
    if (duplication==true){
        return GenZ(x,y);
    }
    else if (duplication==false) {
        return number;
    }
}

我想是这段代码的问题。它会生成如下内容：

758 431 629 
913 267 485 
642 985 317
Stack Overflow

所以我得到了1/3的数独。

Answer 1

您需要将backtracking添加到解决方案中。

考虑这个场景：(这可能会在你的算法中的某个时刻发生)

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 1 2 3 | ? _ _
...

您的程序将继续尝试查找适合?的值，但并不存在这样的值。

相反，您的程序需要查看没有匹配的值，并尝试3的不同值，这也不起作用，然后是2，然后是1，在这种情况下，它最终应该将7、8和9放在第二个块中，如下所示：

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | ? _ _
...

在这种情况下，它可以成功地继续。

还有这个：

zahl = Random(9)+1;

不会真正起作用，因为您可能会不断获得不符合的值(如上例所示)。你不会知道什么时候该回溯。最好遍历所有9个值。在遍历了所有9个值之后，您将知道没有一个值适合您，并且您将知道您必须回溯。

Answer 2

如果在GenZ中使用duplication==true，它将使用相同的x，y再次调用它，这将再次生成duplication==true？特别是因为我看不到你修改"number“，所以它可能是它的初始化值，比如0。

Answer 3

if (duplication==true){
    return GenZ(x,y);
}

我不确定这是否是创建数独的可行方法，无论您如何实现，暴力强制都可能需要一段时间，但您可以通过不使用递归和使用循环来消除堆栈溢出错误。

while (duplication){