c++ - 空数独填充器 C++

Question

我正在开发一个程序，该程序用数独板的正确值填充空的 9x9 数组。我的验证方法是有效的，因为我已经通过简单的迭代回溯方法对其进行了测试。 我目前的方法是随机选择一行和一列并放置适当的值，我还通过使用递归来实现回溯。这是我的求解器函数:

void solve (int board[9][9]) {

    static int counter = 0;
    int val = 0;
    int row = 0;
    int col = 0;

    if (counter == 81) {
        print (board, counter);
        exit(1);
    }

    while (1) {
        row = rand() % 9;
        col = rand() % 9;
        if (board[row][col] == 0)
            break;
    }

    ++counter;
    for (int i = 1; i < 10; i++) {
        val = i;
        if (ok (board, row, col, val)) {
            board[row][col] = val;
            solve (board);
        }
    }
    --counter;
}

现在我遇到的问题是我从未达到 81，我的函数在此之前终止，我假设堆栈变空并返回到 main。你能帮我理解我犯了什么错误吗？谢谢。

Answer 1

当您尝试用适当的值填充数独网格时，您最终会陷入死锁:在不违反数独规则的情况下无法填充您尝试查找值的单元格的情况。作为一个简单的示例，考虑一个网格，其中第一行是 [x, 2, 3, 4, 5, 6, 7, 8, 9]，第一列是 [x, 1, 8, 2, 3, 4, 5, 6, 7]。 x不能填写，其他值均符合规则。

在您的情况下，当发生死锁时，从 1 到 9 的任何值都不满足 ok 条件，并且执行会返回一层递归，到上一个单元格，其中已经选择了一个值。在那里，该函数尝试下一个可能的值。

对于已经有值的单元格发生死锁(即多级死锁)时，执行会再次返回一层递归，但值仍然存在。由于这些“幽灵”值，这会导致后续的 ok 条件在应该成功时失败。对于简单的死锁，不会出现该问题，因为该值保持为 0。

在for循环之后，需要将board[row][col]的值设置回0。