将数独作为优化问题求解
3.00/5 (6投票s)
一种使用布尔运算解决数独问题的快速简单算法
引言
众所周知，数独是一种益智游戏，目标是将数字一到九填入 9x9 的棋盘中，使得每行和每列中没有重复的数字。棋盘还分为九个 3x3 的区域，每个区域内的数字也不能重复。作为线索，最初会提供一些数字。
可能的组合数量巨大，因此我们必须找到某种优化方法，以尽可能多地排除无效组合。
在本文中，我将展示一个简短而简单的算法，它可以使用按位布尔运算（如“与”和“或”）在不到一毫秒的时间内解决数独问题。
您可以访问我的博客找到本文的西班牙语版本。
该项目使用 C# 和 Visual Studio 2015 编写。
背景
该算法的设计只使用适合放置在处理器缓存内存中的数据类型，例如 int 或结构体。这是第一个优化。
我们希望避免检查多个单元格来判断给定数字是否可以放入其中，因此在开始处理棋盘之前必须完成一些初始化工作，以便在每个单元格中提供所需的信息来实现这一点。
我们可以通过在单个 int 中使用位位置来表示一行，而不是使用数组，从而避免一些循环。我们还需要预定义位掩码以快速检查验证条件。
十进制系统不适合与数字进行按位运算，因此我们将进行转换，将每个数字用一个位表示，且在九个不同位置中的一个，即 N = 2n-1，其中 n = 1,2,...,9。
完成此操作后，我们可以为每个单元格构建一个掩码，指示允许的数字。例如，000010011 只允许数字 1、2 和 5。我们可以为行构建一个掩码，为列构建一个掩码，为区域构建一个掩码，并将它们全部组合起来检查数字是否可以放入单元格中。
我们将每个数字的可能位置分成九个独立的层，以便我们可以单独处理它们。首先，将 1 的有效组合放置在空白棋盘上。然后，我们将尝试放置 2 的有效组合，受 1 占据的位置限制，依此类推。
这有效地限制了我们必须尝试的组合数量。此外，一旦我们找到了第一个数字在第一行中的正确位置，它将永远不会再被处理，然后是第二行，然后是第三行，依此类推，直到第一层有了 1 的正确组合，这导致该层将永远不会再被处理。然后，在第二层发生同样的过程，依此类推。
数独初始数据必须放置在文本文件中，包含九行九个逗号分隔的数字，没有额外的空格，表示棋盘。0 表示空单元格。
该应用程序是一个简单的对话框，带有一个“新建”按钮，允许选择要处理的文件并显示结果。
使用代码
棋盘使用 9x9 的 sCell 数据类型元素数组表示，定义如下：
private struct sCell
{
public int Value;
public int Row;
public int Col;
public int Sec;
public bool Fixed;
}
private sCell[,] _sudoku = null;
Value 是单元格中包含的数字，格式为 2n-1，如果为空则为零。Fixed 表示此单元格是否包含初始值。其他三个成员 Row、Col 和 Sec 是位掩码，包含与单元格在同一行、列和区域中已存在的数字。
我们使用 SetCell 方法初始化具有给定数字的单元格，并更新同一行、列和区域中所有单元格的位掩码信息。
private void SetCell(int row, int col, int v, bool fix)
{
_sudoku[row, col].Value = v;
_sudoku[row, col].Fixed = fix;
for (int c = 0; c < 9; c++)
{
_sudoku[row, c].Row |= v;
_sudoku[c, col].Col |= v;
_sudoku[(3 * (row / 3)) + (c % 3), (3 * (col / 3)) + (c / 3)].Sec |= v;
}
}
现在，我们需要定义一个 9x9x9 元素的工作数组，将所有数字分成九层，每一层对应一个不同的值，我们将在其中使用单个位来存储每个列的有效位置。例如，如果第三列中可以有一个 1，我们将使用数字 001000000 来表示该层中的该位置。我们还将定义列和区域的掩码，以便在一次操作中判断某个位置是否允许。此数组包含 sNum 结构体类型的元素，定义如下：
private struct sNum
{
public int Position;
public int Col;
public int ColMask;
public int SecMask;
}
private sNum[,,] _layers = null;
Position 成员包含一个数字，其中表示列的位设置为 1。ColMask 和 SecMask 是列和区域的位掩码。列的位掩码是位置的反向，我们预先计算它以避免在工作程序中的计算中使用非运算符。区域的掩码分别为 000111111、111000111 和 111111000。
为了避免处理空位置，我们将每行 n 个位置的数据存储在数组的前 n 列中。Col 成员用于存储数独棋盘中的实际列。
BuildLayers 方法被调用一次以执行此初始化工作。
private void BuildLayers()
{
int v = 1;
for (int n = 0; n < 9; n++)
{
for (int row = 0; row < 9; row++)
{
int c = 0;
int msec = 0x3F;
int mcol = 0x7EFF;
int bit = 0x100;
for (int col = 0; col < 9; col++)
{
bool set = false;
if (_sudoku[row, col].Fixed)
{
if (_sudoku[row, col].Value == v)
{
set = true;
}
}
else if (((_sudoku[row, col].Row |
_sudoku[row, col].Col |
_sudoku[row, col].Sec) & v) == 0)
{
set = true;
}
if (set)
{
_layers[row, c, n].Position = bit;
_layers[row, c, n].Col = col;
_layers[row, c, n].ColMask = mcol & 0x1FF;
_layers[row, c++, n].SecMask = msec;
}
bit >>= 1;
mcol >>= 1;
mcol |= 0x4000;
if (col == 2)
{
msec = 0x1C7;
}
else if (col == 5)
{
msec = 0x1F8;
}
}
}
v <<= 1;
}
}
我们需要的最后一个元素是一个包含九个整数的数组，用于表示每行的按位位置，1 表示空单元格，0 表示已填充单元格。这可能看起来违反直觉，但这样我们再次避免了在工作程序中使用非运算符。
_positions = new int[9];
for (int n = 0; n < 9; n++)
{
_positions[n] = 0x1FF;
}
现在，我们可以开始处理所有这些数据。我们只需要使用一个单独的递归方法，分为两部分：一部分用于继续处理有效组合，另一部分用于在我们无法做到时尝试新组合。这是 ProcessNextNumber 方法，它带有一个参数，表示要处理的层数。
private bool ProcessNextNumber(int n)
{
int[] indexes = new int[9];
int[] oldpositions = new int[9];
for (int num = 0; num < 9; num++)
{
oldpositions[num] = _positions[num];
}
int mcol = 0x1FF;
int msec = 0x1FF;
int ix = 0;
int v = 1 << n;
while (true)
{
int index = indexes[ix];
if ((_layers[ix, index, n].Position & msec & mcol & _positions[ix]) != 0)
{
_positions[ix] &= _layers[ix, index, n].ColMask;
_sudoku[ix, _layers[ix, index, n].Col].Value = v;
switch (ix)
{
case 2:
case 5:
mcol &= _layers[ix, index, n].ColMask;
msec = 0x1FF;
ix++;
break;
case 8:
if ((n == 8) || ProcessNextNumber(n + 1))
{
return true;
}
_positions[8] = oldpositions[8];
mcol |= _layers[8, indexes[8], n].Position;
msec = _layers[7, indexes[7], n].SecMask &
_layers[6, indexes[6], n].SecMask;
indexes[8]++;
break;
default:
mcol &= _layers[ix, index, n].ColMask;
msec &= _layers[ix, index, n].SecMask;
ix++;
break;
}
}
else
{
if ((_layers[ix, index, n].Position != 0) && (index < 8))
{
indexes[ix]++;
}
else
{
if (ix == 0)
{
return false;
}
indexes[ix] = 0;
ix--;
_positions[ix] = oldpositions[ix];
mcol |= _layers[ix, indexes[ix], n].Position;
switch (ix % 3)
{
case 0:
msec = 0x1FF;
break;
case 1:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask;
break;
default:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask &
_layers[ix - 2, indexes[ix - 2], n].SecMask;
break;
}
indexes[ix]++;
}
}
}
}
第一步是定义和初始化变量。我们将使用 indexes 来存储当前值组合中每行的当前位置。oldpositions 用于将每行的位置掩码重置为其初始值。mcol 和 msec 是列和区域的掩码，我们从允许所有位置使用开始。ix 是当前行的索引，v 是与当前层对应的数字。
为了检查位置的有效性，我们使用以下条件：
if ((_layers[ix, index, n].Position & msec & mcol & _positions[ix]) != 0)
对于有效位置，我们将相应的位设置为 0，并将值存储在 _sudoku 棋盘中。
_positions[ix] &= _layers[ix, index, n].ColMask;
_sudoku[ix, _layers[ix, index, n].Col].Value = v;
根据我们所在的行，处理过程不同。在第二行和第五行，我们即将切换到新的区域行，因此 msec 掩码必须初始化以允许所有位置。mcol 掩码累积已使用的列，以便它们不能再次使用。最后，行索引递增以处理下一行。我们不需要检查行的任何信息，因为我们每行只放置一个值。
mcol &= _layers[ix, index, n].ColMask;
msec = 0x1FF;
ix++;
在第一行到第八行的其余行中，msec 掩码累积当前行的区域掩码。
mcol &= _layers[ix, index, n].ColMask;
msec &= _layers[ix, index, n].SecMask;
ix++;
当我们到达第九行时，我们有一个完整的数值组合。如果我们在最后一层，过程结束；如果不是，我们将控制权传递给下一层。如果这不成功，我们必须重置掩码和位置的值，并尝试第九行中下一个可用位置。
_positions[8] = oldpositions[8];
mcol |= _layers[8, indexes[8], n].Position;
msec = _layers[7, indexes[7], n].SecMask &
_layers[6, indexes[6], n].SecMask;
indexes[8]++;
另一方面，如果当前位置无效，如果仍然有可用的位置，我们尝试下一个。
if ((_layers[ix, index, n].Position != 0) && (index < 8))
{
indexes[ix]++;
}
如果这不可能，我们首先检查是否在第一行。这意味着没有有效的组合，我们返回控制权到上一层，并指示这一点。如果我们可以继续，我们将当前行的索引重置为 0，以再次尝试所有可能的位置，并移到上一行。
if (ix == 0)
{
return false;
}
indexes[ix] = 0;
ix--;
在这一行中，我们必须重置列和区域掩码以及最后使用的位置。最后，我们增加位置索引以再次尝试。
_positions[ix] = oldpositions[ix];
mcol |= _layers[ix, indexes[ix], n].Position;
switch (ix % 3)
{
case 0:
msec = 0x1FF;
break;
case 1:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask;
break;
default:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask &
_layers[ix - 2, indexes[ix - 2], n].SecMask;
break;
}
indexes[ix]++;
此算法完成所需的时间不取决于数独的难度（当然，是人类的难度），而是取决于数字在最终棋盘中的位置。因此，您可能会发现一个简单的数独比一个极其困难的数独完成所需的时间更长。
就这样，感谢阅读！