数独谜题求解器
本文介绍了求解数独谜题的程序的工作原理。
引言
本文描述了一个用 C++ 编写的数独谜题求解方案，旨在达到最快的求解时间。目前，我不敢声称这个算法是“最快”的，因为我还没有将其与其他可能更优的算法进行比较。该程序使用基于规则的算法来解决给定的谜题。即使是回溯算法也能在几秒钟内解决这个问题，这是因为问题的简单性。我们可能会认为，空白格越多，解决问题所需的时间就越长；这对于人类玩家来说可能是正确的，但对于谜题求解算法来说，不一定如此。我们无法仅凭空白格的数量准确确定求解一个谜题的运行时间，因为有些空白格包含足够的信息，可以清楚地确定需要填入的数字。但在大多数情况下，数独谜题的空白格至少有两个可能的选项。
在本文中，“可能性”指的是包含所引用单元格的行、列和同一 3x3 网格中不存在的值的集合。数独谜题的一个规则是，每行、每列和每个 3x3 的子网格中都不能重复数字。这与说每行、每列和 3x3 的子网格都应包含从一到九的所有值相同。每个单元格的可能性可以通过检查其所在的行、列和 3x3 子网格，并消除已找到的值来计算。这样就得到了尚未填入且成为该单元格有效可能性的值。
对我而言，这个程序一开始并没有奏效。我一开始就错了，我不知道数独问题会存在没有任何只有一个可能性的空白格的情况。我最初认为每个数独谜题都可以线性时间解决，每个谜题至少有一个单元格只有一个可能性。我很快编写了一个程序，通过检查只有一个可能性的单元格并填入值来解决问题。但可惜的是，它并非对所有问题都有效！那时我才意识到，数独谜题存在空白格有多个可能性的情况。于是，我的下一个想法是使用回溯算法来获得解决方案。
起初，我不相信回溯算法会奏效。原因在于，如果我们有一个有 35 个空白格的棋盘，每个单元格至少有两个可能性，那么求解就不是一个线性时间操作。即使我们考虑每个空白格的最小可能性，即 2，我们最终将拥有 (2^{35}) 种可能性。有时，甚至有五种可能性。现在这看起来是更大的数字。这完全让我确信使用这样的算法不会奏效。但我错了。简单的原因是，在一个空白格中填入一个数字，在大多数情况下，会使同一行、列和 3x3 单元格中空白格中可以填入的可能值数量减少一个。如果可能性的数量本身是两个，那么它就会减少到一。所以可能性最终不会是 (2^{35})！相反，随着你不断地在每个单元格中填入值，“其他空白格的‘可能性’会减少一个，甚至可能确定（（）即明确说明应填入哪个数字））。最后，通过回溯算法进行的实验，可以清楚地表明，问题并不总是需要很长时间才能解决（（除非它被特意设计成很难通过任何蛮力算法解决））。
数独求解器的基本思想
该解决方案分为两部分；第一部分包含了分析数独棋盘并筛选每个单元格可能性的实现。定义了一组权重值，它决定了首先选择哪个单元格进行填充。权重值的分配方式是，权重值最大的单元格拥有的可能性最少，并且它被周围可能性最小的空白格所包围（（即沿行、列和 3x3 子网格））。
考虑在一个空白格 (p(i, j)) 中填入一个数字，那么子方格就是 (p( [i / 3]X 3 + ki, [j/3]X3 + kj))，其中 (ki) 和 (kj) 从零到三不等。同时，考虑行和列分别表示为 (p(k, j)) k 从 0 到 8 不等，以及 (p(i, k) )k 从 0 到 8 不等。现在，(p(k, j)) 和 (p(i, k)) 中的空白格也会排除一个可能性；即，如果填入 (p(i, j)) 的数字是 v，那么相同的数字不应出现在 (p(k, j), p(i, k)) 和 (p( [i / 3]X 3 + ki, [j/3]X3 + kj)) 中的任何单元格内，也不能填入。因此，(p(k, j)), (p(i, k)) 和 (p( [i / 3]X 3 + ki, [j/3]X3 + kj)) 中的每个空白格都会排除可能性 v（（注意 [.] 表示最大整数））。如果这些单元格组中的空白格的“可能性数量”包含值 v，则可能性数量会减少一个。如果之前有 2 种可能性，则变为 1 种。一旦一个单元格只有一个可能性，它就会立即被填入。因此，为了确保快速的运行时间，会选择被其他可能性较少的空白格包围的单元格。这样它们就可以立即得出结论，更快地填入后续的单元格。为此，涉及以下步骤：
分析数独棋盘并为每个空白单元格返回权重值的算法，
并选择权重值最高的单元格。
算法 1：计算所有可能性的总和
步骤 1：获取谜题棋盘 (p(i, j))
步骤 2：计算每个 ((i, j)) 的可能性
步骤 2.1：初始化大小为 (9x9) 的“可能性棋盘”，其中每个单元格都包含一个位掩码，其中包含所有可能的数字（（ 1 到 9））。
步骤 2.2：现在，从 ((i, j)) 开始搜索行、列和 3x3 子方格
，并消除在这些单元格中找到的每个值，从而获得可能性集合。
步骤 2.3：对所有 ((i , j)) 重复步骤 2.1 和 2.2
步骤 3：现在，从 ((i, j)) 开始，对每行、每列和 3x3 子方格的可能性数量进行求和，并将值放入另一个大小为 9x9 的棋盘（（ b_{sum}））中，用于所有 ((i, j))。
步骤 4：返回 (b_{sum})
算法 2：获取倒数
步骤 1：从算法 1 中获取 (b_{sum})。
步骤 2：初始化另一个棋盘（（ b_{inv}，它是一个浮点变量数组
，大小为 9x9））。
步骤 3：对于每个 ((i, j))，(b_{inv}(i, j)) (=) ( \frac{1}{b_{sum}(i, j)} )
步骤 4：返回 (b_{inv})
算法 3：获取倒数之和
定义另一个大小为 9x9 的浮点数据类型数组变量，类似于算法 1，
对倒数值 (b_{inv}) 进行求和，而不是对可能性的数量进行求和，并获得
(b_{invsum}) 变量并返回它。
人们可能会认为算法 2 中用于获得倒数之和的倒数可能会存储零。但这不可能；因为，每个包含值的单元格都将被视为一个可能性为一的单元格。
现在我们来看看实际包含这些算法的代码。
#ifndef INVERSECOUNT_H
#define INVERSECOUNT_H
#include "basicDeff.h"
#include <vector>
const int Row = 0;
const int Col = 1;
const int Cell = 2;
class InvCount
{
public:
float Count[3][9];
void SetValues(InversePossibility& a);
float Reterive(int Type, int pos);
};
extern const int Row;
extern const int Col;
extern const int Cell;
#endif // INVERSECOUNT_H
现在我们来看定义
#include <iostream>
#include "inverseCountSum.h"
void InvCount::SetValues(InversePossibility& a)
{
int i,j, k;//, c = 0;
for(i= 0; i <9; ++i)
{
Count[Row][i] = 0.0;
for(j=0; j<9; ++j)
{
Count[Row][i] += a[i][j];
}
}
for(i= 0; i <9; ++i)
{
Count[Col][i] = 0.0;
for(j=0; j<9; ++j)
{
Count[Col][i] += a[j][i];
}
}
for(k=0; k<9; ++k)
{
Count[Cell][k] = 0.0;
for(i= (((int)(k/3)*3) ); i < (((int)(k/3)*3)) + 3; ++i)
for(j= ((k*3) % 9); j < ((k*3) % 9) + 3; ++j)
{
Count[Cell][k] += a[i][j];
}
}
}
float InvCount::Reterive(int Type, int pos)
{
//std::cout<<" "<<Count[Row][pos]<<" ";
switch (Type)
{
case Row:
return Count[Row][pos];
break;
case Col:
return Count[Col][pos];
break;
case Cell:
return Count[Cell][pos];
break;
default:
return 0; // do nothing
}
}
上面的代码定义了求和，其中可能性在每一行、每一列和 3x3 子方格中进行求和。如果我们创建一个递归函数来对每个单元格进行求和，那么我们将近乎进行 (27x81) 次操作，而我们只需要进行 (81x2) 次操作。
接下来是实际执行获取每个单元格的求和、计算倒数之和并最终生成权重值的代码部分。
void Sudoku::GeneratePossibilityCount() // this is to be called only after calling the
{ // screen possibility function for all (x,y) coordinates
int i,j;
for(i=0; i<9; ++i)
for(j=0; j<9; ++j)
possibilityCount[i][j] = NoOfElements(possibilities[i][j]);
}
void Sudoku::GenerateInversePossibilityCount() // this is to be called after the GeneratePossibilityCount() is called
{
int i,j;
for(i=0; i<9; ++i)
for(j=0; j<9; ++j)
{
possibilityCountI[i][j] = (float)(1/(float)possibilityCount[i][j]);
}
}
void Sudoku::GenerateWaightValues(InvCount& inv, WaightQueue& Q, int pos_x, int pos_y)
{
GridLimits Lim;
Lim.SetLimits(pos_x, pos_y);
TempPUnit.PriorityValue = inv.Reterive(Row, pos_x - 1) +
inv.Reterive(Col, pos_y - 1) +
inv.Reterive(Cell, Lim.GridNo - 1)+
10*possibilityCountI[pos_y-1][pos_x-1];
TempPUnit.x = pos_x -1; // stored in C string indexing convention
TempPUnit.y = pos_y -1;
Q.push(TempPUnit);
}
// this one generates the weight values.
WaightQueue Sudoku::GenerateWaightValues()
{
WaightQueue Q;
int i,j;
for(i=1; i<=9; ++i)
for(j=1; j<=9; ++j)
{
if (Grid[i-1][j-1] == 0)
GenerateWaightValues(PossibCount, Q, j, i);
}
return Q;
}
以下代码，
possibilityCount[i][j] = NoOfElements(possibilities[i][j]);
从变量 'possibilities[i][j]' 中筛选出可能性。这个变量是一个位掩码，它保存了可以填入位置 ((i, j)) 的所有可能值的集合。这个位掩码数组的每个位置都代表一个特定的值。第 (i) 个位置上的位值为 1 表示值 (i) 已包含在集合中。
供参考，'NoOfElements()' 函数定义如下：
int Sudoku::NoOfElements(int value)
{
int tcount = 0;
if( (value & POS1) != 0) ++tcount;
if( (value & POS2) != 0) ++tcount;
if( (value & POS3) != 0) ++tcount;
if( (value & POS4) != 0) ++tcount;
if( (value & POS5) != 0) ++tcount;
if( (value & POS6) != 0) ++tcount;
if( (value & POS7) != 0) ++tcount;
if( (value & POS8) != 0) ++tcount;
if( (value & POS9) != 0) ++tcount;
return tcount;
}
这显然会检查并计算可能性的数量。现在接下来的部分旨在以类似于反向传播算法的方式使用递归算法来解决问题。唯一的区别是，空白单元格是根据先前计算的权重值选择性地选择的。实现此功能的算法如下所示：
算法 4：实现核心计算部分
步骤 1：获取数独棋盘 (p(i, j))。
步骤 2：如果 (p(i, j)) 没有空白格，并且结果是合法的，则程序将“结果”设置为棋盘 (p(i, j)) 并返回 false。
步骤 3：使用数独棋盘 (p(i, j)) 设置权重值，从而获得 (w(i, j))。
步骤 4：选择权重值最大的空白格
步骤 5：获取可以填入该处的可能值。随机或线性地选择一个并填入空白格。有必要记录进行了什么修改，以便将来能够撤销它。
步骤 6：现在，将新棋盘传递到此模块中，并再次调用此函数。此递归调用将导致再次执行此算法，但具有在最初的空白格中包含值的更新修改。
步骤 7：现在检查此模块返回 true 还是 false。如果返回 true，则表示结果已在某个递归调用中成功计算，并且结果已设置。如果返回 false，则撤销步骤 5 中所做的更改，并填入另一个可能性，继续执行步骤 6 和 7，直到所有可能性都被用尽。
步骤 8：一旦所有可能性都被用尽，就可以得出结论，该棋盘 (p(i, j)) 没有解决方案，并返回 false。
执行上述算法的代码如下：
#include <iostream>
#include "coreSolution.h"
#include "Sudoku.h"
#include "basicDeff.h"
Sudoku Solver::SudokuSolution;
bool Solver::IsSolutionSet = false;
int Solver::Count = 0;
int Solver::GlobalPossibilities[9][9];
void Solver::initializeGP()
{
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j)
GlobalPossibilities[i][j] = POS_ALL;
}
void Solver::SetCurPuzzle(Sudoku P)
{
int i, j;
for (i = 0; i < 9; ++i)
for (j = 0; j < 9; ++j)
(*CurPuzzle.RetGrid())[i][j] = (*P.RetGrid())[i][j];
}
bool Solver::RecrussiveSolve()
{
PriorityUnit Unit;
Solver solve;
int temp_pos, temp;
int i;
int size;
CurPuzzle.reinitializepos();
while (CurPuzzle.Solve()); // tries to solve the puzzle using the linear search
if (CurPuzzle.FullPossibility()) return false;
CurPuzzle.GeneratePossibilityCount();
CurPuzzle.GenerateInversePossibilityCount();
CurPuzzle.SetPossibilityCount();
Q = CurPuzzle.GenerateWaightValues(); // Q is a priority queue containing the weight values
// and the respective cell it points to.
// This automatically arranges the weight values in
// acceding order.
if (CurPuzzle.IsSolved())
{
if (CurPuzzle.IsLegal() )
{
Solver::SudokuSolution = CurPuzzle; // if the puzzle is solved, it sets a global scoped
//variable, assigning it its final answer.
Solver::IsSolutionSet = true; // indicates that the solution is set successfully
return true;
}
else
return false;
}
solve.SetCurPuzzle(CurPuzzle);
Unit = Q.top();
temp_pos = (*CurPuzzle.RetPoss())[Unit.y][Unit.x];
size = Sudoku::NoOfElements(temp_pos);
for (i = 0; i < size; ++i)
{
temp = (*solve.CurPuzzle.RetGrid())[Unit.y][Unit.x] = Sudoku::BitValue(temp_pos);
Sudoku::DeleteValue(temp, temp_pos);
if (solve.RecrussiveSolve())
return true;
solve.SetCurPuzzle(CurPuzzle);
}
(*solve.CurPuzzle.RetGrid())[Unit.y][Unit.x] = 0;
Q.pop();
return false;
}
上面的程序执行“递归求解”过程。
使用此代码
此代码使用 g++ 编译器编译，并在 code::blocks IDE 中开发。
未来工作
此程序可以扩展以支持更多分析方法来研究数独谜题的性质。需要分析其数学结构和在各种场景下的行为。观察以下一行：
TempPUnit.PriorityValue = inv.Reterive(Row, pos_x - 1) +
inv.Reterive(Col, pos_y - 1) +
inv.Reterive(Cell, Lim.GridNo - 1)+
10*possibilityCountI[pos_y-1][pos_x-1];
值 10 是随机选择的，即使将符号从 10 更改为 -10 也可能对解决方案产生影响；对于一类特定问题，求解速度会更快，而另一类问题求解速度会变慢。或者，如果我们使用 -3 而不是 +10，我们将完全忽略添加到这些其他值的单元格中的可能性。但是通过添加 10，我们优先考虑该特定单元格的可能性数量，而不是相邻单元格的可能性数量。
这个“retrieve”函数检索沿 x 或 y 方向的求和。这个分析部分不影响解决方案的正确性，但直接影响执行时间。
历史
本文首次发布于 2015-09-27。