-2

This link has a Backtracking implementation of the Sudoku Solver algorithm. Notice how line number 42, reverts the value initially assigned to a cell, to another value, in case the initially assigned value did not give a valid output.

However, I don't understand how merely changing the value of that cell alone is sufficient. This call could've triggered many other calls, and since arrays (matrices) are passed by memory (reference), it does not keep a copy of the matrix (grid[N][N]) at every invocation of the recursive function, and so changes till the base case of the recursion will reflect even in the first frame of recursion by the time it returns back.

According to me, just before calling the recursive function, you should make a temporary copy of grid[N][N] and restore it as soon as the call gets returned, and before the next function in the same frame is called.

Something like

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;
        }
    }

Please help me understand this detail.

4

1 回答 1

3

它正在保存状态：每个递归调用都将状态保存在调用堆栈上。

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

这是一个蛮力求解器。您可能也想在周围搜索一下。

希望这可以帮助。

于 2016-07-18T02:29:56.963 回答