欧拉项目 | 96题 | 数独

96题链接

数独，一个很经典的填数字游戏。规则也很简单，每一行、每一列、九个九宫格的九个数字不重复。
设计很好的数独游戏只有一个解，题目中也假设了这一点。
题目最后要求五十个数独的解，然后计算左上角三位数之和。
这个题对我来说还算比较简单，只需要把我人肉做数独游戏的方法写成程序就好了。

由于整体思路非常清晰，我采用了自上而下的设计方式，几乎一气呵成了整个程序，除了debug了一个小地方fix了一个bug外。
我需要一个函数把题目给的txt下载下来并一行一行的读到一系列二位数组中。
对于每个二维数组，就是一个数独题目，然后求解，得到左上角的三位数。求和。

private static readonly int Length = 9;

public static int GetAnswer()
{
    int sum = 0;
    var lines = GetContent();
    for (int i = 0; i < 50; i++)
    {
        int[,] soDoku = new int[Length, Length];
        for (int j = 0; j < Length; j++)
        {
            var line = lines[10 * i + j + 1];
            for (int k = 0; k < Length; k++)
            {
                soDoku[j, k] = Convert.ToInt32(line[k].ToString());
            }
        }

        sum += GetTopLeft(SolveSuDoku(soDoku));
    }

    return sum;
}

GetContent()函数很简单，下载文件，切分行。如果愿意的话，甚至能写成一行。

private static string[] GetContent()
{
    WebClient client = new WebClient();
    string content = client.DownloadStri("https://projecteuler.net/project/resources/p096_sudoktxt");
    return content.Split('\n');
}

GetTopLeft(int[,] soDoku)函数相对也比较简单，拿到二维数组的左上角三个数字，拼成string然后转成int即可。或者是第一位乘以100加第二位乘以10加第三位。

private static int GetTopLeft(int[,] soDoku)
{
    return int.Parse($"{soDoku[0, 0]}{soDoku[0, 1]}{soDoku[0, 2]}");
}

最复杂的部分就是解数独了。
解数独就是在不停的猜测和测试，整个过程显然是递归的。
找个一个空，可能有几个情况，选一个填进去，依旧是未完成的数组，再来一轮，一轮，直到完成。整个过程是一个树，分了很多叉。题目告诉我们只有一个解，那么只有一个叶子节点是完整的解，其他叶子节点都不合法，有矛盾的地方，比如某个点所在的行和列出现了重复数字。
首先，我们判断数独是否完成，如果是，则返回该解。
如果没有，我们需要找一个点，该点没有被填写数字，且可能填的数字尽可能的少，这种情况下该节点的子树才最少，效率能尽可能的高。FindMinimalPoint返回参数包含三项，前两者描述的该节点的位置，第三项是可能的值。如果Item3是空的话，那么说明当前的数独有矛盾，返回null。试图尝试所有的可能性，如果有解，则返回，如果所有的可能性都无解的话，走到最后一行返回null。

private static int[,] SolveSuDoku(int[,] soDoku)
{
    if (IsCompleted(soDoku))
    {
        return soDoku;
    }

    var point = FindMinimalPoint(soDoku);
    foreach (var v in point.Item3)
    {
        int[,] newSoDoku = soDoku.Clone() as int[,];
        newSoDoku[point.Item1, point.Item2] = v;
        var ret = SolveSuDoku(newSoDoku);
        if (ret != null)
        {
            return ret;
        }
    }

    return null;
}

如果实现FindMinimalPoint呢？遍历非0点，找到可能的值（FindVaulesAt），记录下可能的值最少的点坐标和对应的值并返回。对于FindVaulesAt函数，很可能返回0个解，就是说该数独有矛盾。minList在初始化的时候写了十个值，目的是比九大，其实这里写九个也没问题，因为最小值肯定比九要小。

private static (int, int, List<int>) FindMinimalPoint(int[,] soDoku)
{
    int minRow = -1;
    int minCol = -1;
    var minList = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    for (int i = 0; i < Length; i++)
    {
        for (int j = 0; j < Length; j++)
        {
            if (soDoku[i, j] == 0)
            {
                var values = FindVaulesAt(i, j, soDoku);
                if (values.Count < minList.Count)
                {
                    minList = values;
                    minRow = i;
                    minCol = j;
                }
            }
        }
    }

    return (minRow, minCol, minList);
}

FindVaulesAt想法很直接。每个空可能填入一到九九个数字，排除所在行、所在列和所在的九宫格已经出现的数字即可。
文章开头提到fix了一个小bug就是在这个函数，一开始row的初始值写成了i % 3，row < i - i % 3 + 3，进而没能得到正确的可能的值。

private static List<int> FindVaulesAt(int i, int j, int[,] soDoku)
{
    List<int> values = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    for (int k = 0; k < Length; k++)
    {
        values.Remove(soDoku[i, k]);
    }

    for (int k = 0; k < Length; k++)
    {
        values.Remove(soDoku[k, j]);
    }

    for (int row = i - i % 3; row < i - i % 3 + 3; row++)
    {
        for (int col = j - j % 3; col < j - j % 3 + 3; col++)
        {
            values.Remove(soDoku[row, col]);
        }
    }

    return values;
}

最后，给出整个拼图的最后一块IsCompleted。如果所有空都不是0，说明数独已经求解完毕了。

private static bool IsCompleted(int[,] soDoku)
{
    foreach (var cell in soDoku)
    {
        if (cell == 0)
        {
            return false;
        }
    }

    return true;
}