C#数独求解：基于回溯算法的面向对象实现

拾光

发布时间：2026-10-16 | 5人浏览过

原创

数独是一种经典逻辑游戏，要求根据已知数字推理出剩余空格的数值。本文将展示如何运用C#面向对象特性，结合基础的回溯算法高效解决这一问题。通过完整的类封装与代码解析，帮助开发者理解递归在逻辑解题中的应用。

数独求解的核心逻辑

数独（Sudoku）源自18世纪的瑞士，属于一种运用纸笔演算的逻辑游戏。其核心规则在于一个9×9的九宫格内，每一行、每一列以及每一个3×3的粗线宫内，必须包含1到9的数字且不重复。求解数独即是在给定部分初始数字的前提下，推断出所有空白位置的正确数值。

计算机求解此类问题的常用方法是"回溯法"（Backtracking）。该算法模拟人类试错的过程：选择一个空格，填入当前合法的最小数字，若后续出现矛盾则回退（Backtrack），尝试下一个数字。虽然简单的回溯并非最高效的解法，但其代码结构直观，易于理解和实现，非常适合用于算法入门和教学。

C#面向对象实现方案

为了提升代码的可读性与复用性，我们将数独状态和求解逻辑封装为一个 Sudoku 类。以下是完整的C#实现代码：

class Sudoku
{
    public int[,] Numbers { get; set; }
    int x;
    int y;

    // 构造函数：初始化棋盘数据并定位第一个待填空格
    public Sudoku(int[,] num)
    {
        Numbers = num;

        for (x = 0; x < 9; x++)
        {
            for (y = 0; y < 9; y++)
            {
                if (Numbers[x, y] == 0)
                    return;
            }
        }
    }

    // 属性：判断是否所有格子已填满
    public bool IsCompleted { get { return x == 9 && y == 9; } }

    // 核心方法：递归求解
    public Sudoku CaluSudoKu()
    {
        if (IsCompleted)
            return this;

        // 获取当前空格可填的所有有效数字
        foreach (var num in GetAvaibleNumbers())
        {
            var tmpData = Numbers.Clone() as int[,];
            tmpData[x, y] = num;

            var sudouku = new Sudoku(tmpData);
            var ret = sudouku.CaluSudoKu();

            if (ret != null)
                return ret;
        }

        return null; // 无法求解时返回null
    }

    // 辅助方法：计算当前(x,y)位置可用数字集合
    int[] GetAvaibleNumbers()
    {
        var set = new HashSet<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
        
        // 排除同行同列已存在的数字
        for (int i = 0; i < 9; i++)
        {
            set.Remove(Numbers[x, i]);
            set.Remove(Numbers[i, y]);
        }

        // 排除所在3x3宫内已存在的数字
        int xStart = x - x % 3;
        int yStart = y - y % 3;

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                set.Remove(Numbers[i + xStart, j + yStart]);
            }
        }

        return set.ToArray();
    }
}

代码结构与运行原理

第1步：状态初始化与定位

目的：确保每次递归调用都能正确处理当前的棋盘状态。
动作：构造函数接收一个9×9的整数数组 int[,]，其中0代表空格。通过双重循环扫描，找到第一个值为0的坐标 (x, y)。
结果：若未找到0，说明棋盘中无空格，此时 x=9, y=9，可通过 IsCompleted 属性判断求解结束。

第2步：可行性分析与剪枝

入口：调用 GetAvaibleNumbers() 方法。
参数：当前坐标 x, y 及棋盘数据 Numbers。
逻辑：初始化一个包含1-9的哈希集合。首先剔除当前行和列中已出现的数字；接着计算当前格子所属3×3宫的起始坐标 xStart 和 yStart，再次剔除宫内已有数字。最终返回剩余可用的数字数组。

第3步：递归回溯执行

操作：在 CaluSudoKu() 方法中，遍历所有可用数字。对每个数字：
1. 克隆当前棋盘数据 tmpData；
2. 将数字填入 tmpData[x, y]；
3. 创建新的 Sudoku 实例进行下一层递归。
完成判断：若递归返回非空对象 ret，说明找到了完整解，直接向上返回该结果；若循环结束仍未找到可行解，返回 null 触发上一级的回溯（尝试下一个数字或返回false）。