在 C# 中没有触发回溯

Question

我正在尝试用 c# 为数独求解器编写代码。但似乎递归没有正常工作，回溯也没有被解雇。

当我在 row 为 1 且 col 为 7 时尝试调试代码时，它应该开始展开并且执行应该到来 "grid[row,col] = 0;" 此处没有执行

以下是我的代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3
{
class solver
{

    static int N = 9;
    static int[,] grid = new int[9, 9]
        {{0,0,2,4,5,0,1,9,0},
         {0,0,0,3,0,0,0,0,0},
         {7,5,0,9,0,2,3,0,0},
         {9,2,5,0,3,0,0,8,6},
         {0,0,4,0,0,0,9,0,0},
         {1,8,0,0,9,0,4,3,5},
         {0,0,3,6,0,5,0,7,1},
         {0,0,0,0,0,9,0,0,0},
         {0,4,8,0,1,3,6,0,0}
        };


    //int a=10;
    static int row = 0, col = 0;
    public static void Main()
    {

        if (solveSudoku())
        {
            for (int r = 0; r < 9; r++)
            {
                for (int c = 0; c < 9; c++)
                {
                    Console.Write(" " + grid[r, c] + " ");
                }
                Console.WriteLine();
            }

            Console.ReadLine();
        }
        else
        {
            Console.Write("OOPs");
            Console.ReadLine();
        }

    }

    static Boolean solveSudoku()
    {

        if (!FindUnassigned())
        {
            return true;
        }

        for (int num = 1; num <= 9; num++)
        {
            if (isSafe(num))
            {
                grid[row, col] = num;
                if (solveSudoku())
                {
                    return true;
                }
                grid[row,col] = 0;
            }
        }
        //triggers backtracking
        return false;
    }

    static Boolean FindUnassigned()
    {
        for (row = 0; row < 9; row++)
        {
            for (col = 0; col < 9; col++)
            {
                if (grid[row, col] == 0)
                    return true;
            }
        }
        return false;
    }
    static Boolean isSafe(int num)
    {
        return (!UsedInRow(num) &&
       !UsedInCol(num) &&
       !UsedInBox(row-row%3, col-col%3,num));

    }
    static Boolean UsedInRow(int num)
    {
        for (int c = 0; c < 9; c++)
            if (grid[row,c] == num)
                return true;
        return false;
    }
    static Boolean UsedInCol(int num)
    {
        for (int r = 0; r < 9; r++)
            if (grid[r, col] == num)
                return true;
        return false;
    }
    static bool UsedInBox( int boxStartRow, int boxStartCol, int num)
        {
            for (int row = 0; row < 3; row++)
                for (int col = 0; col < 3; col++)
                    if (grid[row+boxStartRow,col+boxStartCol] == num)
                        return true;
            return false;
        }
    }
}`

Answer 1

这里的基本问题正如评论者 EBrown 和 Servy 所解释的那样：使用递归方法修改全局状态通常不是您想要的。

请注意，递归的主要好处是保存每次新的递归调用时发生的状态。也就是说，新的调用创建了新的状态，但是之前的所有状态都被保留了下来。但是，请注意，唯一保留的状态是存储在本地调用帧中的状态。

递归方法本身甚至不知道它们是递归的，更不用说它们能否神奇地知道在进行时保存全局状态。因此，当您在递归实现中修改非本地 row 和 col 变量时，您没有任何方法可以恢复它们以前的状态，因为递归方法会回溯。

相反，您想要的是 solveSudoku() 方法的每次递归迭代，以在局部变量中保持 row 和 col 状态。这样，如果算法在没有解决难题的情况下到达终止情况（即它找到一个没有可能值的未分配元素），它可以回溯并在 previously[=45 中尝试不同的数字=] 被认为是空元素。

修复代码相对容易。我所做的只是注释掉非本地 row 和 col 变量，将它们改为 out 方法的 FindUnassigned() 参数（这是您用来扫描的方法第一个空元素的板）。然后剩下的编译错误我简单地通过添加 row and/or col 适当地添加到每个使用它们的方法，并从调用者传递值来修复。

我鼓励你尝试这个练习，这样你就会知道它是如何工作的。但是，为了完整起见，我在下面包含了我的代码版本：

//static int N = 9; static int[,] grid = new int[9, 9] {{0,0,2,4,5,0,1,9,0}, {0,0,0,3,0,0,0,0,0}, {7,5,0,9,0,2,3,0,0}, {9,2,5,0,3,0,0,8,6}, {0,0,4,0,0,0,9,0,0}, {1,8,0,0,9,0,4,3,5}, {0,0,3,6,0,5,0,7,1}, {0,0,0,0,0,9,0,0,0}, {0,4,8,0,1,3,6,0,0} }; //int a=10; //static int row = 0, col = 0; public static void Main() { if (solveSudoku()) { for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { Console.Write(" " + grid[r, c] + " "); } Console.WriteLine(); } Console.ReadLine(); } else { Console.Write("OOPs"); Console.ReadLine(); } } static Boolean solveSudoku() { int row, col; if (!FindUnassigned(out row, out col)) { return true; } for (int num = 1; num <= 9; num++) { if (isSafe(num, row, col)) { grid[row, col] = num; if (solveSudoku()) { return true; } } } grid[row, col] = 0; //triggers backtracking return false; } static Boolean FindUnassigned(out int row, out int col) { for (row = 0; row < 9; row++) { for (col = 0; col < 9; col++) { if (grid[row, col] == 0) return true; } } row = col = -1; return false; } static Boolean isSafe(int num, int row, int col) { return (!UsedInRow(num, row) && !UsedInCol(num, col) && !UsedInBox(row - row % 3, col - col % 3, num)); } static Boolean UsedInRow(int num, int row) { for (int c = 0; c < 9; c++) if (grid[row, c] == num) return true; return false; } static Boolean UsedInCol(int num, int col) { for (int r = 0; r < 9; r++) if (grid[r, col] == num) return true; return false; } static bool UsedInBox(int boxStartRow, int boxStartCol, int num) { for (int row = 0; row < 3; row++) for (int col = 0; col < 3; col++) if (grid[row + boxStartRow, col + boxStartCol] == num) return true; return false; }

备注：

只需要在solveSudoku()方法即将returnfalse时将空元素重置为0即可。在任何其他情况下，循环的下一次迭代无论如何都会覆盖当前值，并且当您调用 isSafe() 时先前的无效值仍然存在不会干扰该方法的操作。我已经在上面进行了更改。

我没有费心实际检查输出。对于暴力数独求解器，该代码似乎是合理正确的，但我不保证您的代码中是否还有其他错误。

同样的，其他的优化机会我也没有在这里评论过。我只是提供有关如何使基本想法发挥作用的信息。

在 C# 中没有触发回溯

Backtracking not getting triggered in c#

c#

sudoku