C#实现数独解法

简介

数独游戏是一种经典的逻辑推理游戏。在9*9个方格中，按照一定的规则填入数字，使得每行、每列、每宫都含有1-9的数字且不重复。本文将介绍如何使用C#实现数独解法。

准备

在开始编写代码之前，先准备好一个数独问题作为输入。例如：

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

其中0代表空格。

实现

首先，我们需要定义一个Sudoku类，表示数独游戏的状态。

class Sudoku
{
    private int[,] board; // 数独面板，9*9的二维数组

    public Sudoku(int[,] board)
    {
        this.board = board;
    }

    // 返回第i行j列的数字。0表示空格。
    public int Get(int i, int j)
    {
        return board[i, j];
    }

    // 设置第i行j列的数字。
    public void Set(int i, int j, int value)
    {
        board[i, j] = value;
    }

    // 返回第i行的数字列表。
    public IEnumerable<int> GetRow(int i)
    {
        for (int j = 0; j < 9; j++)
        {
            yield return Get(i, j);
        }
    }

    // 返回第j列的数字列表。
    public IEnumerable<int> GetCol(int j)
    {
        for (int i = 0; i < 9; i++)
        {
            yield return Get(i, j);
        }
    }

    // 返回第k宫的数字列表。
    public IEnumerable<int> GetBox(int k)
    {
        int boxi = (k / 3) * 3; // 宫的左上角行号
        int boxj = (k % 3) * 3; // 宫的左上角列号
        for (int i = boxi; i < boxi + 3; i++)
        {
            for (int j = boxj; j < boxj + 3; j++)
            {
                yield return Get(i, j);
            }
        }
    }

    // 返回下一个空格的行列号。（如果已经填满了，返回null）
    public Tuple<int, int> Next()
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (Get(i, j) == 0)
                {
                    return Tuple.Create(i, j);
                }
            }
        }
        return null;
    }

    // 判断给定的数字是否合法。
    public bool IsValid(int i, int j, int value)
    {
        if (Get(i, j) != 0)
        {
            return false; // 非空格不可填
        }
        if (GetRow(i).Contains(value))
        {
            return false; // 同一行不能重复
        }
        if (GetCol(j).Contains(value))
        {
            return false; // 同一列不能重复
        }
        if (GetBox(i / 3 * 3 + j / 3).Contains(value))
        {
            return false; // 同一宫不能重复
        }
        return true;
    }

    // 返回解决本数独问题的一个解（如果存在）。
    public Sudoku Solve()
    {
        Tuple<int, int> next = Next();
        if (next == null)
        {
            return this; // 已经解决了
        }
        int i = next.Item1;
        int j = next.Item2;
        for (int value = 1; value <= 9; value++)
        {
            if (IsValid(i, j, value))
            {
                Sudoku child = new Sudoku((int[,])board.Clone()); // 复制一个新的数独状态
                child.Set(i, j, value); // 填上一个值
                Sudoku solved = child.Solve(); // 递归解决子问题
                if (solved != null)
                {
                    return solved; // 子问题有解，原问题有解
                }
            }
        }
        return null; // 所有可能的值都尝试过了，无解
    }

    // 输出数独面板
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                sb.Append(Get(i, j)).Append(' ');
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }
}

然后，可以在Main()函数中使用上述代码：

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

运行结果如下所示：

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

可以看到，程序输出了数独问题的一个解。如果该问题无解，程序则会输出null。

示例

示例一

输入：

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

输出：

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

示例二

输入：

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

输出：

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

总结

本文介绍了如何使用C#实现数独解法。通过定义Sudoku类，实现了数独问题的求解。在解题过程中，利用回溯算法，递归地试探每个空格可能的填数，直到填到所有空格都有数为止。通过实现数独解法，不仅能够增强逻辑思维能力，还能加深对程序设计的理解。