我的C#数独求解器无法输出解？递归逻辑问题排查求助

这是我的第一篇帖子，若有不当之处敬请谅解。我接触编程数月，最初使用Python，现在转用C#。为学习回溯算法，我尝试编写数独求解器，但始终无法理解代码为何无法正常运行。我知道已有很多现成解决方案，但目前我认为理解自己代码中的缺失是最好的进步方式。

问题：为何我的代码无法返回已解的数独棋盘？我怀疑问题出在递归部分。

运行结果：代码会两次输出原始未解的数独棋盘，似乎初始运行正常，但中途所有内容都重置回原始状态。

我的代码 #

主程序 #

using System;

namespace Sudoku
{
    class Program
    {
        static void Main(string[] args)
        {          
            
            var sudokuTemplate = new SudokuTemplate();
            var sudoku = sudokuTemplate.CreateSudoku();
            Print.print(sudoku);
            Console.WriteLine();
            Print.print(driver(sudoku));
        }    

        static int[,] driver(int[,] board)
        {
            var check = new ErrorCheck();

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (board[i,j] == 0)
                    {   
                        for (int n = 1; n <= 9; n++)
                        {
                            if (check.legal(board, i, j, n))
                            {
                                board[i, j] = n;  
                                driver(board); 
                            }   
                            else
                            {
                                board[i, j] = 0;
                            }                         
                        } 
                        return board;                      
                    }                  
                }
            }
            return board;
        }
    }
}

未解数独模板 #

namespace Sudoku
{
    class SudokuTemplate
    {
        public int[,] CreateSudoku()
        {
            var array = new int[,] 
            {
                {5,3,0,0,7,0,0,0,0},  
                {6,0,0,1,9,5,0,0,0},  
                {0,9,8,0,0,0,0,6,0},  
                {8,0,0,0,6,0,0,0,3},  
                {4,0,0,8,0,3,0,0,1},  
                {7,0,0,0,2,0,0,0,6},  
                {0,6,0,0,0,0,2,8,0},  
                {0,0,0,4,1,9,0,0,5},  
                {0,0,0,0,8,0,0,7,9}  
            };
            return array;
        }
    }
}

合法性检查类（判断数字n是否可放置） #

namespace Sudoku
{
    public class ErrorCheck
    {
        public bool legal(int[,]array, int row, int col, int n)
        {   //check col & row
            for (int i = 0; i < 9; i++)
            {
                if (array[row, i] == n)
                {
                    return false;
                }
                if (array[i, col] == n)
                {
                    return false;
                }
            }

            //check boxes
            int valRow = 0;
            if (row < 6 && row > 2)
            {
                valRow = 3;
            }
            else if (row < 9 && row > 5)
            {
                valRow = 6;
            }

            int valCol = 0;
            if (col < 6 && col > 2)
            {
                valCol = 3;
            }
            else if (col < 9 && col > 5)
            {
                valCol = 6;
            }
            
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (array[(j+valRow), (i+valCol)] == n)
                        {
                            return false;
                        }
                }
            }
            return true;
        }   
        
    }
}

打印函数 #

namespace Sudoku
{
    class Print
    {
        public static void print(int[,] array)
        {
            // prints sudoku
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++) 
                {
                    Console.Write("{0} ", array[i, j]);
                    Console.Write("|");     
                }
                Console.WriteLine();
            }
            
        }
    }
}

问题分析与修复 #

你的递归逻辑存在几个关键问题：

1. 递归调用后未判断求解状态：调用driver(board)后，不管递归是否成功解出数独，代码都会继续尝试下一个数字，最终重置当前格子为0，覆盖之前的递归结果。
2. 错误的回溯时机：在else分支直接重置格子为0是错误的，应该是递归发现当前数字无法得到解时，再回溯重置。
3. 缺乏终止反馈：数独填满时没有返回成功标记，上层递归无法停止尝试其他数字。

修复后的driver方法 #

static bool driver(int[,] board)
{
    var check = new ErrorCheck();

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (board[i,j] == 0)
            {   
                for (int n = 1; n <= 9; n++)
                {
                    if (check.legal(board, i, j, n))
                    {
                        board[i, j] = n;  
                        // 递归成功则向上返回true，终止上层尝试
                        if (driver(board))
                        {
                            return true;
                        }
                        // 递归失败，回溯重置当前格子
                        board[i, j] = 0;
                    }                         
                } 
                // 所有数字都尝试过无解，返回false
                return false;                      
            }                  
        }
    }
    // 无空格子，求解完成
    return true;
}

主函数修改 #

因为driver现在返回布尔值表示是否成功，主函数需调整：

static void Main(string[] args)
{          
    var sudokuTemplate = new SudokuTemplate();
    var sudoku = sudokuTemplate.CreateSudoku();
    Print.print(sudoku);
    Console.WriteLine();
    
    if (driver(sudoku))
    {
        Print.print(sudoku);
    }
    else
    {
        Console.WriteLine("数独无解");
    }
}

额外优化：方块起始索引计算 #

原合法性检查中的方块起始行/列计算可简化，避免条件判断：

// 替换原来的valRow和valCol计算逻辑
int valRow = (row / 3) * 3;
int valCol = (col / 3) * 3;

该方式通过整数除法直接得到3x3方块的起始索引，逻辑更简洁且不易出错。

内容的提问来源于stack exchange，提问作者badcoder_94