尽管不存储状态，这个数独求解器的实现是如何工作的？

Question

This link 具有数独求解器算法的回溯实现。请注意第 42 行如何将最初分配给单元格的值还原为另一个值，以防最初分配的值未提供有效输出。

但是，我不明白仅更改该单元格的值如何就足够了。此调用可能会触发许多其他调用，并且由于数组（矩阵）是通过内存（引用）传递的，因此它不会保留矩阵的副本（网格[N][N ]) 在递归函数的每次调用中，因此会发生变化，直到递归的基本情况在 returns 返回时甚至会反映在递归的第一帧中。

根据我的说法，就在调用递归函数之前，您应该制作一个临时副本 grid[N][N] 并在调用返回后立即恢复它，并且在同一帧中的下一个函数之前被调用。

类似

for (int num = 1; num <= N; num++)
    {
        // if looks promising
        if (isSafe(grid, row, col, num))
        {
            //save grid state
            int[][] temp = new int[N][N];
            save(temp,grid); //copy all values from grid to temp             

            // make tentative assignment
            grid[row][col] = num;

            // return, if success, yay!
            if (SolveSudoku(grid))
                return true;

            //restore grid state           
            restore(temp,grid); //copy all values from temp back to grid

            // failure, unmake & try again
            grid[row][col] = UNASSIGNED;
        }
    }

请帮助我理解这个细节。

Answer 1

它是保存状态：每次递归调用都会在调用堆栈上保存状态。

修改网格中未分配的部分，直到找到有效的解决方案。一旦完成，所有堆叠函数调用都将终止（第 38 和 39 行），使 grid[][] 处于已解决状态。如果不是，它将当前单元格恢复为其 UNASSIGNED 值并尝试下一个可能的值。

这是一个强力求解器。您可能也想 google 解决这个问题。

希望对您有所帮助。

尽管不存储状态，这个数独求解器的实现是如何工作的？

How does this implementation of Sudoku solver work in spite of not storing state?

c++

recursion

pass-by-reference

backtracking

recursive-backtracking