使用渐进式搜索解决数独
4.00/5 (1投票)
本文描述了一个使用渐进式搜索算法解决数独难题的 ASP.NET Web 应用程序。
引言
本文旨在描述一个数独求解器 Web 应用程序（可从此处运行）及其相关的渐进式搜索算法。渐进式搜索是作者开发的一种随机迭代搜索算法，已被发现对各种优化问题有效。其中包括但不限于填字游戏生成和寻找大型幻方（一个 200×200 的幻方可以在大约 3 分钟内找到）；更多信息可以在我的活动页面和我的算法书籍Algorithms: Development and Programming中找到。
数独是一种近年来流行的逻辑谜题。该谜题通常吸引那些寻求挑战其逻辑技能的人。该谜题使用一个 9×9 的方格，由九个 3×3 的子方格（盒子）组成。求解器的任务是将数字 1-9 放入网格的单元格中，使得每个数字在每行、每列和每个 3×3 的盒子中都只出现一次。一个典型的数独谜题可能有 20 到 35 个初始填充的单元格，具体取决于难度级别。数独求解器的任务是找到可以分配给空单元格的缺失数字。
如何使用数独求解器
从上图中展示的界面可以看出，有三种方法可以输入数独谜题。
- 从下拉列表中选择一个谜题。
- 点击“随机谜题”按钮生成一个随机谜题。
- 在显示的谜题网格中输入固定单元格的数字。
求解器将尝试大约 20 秒来找到一个最终（或近似）解。无论返回的解是最终解还是近似解，都可以点击“新解”按钮再次尝试解决相同的谜题。
应用程序结构
我们的数独求解器是一个 ASP.NET 网站，由 ASPX 文件“default.aspx”及其后端 C# 代码文件“default.aspx.cs”组成。ASPX 文件中的 HTML/JavaScript/CSS 提供用户界面并处理用户操作。客户端代码有点大，因为它尽可能避免回发；它只回发以获取当前数独谜题的解决方案。服务器上的事件处理代码保持最小化，并且禁用了视图状态。
注意：为了使文章篇幅合理，此处未对客户端代码进行解释。
以下列表显示了服务器端代码的起始部分。
protected void Page_Load(object sender, EventArgs e)))
{ if (Request["PuzzleData"] == null) return;
Server.ScriptTimeout = 30;
Sudoku mySudoku = new Sudoku(); int[,] grid = null;
int AllotedTime = 20; // in seconds
int Cost = mySudoku.SolveIt(Request["PuzzleData"], AllotedTime, out grid);
mySudoku = null;
outData.InnerText = GridToString(grid);
outCost.InnerText = Cost.ToString();
}
string GridToString(int[,] grid)
{ string str = "";
for (int i = 0; i < 9; i++)
{ for (int j = 0; j < 9; j++)
{ str += grid[i, j]; }
}
return str;
}
从前面的代码中可以很容易看出，数独谜题通过调用 mySudoku.SolveIt() 解决，其中 mySudoku 是 Sudoku 类实例的引用。该方法的第一参数是一个长度为 81 的输入字符串（数独谜题的编码），由数字 0-9 组成（0 表示相应的单元格为空）。AllotedTime 参数用于寻找解决方案的最大时间。最后一个参数（out 参数）是一个 2 维数组（网格），编码了谜题的解决方案。网格通过调用 GridToString() 方法转换为字符串。返回的 Cost 值是一个非负整数，表示返回解决方案的成本（违规次数）——成本为零表示返回的解决方案是最佳的（没有冲突）。最后，解决方案作为一些 HTML div 的内容保存，供客户端代码访问。
SolveIt() 方法包含了解决输入数独谜题的渐进式搜索算法。此方法的详细信息将在本文的后续部分给出。
随机搜索启发式算法
随机搜索启发式算法多年来一直是一个活跃的研究领域。这导致了各种元搜索框架的发展。其中包括禁忌搜索、模拟退火、遗传算法、可变邻域搜索以及其他统称为贪婪随机自适应搜索过程 (GRASP) 的迭代局部搜索 (ILS) 启发式算法。
随机搜索算法的一个共同特征是它们是非确定性的——决定接下来要追求哪个搜索路径通常是随机确定的。因此，随机搜索算法在每次运行中通常会产生不同的解决方案。尽管它们不能保证找到最优解决方案，但随机搜索算法通常可以快速找到接近最优的解决方案。
什么是渐进式搜索？
以下列表显示了用伪代码表示的渐进式搜索算法。
void ProgressiveSearch()
{ PQueue = new PriortyQueue();
NBSIZE = 50;
Threshold = some value; // Pick a value for the Threshold parameter
smallThreshold = some value; // Pick a value for smallThreshold parameter
Let X be an initial solution;
BestX = X;
BestCost = f(X);
PQueue.Enqueue(X,f(x)); // Use f(x) as the priority of x
while (PQueue not empty)
{ X = PQueue.Dequeue();
nbcount =0; // count of generated neighbors
while (nbcount < NBSIZE)
{ if (TimeElapsed > MaximumAllowedTime) return;
X1 = NewSolution(X); // Generate a solution X1 by mutation of X
nbcount = nbcount+1;
if (f(X1) < BestCost)
{ BestX = X1;
BestCost = f(X1);
if (BestCost == 0) return; // optimal solution is found
X = X1; nbcount = 0;
}
else if (f(X1) <= BestCost + smallThreshold) // Progressive search here
{ PQueue.Enqueue(X1, f(X1));
// Reset current solution to X1
X = X1; nbcount = 0;
}
else if (f(X1) <= BestCost + Threshold)
{ PQueue.Enqueue(X1, f(X1)); }
}
}
}
渐进式搜索的基本思想是保留（在优先队列中）一组解决方案，这些解决方案在当前最佳解决方案的某个阈值（Threshold 参数）内，以便由 NewSolution() 方法进一步变异。该算法围绕当前解决方案生成并入队最多 NBSIZE（邻域大小）个解决方案，但如果找到更好的解决方案（或非常接近当前最佳解决方案的解决方案），则当前解决方案将重置为新找到的解决方案。
渐进式搜索有一个**显著特点**（也是命名原因）
当前解将立即重置为与当前最佳解具有相同成本（或非常接近的成本，即在 `smallThreshold` 内）的任何新发现的解。
这已被发现可以加速向更好解决方案的进展。对这种行为的一个可能解释是：对 `NewSolution()` 的调用通过微小的步骤进入解决方案空间，这使得击败当前最佳解决方案的可能性很小；然而，如果从几个附近的解决方案级联移动，则击败当前最佳解决方案的机会就会增加。偏爱探索成本与当前最佳解决方案相等的解决方案是爬山（贪婪）算法的一个特征，只是在爬山算法中，集合的大小限制为一个解决方案（即当前最佳解决方案）。
四季皆宜的优先队列
优先队列适用于迭代搜索，因为我们可以利用优先级度量来对迄今为止找到的解进行排序。使用最小化优先队列（我们使用最小堆），我们可以简单地使用惩罚成本函数 f(X) 作为 X 的优先级。通过这种方式，我们倾向于探索接近当前最佳解的解。实验表明，如上所述的渐进式搜索对于大型优化问题（例如找到最大独立集或最小着色）表现良好。然而，实验也表明，向最优解的进展速度高度依赖于阈值，并且通常需要在多次运行中尝试不同的设置。接下来，我们提出一种机制来
（1）避免队列变得过大，以及
（2）避免使用阈值参数。
为了防止队列变得过大，我们使用一个 `MaxSize` 属性；如果设置，则队列中的项目永远不会超过 `MaxSize`。为了避免使用阈值，我们采用了一个技巧。我们希望队列包含在迄今为止找到的“最佳”项目的一定阈值内的项目（解决方案）。我们将以优先级的“反向”插入项目（用户只需使用“成本的负值”作为优先级）。这样，最差的项目将位于队列的根部。为了实现这种行为，我们只修改入队操作如下：如果待入队的项目 X 的优先级比根部差，并且队列中当前的项目数量等于 `MaxSize`，则不插入 X；否则，插入 X（如果没有空间，则先将根部项目出队）。
以下列表显示了渐进式搜索的简化版本，该版本利用了固定大小的队列并避免了使用 `Threshold` 参数。请注意，前一版本中的最后一个 else-if 块现已删除。大多数情况下，`smallThreshold` 参数可以设置为 0（即删除）；它保留是为了通用性。
void ProgressiveSearch()
{ PQueue = new PriortyQueue();
PQueue.MaxSize = 20; // Use a fixed-size queue
NBSIZE = 50;
smallThreshold = some value; // Pick a value for smallThreshold parameter
Let X be an initial solution;
BestX = X; BestCost = f(X);
PQueue.Enqueue(X,-f(X)); // Use –f(X) as the priority of X
while (true) // Queue-processing loop
{ X = PQueue.RandomItem(); // Use RandomItem instead of Dequeue
nbcount =0;
while (nbcount < NBSIZE) // Local search and mutation loop
{ if (TimeElapsed > MaximumAllowedTime) return;
X1 = NewSolution(X); // Generate a solution X1 by mutation of X
nbcount = nbcount+1;
PQueue.Enqueue(X1,-f(X1)); // Use –f(X1) as the priority of X1
if (f(X1) < BestCost)
{ BestX = X1;
BestCost = f(X1);
if (BestCost == 0) return; // optimal solution is found
X = X1; nbcount = 0;
}
else if (f(X1) <= BestCost + smallThreshold) // Progressive search here
{ X = X1; nbcount = 0; }
}
}
}
请注意，由于最差的元素位于根部，我们不能使用出队操作来获取有利的元素；相反，我们使用对 RandomItem() 的调用来从队列中获取一个随机元素。另外，请注意，在此版本的渐进式搜索中，我们已经消除了对空队列的测试，因为队列不可能变空。
使用渐进式搜索的框架
渐进式搜索是一种元搜索算法。要将其用于特定问题，我们必须开发其他几个辅助算法。简而言之，我们必须实现以下步骤
- 指定适当的数据结构来编码解决方案。
- 指定变异解决方案以获得相邻解决方案的过程。
- 定义一个适当的惩罚成本函数来衡量解决方案的质量（接近最优的程度）。
为了方便上述操作，拥有一个 `Solution` 类是合适的。该类用于编码当前问题的解决方案（好的或坏的）；它包含以下方法：`SetInitialSolution()` 用于构建并返回一个初始解决方案，`ComputeMeasure()` 用于返回解决方案的成本，`NewSolution()` 用于将一个解决方案变异成一个新的解决方案。
NewSolution() 方法具有以下典型结构
Solution NewSolution()
{ Solution s1 = this.CopySolution();
// Now mutate s1 then compute its cost
return s1;
}
它通过调用 CopySolution() 复制传入的解决方案开始。这样我们就可以保持旧解决方案的完整性，以备将来变异。然后我们变异副本并计算其成本。对于变异，我们通常使用一些简单的随机修改。例如，对于在给定图 G 中寻找大小为 k 的独立集，我们可以将解决方案编码为顶点集 S，该顶点集是独立集的潜在候选。然后作为 S 的变异，我们随机从 S 中选择一个顶点，并将其与从 S 外部随机选择的另一个顶点交换。为了以系统而非随机的方式选择顶点，我们可以将 nbcount 传递给 NewSolution() 并将其用于顶点选择（例如，表达式 nbcount mod |S| 标识 S 中的一个顶点，表达式 nbcount mod (|G|-|S|) 标识 S 外部的一个顶点）。
关于 `ComputeMeasure()`，以增量方式计算效率更高。也就是说，由于新解决方案 X 是旧解决方案 X' 的变异，那么 `f(X)` 应该用 `f(X')` 来表示。然而，找到正确的表达式通常很复杂；因此，建议最初应该以直接的方式计算 f（无论如何，初始解决方案都需要这样做），然后稍后尝试对其进行优化。
通过渐进式搜索解决数独
我们的程序代码由两个类（位于 App_Code 文件夹中）组成：`Sudoku` 类和 `Solution` 类。`Sudoku` 类主要由 `SolveIt()` 方法（作为与外界的接口）、`ProgressiveSearch()` 和其他一些辅助方法/对象组成，包括一个用于编码数独谜题的 `FixedCells` 数组。
以下显示了 `Solution` 类的程序代码。
class Solution // Solution class for Sudoku puzzle
{
// static Random rand = new Random(); // This causes a problem for concurrent web requests
// Instead, the random object is a member of the Sudoku instance and passed to the Solution() constructor
Random rand;
internal int[,] grid = new int[9, 9];
internal float Cost; // The PQUEUE class uses float for priority values
int[] FixedCell;
internal Solution(int[] FixedCell, Random rand) { this.FixedCell = FixedCell; this.rand = rand; }
internal void SetInitialSolution()// set initial grid as 1,2 .. 9 in each row
{ for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
{ grid[i, j] = j + 1; }
Cost = ComputeMeasure();
}
int ComputeMeasure()
{ int[] perm = new int[9];
int sum = 0;
for (int k = 0; k < 27; k++)
{ for (int i = 0; i < 9; i++) perm[i] = 0;
for (int i = 0; i < 9; i++) perm[grid[Sudoku.PosRow[k, i], Sudoku.PosCol[k, i]] - 1] += 1;
for (int i = 0; i < 9; i++)
{ if (perm[i] == 0) sum++; // digit i is missing
else if (perm[i] > 1) sum += perm[i] - 1; // digit i occurs more than once
}
}
// check fixed cells; have a large weight (per cell) here than above
for (int i = 0; i < 81; i++)
if (FixedCell[i] != 0)
if (grid[i / 9, i % 9] != FixedCell[i]) sum = sum + 8;
return sum;
}
Solution CopySolution()
{ Solution s = new Solution(FixedCell,rand);
Array.Copy(grid, s.grid, grid.Length);
// s.Cost = Cost;
return s;
}
internal Solution NewSolution( )
{ Solution s1 = this.CopySolution();
int i = rand.Next(81);
int j = i;
while (i == j) { j = rand.Next(81); }
int t = s1.grid[i / 9, i % 9];
s1.grid[i / 9, i % 9] = s1.grid[j / 9, j % 9];
s1.grid[j / 9, j % 9] = t;
s1.Cost = s1.ComputeMeasure();
return s1;
}
}
该类使用数组 `grid[0..8,0..8]` 来存储 9x9 数独谜题的解决方案。对于初始解决方案，我们将每行填充数字 1 到 9。
对于解的变异，我们只需随机选择两个单元格并交换它们的值。惩罚成本函数（作为 `ComputeMeasure()` 实例方法实现）本质上衡量了一个解与正确（即无冲突）解的接近程度。
令 `Ri`（对于 `i`=0 到 8）表示放置在第 `i` 行的数字集合。同样，令 `Cj` [`Bk`] 表示放置在第 `j` 列 [第 `k` 块] 的数字集合。（注意：在指定行（列或块）时，我们从 0 开始索引）。总共有 27 个集合。这些集合在 `Sudoku` 类中定义为（其中 `PosRow` [`PosCol`] 给出行 [列] 号）
internal static int[,] PosRow = new int[27,9];
internal static int[,] PosCol = new int[27,9];
static void SetRowColPos()
{ // set PosRow/PosCol to correspond to 9 row-constraints, 9 col-constraints and 9 box-constrains
// Code omitted for brevity
}
一个正确的解决方案必须确保这些集合中的每一个都包含数字 1-9，任何违反都会导致成本增加 1。这由 ComputeMeasure() 方法中的第一个 for 块处理。此外，一个正确的解决方案必须有某些单元格填充特定的数字。为此，我们使用在 Sudoku 类中定义为实例成员的 FixedCell 数组，其中 FixedCell[i]=j 表示位置 i 的单元格固定为包含 j，否则为 0。如果网格单元格不包含指定的数字，则此类违反会使成本增加 8。这由第二个 for 块处理。
通过为固定单元格违规分配较大的成本值（例如 100），算法被强制尽早解决固定单元格。然而，这被发现会减慢算法。此外，如果初始解决方案保持固定单元格不变，算法也会减慢。这是一个普遍的观察，如果问题的约束逐渐强制执行而不是过早强制执行，渐进式搜索效果更好。
结论
数独求解器是证明渐进式搜索有效性的一个很好的例子。该求解器已在流行的浏览器上进行测试，并发现其工作正常。
历史
- 2013年11月22日：版本 1.0
许可证
本文及其任何相关的源代码和文件均根据Code Project Open License (CPOL) 授权。