使用 C# 和 Excel-DNA 在 Excel 中求解数独

引言

关于数独求解器的实现，各种语言都有很多。但我找不到一个在 Excel 中可以使用的。本文介绍了如何使用 C# 构建数独求解器和生成器，并使用 Excel-DNA 将其暴露给 Excel。求解器/生成器的算法非常基础，易于理解。

背景

Excel 非常适合处理网格上的数字，因此添加生成和解决数独谜题的功能非常简单。求解器用 C# 实现，并在 Excel-DNA 库的帮助下导出到 Excel。

Using the Code

已实现以下 Excel 函数来解决数独谜题。

1. acq_sudoku_generate - 生成一个随机的数独谜题。 接受一个可选的种子作为参数。 如果未指定种子，则使用计算机计时作为种子。 该函数产生一个 9x9 矩阵，因此需要在 Excel 中作为数组公式输入 (Ctrl+Shift+Enter)
2. acq_sudoku_solve - 解决数独谜题。 接受 9x9 的数独谜题作为输入参数，并生成已解决的 9x9 矩阵。 需要在 Excel 中作为数组公式输入 (Ctrl+Shift+Enter)。
3. acq_sudoku_solution_count - 返回指定谜题的可能解决方案的数量。 通常，应该只有一个解决方案，但如果您手动从谜题中删除数字，则可能解决方案的数量会增加。 该函数在找到 1024 个解决方案后停止计数。

谜题生成器在 ACQ.Math.Sudoku.Generate 中实现。 我们首先检查种子参数，然后从 Excel 包装函数中调用它。 Generate 函数生成一个 9 x 9 的数组。 此数组中等于零的元素表示空的数独单元格。 由于我们不希望 Excel 显示零，我们将其转换为对象数组，并将零替换为空字符串。

[ExcelFunction(Description = "Generate Sudoku puzzle", IsThreadSafe = true)]
public static object[,] acq_sudoku_generate(object seed)
{
    int[,] grid;
    if (seed != null && seed is double)
    {
        grid = ACQ.Math.Sudoku.Generate((int)(double)seed);
    }
    else
    {
        grid = ACQ.Math.Sudoku.Generate();
    }
    
    object[,] result = new object[grid.GetLength(0), grid.GetLength(1)];
    for (int i = 0; i < grid.GetLength(0); i++)
    {
        for (int j = 0; j < grid.GetLength(1); j++)
        {
            if (grid[i, j] == 0)
                result[i, j] = String.Empty;
            else
                result[i, j] = grid[i, j];
        }
    }
    return result;
}

求解在 ACQ.Math.Sudoku 中完成，使用一个非常原始的递归算法。 该函数返回最多指定最大值（在下面的代码中为 1）的解决方案。 ExcelHelper.BoxArray 将 int[,] 转换为 object[,]。 如果没有找到解决方案，则返回 ExcelError.ExcelErrorNull 。该函数不会检查解决方案是否是唯一的。

[ExcelFunction(Description = "Solve Sudoku puzzle", IsThreadSafe = true)]
public static object[,] acq_sudoku_solve(object[,] grid)
{
    const int size = 9;
    int[,] sudoku = acq_sudoku_convertgrid(grid, size);
    if (sudoku != null)
    {
        List<int[,]> solutions = new List<int[,]>();
        ACQ.Math.Sudoku.Solve(sudoku, solutions, 1);
        if (solutions.Count > 0)
        {
            return ExcelHelper.BoxArray(solutions[0]);
        }
    }   
    return ExcelHelper.CreateArray(1, 1, ExcelError.ExcelErrorNull);
}

下面显示了返回可能数独解决方案数量的函数的代码。 实现与 acq_sudoku_solve 几乎相同。 当您在 Excel 中手动解决数独谜题时，可以使用此函数来跟踪您的进度。 当您犯错时，可能解决方案的数量变为零。

[ExcelFunction(Description = "Count solutions to Sudoku puzzle", IsThreadSafe = true)]
public static int acq_sudoku_solution_count(object[,] grid)
{
    const int size = 9;
    const int max_count = 1024;
    int[,] sudoku = acq_sudoku_convertgrid(grid, size);
    int count = 0;
    if (sudoku != null)
    {
        List<int[,]> solutions = new List<int[,]>();
        ACQ.Math.Sudoku.Solve(sudoku, solutions, max_count);
        count = solutions.Count;                
    }
    return count;
}

用于解决数独谜题的算法是简单的递归。 还有更好的算法，因此这里没有列出（搜索代码以获取更多详细信息，例如ACQ.Math.Sudoku.Solve）。

谜题生成更有趣一些。 在第一步，使用 Knuth shuffle (也称为 Fisher-Yates shuffle) 填充对角线 3 x 3 块（如下图所示）。 这些块是独立的，因此可以随机填充。 然后解决谜题，并从谜题中随机删除数字，直到仍然有唯一的解决方案。

最新版本可在 https://github.com/ratesquant/ACQ. 获取

致谢

此 ACQ 插件基于 Excel-DNA https://exceldna.codeplex.com/。 感谢 Govert van Drimmelen（Excel-DNA 的创建者）让它成为可能。