C# 数独求解算法的实现

本文将详细讲解如何使用C#语言实现数独求解算法。

数独简介

数独是一种逻辑类的游戏，玩家需要在9*9宫的大九宫格中，填入数字1~9，使每行、每列、每个小九宫格内都恰好包含数字1~9，且不重复。

算法思路

数独求解算法的基本思路是采用回溯算法。从数独的左上角开始，依次尝试填入1~9的数字，若当前填入的数字满足数独条件，则进入下一格继续填入数字；否则回溯到上一格重新填入数字。当填完数独的最后一格时，判断数独是否已成功求解。

算法实现

数独数据结构设计

我们首先需要定义数独的数据结构，以便于进行算法实现。数独的数据结构应该包含以下信息：

• 二维数组grid：表示数独的状态，0表示该格尚未填入数字，1~9表示当前格填入的数字。
• HashSet数组rows、cols、blocks：分别表示每一行、每一列、每一个小九宫格内已出现的数字。

public class Sudoku
{
    private int[][] grid;
    private HashSet<int>[] rows;
    private HashSet<int>[] cols;
    private HashSet<int>[] blocks;
}

初始化数独数据结构

对于数独，我们需要先将其数据结构进行初始化。具体来说，对于每一个元素(grid[i][j])：

• 将该元素所在的行(rows[i])、列(cols[j])、小九宫格(blocks[i/3][j/3])都加入到HashSet中，表示这些数字已在数独中出现过。
• 如果该元素不为0，则将其加入到以上的三个HashSet中。

public void Initialize(int[][] board)
{
    grid = board;

    rows = new HashSet<int>[9];
    cols = new HashSet<int>[9];
    blocks = new HashSet<int>[9];
    for (int i = 0; i < 9; i++)
    {
        rows[i] = new HashSet<int>();
        cols[i] = new HashSet<int>();
        blocks[i] = new HashSet<int>();
    }

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (board[i][j] != 0)
            {
                rows[i].Add(board[i][j]);
                cols[j].Add(board[i][j]);
                blocks[i / 3 * 3 + j / 3].Add(board[i][j]);
            }
        }
    }
}

回溯算法实现

数独求解的具体实现方法，是通过回溯算法实现的。为方便实现，我们将回溯算法定义为递归函数：

public bool Solve(int i, int j)
{
    if (j == 9)
    {
        i++;
        j = 0;
        if (i == 9)
        {
            return true; // 数独已成功求解
        }
    }

    if (grid[i][j] != 0)
    {
        return Solve(i, j + 1);
    }

    for (int num = 1; num <= 9; num++)
    {
        if (!rows[i].Contains(num) && !cols[j].Contains(num) && !blocks[i / 3 * 3 + j / 3].Contains(num))
        {
            grid[i][j] = num;
            rows[i].Add(num);
            cols[j].Add(num);
            blocks[i / 3 * 3 + j / 3].Add(num);

            if (Solve(i, j + 1))
            {
                return true;
            }

            grid[i][j] = 0;
            rows[i].Remove(num);
            cols[j].Remove(num);
            blocks[i / 3 * 3 + j / 3].Remove(num);
        }
    }
    return false;
}

算法的每一次递归都尝试填入1~9中的一个数字，若填入的数字合法，则进入下一格继续回溯；否则回溯到上一格重新填入数字，直至所有格子都填满。

示例说明

假设下面是一个未解决的数独：

0 0 0 0 0 0 0 6 7
0 9 0 0 0 0 8 0 3
8 5 0 7 0 0 0 0 0
4 0 0 0 9 0 0 0 0
0 3 0 0 7 0 0 8 5
0 0 0 0 0 0 4 1 0
0 7 1 0 5 0 0 0 0
0 0 0 0 1 0 3 0 9
5 0 2 0 0 0 0 7 0

我们可以使用以下代码进行求解：

static void Main(string[] args)
{
    int[][] board = new int[9][];
    board[0] = new int[] { 0, 0, 0, 0, 0, 0, 0, 6, 7 };
    board[1] = new int[] { 0, 9, 0, 0, 0, 0, 8, 0, 3 };
    board[2] = new int[] { 8, 5, 0, 7, 0, 0, 0, 0, 0 };
    board[3] = new int[] { 4, 0, 0, 0, 9, 0, 0, 0, 0 };
    board[4] = new int[] { 0, 3, 0, 0, 7, 0, 0, 8, 5 };
    board[5] = new int[] { 0, 0, 0, 0, 0, 0, 4, 1, 0 };
    board[6] = new int[] { 0, 7, 1, 0, 5, 0, 0, 0, 0 };
    board[7] = new int[] { 0, 0, 0, 0, 1, 0, 3, 0, 9 };
    board[8] = new int[] { 5, 0, 2, 0, 0, 0, 0, 7, 0 };

    Sudoku s = new Sudoku();
    s.Initialize(board);
    bool solved = s.Solve(0, 0);

    if (solved)
    {
        Console.WriteLine("数独已成功求解：");
        for(int i=0;i<9;i++)
        {
            for (int j = 0; j < 9; j++)
            {
                Console.Write("{0} ", s.Get(i, j));
            }
            Console.WriteLine();
        }
    }
    else
    {
        Console.WriteLine("数独无解！");
    }
    Console.ReadKey();
}

程序输出结果为：

数独已成功求解：
2 4 3 5 8 1 9 6 7 
6 9 7 2 4 3 8 5 3 
8 5 1 7 6 9 2 3 4 
4 1 5 8 9 2 7 3 6 
9 3 6 4 7 5 1 8 5 
7 2 8 3 6 1 4 1 9 
3 7 1 9 5 4 6 2 8 
0 0 0 0 1 0 3 0 9 
5 6 2 1 3 8 1 7 0 

上面就是数独求解算法的实现过程。对于更加复杂的数独问题，我们可以使用类似的算法进行求解。