数独解题器和生成器

• 下载源文件 - 17.63 KB
• 下载演示项目 - 11.71 KB

引言

不久前，我的一个同事向我介绍了一款名为数独的游戏。我对此游戏一无所知，但很快就明白了规则，然后很快意识到，做一个程序来解决这个问题会比解决一个单一的谜题快得多！

数独规则

数独的规则很简单。你有一个 9x9 的棋盘，棋盘进一步划分为九个 3x3 的子正方形。在每个子正方形、每行和每列中，你必须唯一地填入数字 1-9。

在创建数独时，我们必须记住，它只能有一个解，否则它不被认为是真正的数独。

解决谜题

当类初始化并且设置了数独谜题进行求解时，我们可以让 `Solve()` 函数开始工作。在每次迭代中，我们希望找到棋盘上信息最多的位置。我们从一个包含该位置所有可能解的初始集合 `M` 开始。

// Set M of possible solutions
byte[] M = {0,1,2,3,4,5,6,7,8,9};

然后我们移除垂直方向上所有已使用的出现项

for(int a = 0; a < 9; a++)
    M[m_sudoku[a,x]] = 0;

以及水平方向上

for(int b = 0; b < 9; b++)
    M[m_sudoku[y,b]] = 0;

最后，我们移除子正方形中所有已使用的出现项。为了加快可行性测试并简化代码，我决定使用子正方形的查找表。首先，我们通过使用一个将位置映射到子正方形的表，从当前位置获取子正方形表的索引。

int squareIndex = m_subSquare[y,x];

然后我们使用一个子索引数组来获取二维数组中的实际位置。

EntryPoint p = m_subIndex[squareIndex,c];

最后一段代码片段用于一个移除正方形中所有出现项的循环。

for(int c = 0; c < 9; c++)
{
    EntryPoint p = m_subIndex[squareIndex,c];
    M[m_sudoku[p.x,p.y]] = 0;
}

然后我们计算集合 `M` 的基数。

int cM = 0;
for(int d = 1; d < 10; d++)
    cM += M[d] == 0 ? 0 : 1;

如果当前集合的基数小于之前的最小基数，则当前位置是迄今为止评估出的最佳位置。

if(cM < cMp)
{
    cMp = cM;
    Mp = M;
    xp = x;
    yp = y;
}

最小基数 `cMp` 最初设置为 `10`，如果它没有改变，我们可以确定棋盘上没有空位，并且可以成功退出。

if(cMp == 10)
    return true;

另一方面，如果最小集合的基数为 `0`，即有一个空的可能元素集合 `M`，我们可以确定没有解决方案，并且必须回溯。

if(cMp == 0)
    return false;

当所有基本情况都得到处理后，我们可以开始迭代过程，依次尝试 `M` 中的每个元素。

for(int i = 1; i < 10; i++)
{
    if(Mp[i] != 0)
    {
        m_sudoku[yp,xp] = Mp[i];
        if(Solve())
            return true;
    }
}

// Restore to original state.
m_sudoku[yp,xp] = 0;
return false;

该循环依次用 `M` 中的每个元素替换未使用的位置，并以递归方式尝试求解。当 `M` 被耗尽时，我们返回 `false`，表示没有解决方案。如果函数成功返回，则可以在 `Data` 属性中读取解决方案，如示例所示。

...
Sudoku s = new Sudoku();
s.Data = SudokuToSolveFor;
if(s.Solve())
    byte[,] SudokuSolved = s.Data;
else
    // No solution
...

生成数独

我很快意识到手动输入数独太无聊了，于是着手进行生成数独的任务。我的要求是，你应该能够指示需要填充多少个位置，并提供一个可能的起始模式。如果可能的起始模式第一次尝试不成功，它就可以被丢弃，并且可以生成一个全新的模式，否则我们可能会陷入一个没有解决方案的模式，考虑到整个数独空间的规模，这在复杂性方面是很糟糕的，程序会进行一定次数的重试。

函数 `Generate(int nodes, int numberOfTries = 1000000)` 是所有功能所在的地方。我们开始计算当前数据集已使用的位置数量，然后决定是重新开始还是，然后生成一个全新的数独。

int num = GetNumberSpots();

if(!IsSudokuFeasible() || num > nodes)
{
    // The supplied data is not feasible, clear data.
    // - or -
    // The supplied data has too many nodes set, clear data.
    return Tuple.Create(0L, false);
}

生成指定数量的位置，然后测试数独的唯一性。

do
{
    var originalData = Data;

    long tries = 0;
    for (; tries < numberOfTries; tries++)
    {
        // Try to generate spots
        if (Gen(spots - num))
        {
            // Test if unique solution.
            if (IsSudokuUnique())
            {
                return Tuple.Create(tries, true);
            }
        }

        // Start over.
        Data = originalData;
    }

    return Tuple.Create(tries, false);

该循环一直运行直到找到解决方案运行指定次数的迭代。如果我们想在搜索过程中中止，这里有改进的空间。`Gen(int spots)` 函数首先在 9x9 的棋盘上生成一个随机位置。为了在单元测试中实现确定性，随机生成器实现了 `IRandomizer` 接口，在生产环境中是非确定性的，但在单元测试中是确定性的。

do
{
    xRand = Randomizer.GetInt(9);
    yRand = Randomizer.GetInt(9);
} while(m_sudoku[yRand,xRand] != 0);

对于每个随机位置，我们必须检查可行值，这几乎与求解器中的方式相同。

// Set M of possible solutions
byte[] M = {0,1,2,3,4,5,6,7,8,9};

// Remove used numbers in the vertical direction
for(int a = 0; a < 9; a++)
    M[m_sudoku[a,xRand]] = 0;

// Remove used numbers in the horizontal direction
for(int b = 0; b < 9; b++)
    M[m_sudoku[yRand,b]] = 0;

// Remove used numbers in the sub square.
int    squareIndex = m_subSquare[yRand,xRand];
for(int c = 0; c < 9; c++)
{
    point p = m_subIndex[squareIndex,c];
    M[m_sudoku[p.x,p.y]] = 0;
}

int cM = 0;
// Calculate cardinality of M
for(int d = 1; d < 10; d++)
    cM += M[d] == 0 ? 0 : 1;

如果基数大于零，我们从可行集 `M` 中随机抽取一个样本。

if(cM > 0)
{
    int e = 0;

    do
    {
        // Randomize number from the feasible set M
        e =  Randomizer.GetInt(1,10);
    } while(M[e] == 0);

    // Set number in Sudoku
    m_sudoku[yRand,xRand] = (byte)e;
}

如果集合 `M` 为空，这就不可能是一个数独，我们重新开始该过程，直到找到一个非空的集合 `M`。当所有给定的位置都生成完毕后，我们在 `TestUniquness()` 函数中尝试唯一性。唯一性测试是通过尝试生成多个解决方案来实现的；一旦存在多个解决方案，生成的集合将不可行，然后生成一个新的解决方案。

... // same as in Solve()

int success = 0;
for(int i = 1; i < 10; i++)
{
    if(Mp[i] != 0)
    {
        m_sudoku[yp,xp] = Mp[i];

        switch(TestUniqueness())
        {
            case Ret.Unique:
                success++;
                break;

            case Ret.NotUnique:
                return Ret.NotUnique;

            case Ret.NoSolution:
                break;
        }

        // More than one solution found?
        if(success > 1)
            return Ret.NotUnique;
    }
}

...

switch(success)
{
    case 0:
        return Ret.NoSolution;

    case 1:
        return Ret.Unique;

    default:
        // Won't happen.
        return Ret.NotUnique;
}

示例应用

为了演示如何使用该类，我制作了一个使用 Windows Forms 的小型、基础的应用程序。通过这个应用程序，你可以生成、求解、打印、加载和保存数独。

历史

• 2010 年 7 月 31 日 - 文章更新
• 提交了一个存在了大约五年的 bug 修复。
• 将解决方案迁移到 Visual Studio 2010 和 .NET 4.0。
• 将解决方案拆分为三个程序集。
• 添加了元组和可选参数 (C# 4.0)。
• 添加了单元测试 (`Microsoft.VisualStudio.TestTools.UnitTesting`)。
• 2005 年 10 月 18 日 - 文章提交
• 2005 年 10 月 2 日 - Windows Forms 框架
• 2005 年 9 月 25 日 - 数独类