数独作为 CSP
4.31/5 (9投票s)
使用 CSP 算法和技术解决 NxN 数独难题。
引言
我在大学学习了一门人工智能课程，并了解了约束满足问题（CSP）。讲师要求做一些小型求解器项目，我心想……数独！这是一个经典的 CSP。
数独？
我想大家都知道数独；对于那些不知道的人，请尝试谷歌或维基百科。
数独的基本规则是：
- 对于每行/列/区域，你必须使用不同的数字。
- 所有单元格都必须被赋值。
数独棋盘是一个 NxN 矩阵，这意味着我们需要使用范围 [1..N] 内的数字。
什么是 CSP？
CSP 或约束满足问题由三个部分定义：
- 一个有限的变量集。
- 一个将每个变量映射到有限**域**的函数。
- 一个有限的约束集。
**约束传播**和**回溯搜索**是 CSP 中的一些技术，我将在本文中描述这两个概念。
设置问题（或者，这与数独有什么关系？）
在我们开始之前，我想列出一些定义：
- 单元格：数独网格中的一个“方格”。
- 网格：代表数独棋盘。
- 同伴：所有单元格的邻居；邻居是与该单元格在同一单元中的单元格。
- 单元：每行、每列和每个区域的 `GRIDSIZE` 个单元格的集合。
- 区域：一个小的正方形，通常大小为 sqrt(N) x sqrt(N)。
这里的算法将使用基于 CSP 思想的两种方法来描述：约束传播和回溯搜索。
首先，我们需要将数独问题定义为 CSP。
- 变量：变量将是网格上的每个单元格。
- 域：域将是 1 到 `GRIDSIZE` 之间的任何数字。如果 `GRIDSIZE` > 9，我将使用从“A”到……我需要多少字母，其中“A”等于 10，“B”等于 11，依此类推。
- 约束：约束是
- 相同的数字（或字母）不能在同一行中出现两次（或更多）。
- 相同的数字（或字母）不能在同一列中出现两次（或更多）。
- 相同的数字（或字母）不能在同一区域中出现两次（或更多）。
我将变量的域实现为字符串（为了效率），当任何单元格域长度变为 1 时，我们就会得到一个解决方案！
约束传播
当然，我可以直接进行一些暴力破解，检查选项并找到解决方案（这可能需要时间，但它有效），但我能做得更好吗？是的，我可以。
CSP 中的一个关键问题是约束传播；我们将看到两种类型：前向检查和弧一致性。
前向检查
最基本的约束传播是前向检查。这意味着提前消除与未赋值变量域中的约束不匹配的可能性。例如，如果我们将数字“d”赋值给单元格 c1，我们就会从该单元格所有同伴的域中消除“d”。
MyCell[,] EliminateFC(MyCell[,] branch, Pos p, char val)
{
branch[p.ln, p.col].Value =
branch[p.ln, p.col].Value.Replace(val.ToString(), "");
return branch;
}
MyCell[,] AssignFC(MyCell[,] branch, Pos p, char val)
{
for (int i = 0; i < branch[p.ln, p.col].Peers.Count; i++)
{
branch[branch[p.ln, p.col].Peers[i].ln, branch[p.ln, p.col].Peers[i].col].Value =
branch[branch[p.ln, p.col].Peers[i].ln,
branch[p.ln, p.col].Peers[i].col].Value.Replace(val.ToString(), "");
if (branch[branch[p.ln, p.col].Peers[i].ln,
branch[p.ln, p.col].Peers[i].col].Value.Length == 0)
return null;
}
branch[p.ln, p.col].Value = val.ToString();
branch[p.ln, p.col].assigned = true;
return branch;
}
弧一致性
我所做的并非完全是弧一致性，而是基于它。我正在进行三种类型的缩减，有些是为了缩小域，有些只是为了提前发现错误以节省时间
- 当我们要将数字“d”分配给单元格 s1 时，我们使用 assign(cells, s, d)。通过这样做，我想将值 d 分配给 s（哒……），但我也想从其同伴中消除这种可能性（就像 FC 所做的那样，告诉我一些新的东西！）。如果消除导致其中一个（或一些）同伴只剩下一个可能性，我们称之为 d2，我们想将 d2 分配给它，通过这样做，从其所有同伴的同伴中消除 d2，这可能会引发另一个连锁反应。这种连锁反应简单地称为*约束传播*：对一个单元格施加约束可能会导致对其他单元格施加进一步的约束。
- 第二种类型：假设我们只是将 6 从单元格 [0,0] 的可能值中排除，然后我们查看 [0,0] 的第一个单元（行单元），发现唯一可能包含 6 的单元格是 [0,7]。我们将 6 分配给 [0,7]，然后再次发生连锁反应。
- 最后一种是错误预检查，因为数独被声明为 AllDiff 约束。我们可以通过以下简单形式的不一致性检测来提前检查有效解：如果约束中涉及 M 个变量，并且它们总共有 N 个可能的不同值，并且 M > N，那么该约束就无法满足（我们就不必在这个最终会出错的分支上浪费时间）。
/// <summary>
/// Assigns the with ac3.
/// </summary>
/// <param name="Cells">The cells.</param>
/// <param name="assignmentPosition">The assignment position.</param>
/// <param name="assignmentValue">The assignment value.</param>
/// <returns></returns>
MyCell[,] AssignWithAc3(MyCell[,] Cells, Pos assignmentPosition, char assignmentValue)
{
for (int i = 0; i < m_gridSize; i++)
if (m_MaxDomain[i] != assignmentValue)
{
Cells = EliminateWithAc3(Cells, assignmentPosition, m_MaxDomain[i]);
if (Cells == null)
return null;
}
Cells[assignmentPosition.ln, assignmentPosition.col].assigned = true;
return Cells;
}
/// <summary>
/// Eliminates the with ac3.
/// </summary>
/// <param name="Cells">The cells.</param>
/// <param name="assignmentPosition">The assignment position.</param>
/// <param name="assignmentValue">The assignment value.</param>
/// <returns></returns>
MyCell[,] EliminateWithAc3(MyCell[,] Cells,
Pos assignmentPosition, char assignmentValue)
{
//Check if already eliminated :
if (!Cells[assignmentPosition.ln, assignmentPosition.col].Value.Contains(
assignmentValue.ToString()))
return Cells;
//eliminating :
Cells[assignmentPosition.ln, assignmentPosition.col].Value =
Cells[assignmentPosition.ln, assignmentPosition.col].Value.Replace(
assignmentValue.ToString(), "");
//check for inconsistency.
if (Cells[assignmentPosition.ln, assignmentPosition.col].Value.Length == 0)
return null;
if (Cells[assignmentPosition.ln, assignmentPosition.col].Value.Length == 1)
{
Cells[assignmentPosition.ln, assignmentPosition.col].assigned = true;
char val2 = Cells[assignmentPosition.ln, assignmentPosition.col].Value[0];
for (int i = 0; i < Cells[assignmentPosition.ln,
assignmentPosition.col].Peers.Count; i++)
{
Cells = EliminateWithAc3(Cells, Cells[assignmentPosition.ln,
assignmentPosition.col].Peers[i], val2);
if (Cells == null)
return null;
}
}
for (int i = 0; i < 3; i++)
{
int n = m_gridSize;
int m = 0;
List<Pos> val_place = new List<Pos>();
for (int j = 0; j < Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i].Count; j++)
{
if (Cells[Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].ln,
Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].col].assigned)
n--;
else
m++;
if (Cells[Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].ln,
Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].col].Value.Contains(
assignmentValue.ToString()))
{
val_place.Add(new Pos(Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].ln,
Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].col));
}
}
if (m > n)
return null;
if (val_place.Count == 0)
return null;
if (val_place.Count == 1)
{
Cells = AssignWithAc3(Cells, val_place[0], assignmentValue);
if (Cells == null)
return null;
}
}
return Cells;
}
好了，这是第一步，但有些数独并没有给我们任何选择，迫使我们进行一些猜测才能找到解决方案。但是，如果我们猜错了怎么办？我们必须回溯，因此我们有了回溯搜索，简单吗？它会变得更聪明，你等着瞧。
回溯搜索
通过使用回溯搜索，我们可以遍历树并检查任何可能性（但如果我们足够聪明，就不需要这样做），以找出低效之处。但是，由于约束的存在，每个分支变得越来越小，如果我们使用一些启发式方法，我们可以做得更好！
回溯搜索是这样进行的：如果已经有了有效解，则返回该解；如果没有，则选择一个未填充的单元格（哪个单元格？我们稍后会看到……！）并考虑其所有可能的值（按什么顺序？）。一次一个，我们尝试为每个单元格赋值，并从结果位置继续搜索。
MyCell[,] backtrackingSearch(MyCell[,] branch)
{
MyCell[,] ret;
if (branch == null) return null;
if (isFinish(branch)) return branch;
Pos s = SelectUnassignedVariable(branch);
while (branch[s.ln, s.col].Value.Length > 0)
{
char c = SelectDomainValue(branch, s);
ret = backtrackingSearch(Assign(Clone(branch), s, c));
if (ret != null)
return ret;
m_NumOfBacktracking++;
branch = Eliminate(branch, s, c);
if (branch == null) return null;
}
变量启发式（或者：我应该先尝试哪个单元格？）
在前面提到的搜索算法中，我使用了 `SelectUnassignedVariable` 函数，但它没有说明任何准则。那是因为这个“函数”是一个委托，用于比较其他一些启发式。我将回溯搜索编写为通用的，我只是将委托值从一个更改为另一个。
那么，有哪些启发式呢？很多，我希望阅读本文的人能提出一些我可以探索和比较的东西。我将讨论经典的，以及我的程序实现的那些。
第一个未赋值
这必须是最简单的启发式方法了；它也非常快，但另一方面，它非常愚蠢。我们只是选择找到的第一个，它用于暴力搜索，但我们想比这更聪明一点。
Pos FirstUnassignedCell(MyCell[,] branch)
{
for (int i = 0; i < m_gridSize; i++)
for (int j = 0; j < m_gridSize; j++)
if (!branch[i, j].assigned)
return new Pos(i, j);
return null;
}
最小剩余值（MRV）启发式
好的，终于来了一个真正的启发式。在这个启发式中，我们将选择可能性最小的单元格。其逻辑是，它之所以好，是因为它猜对的几率最大。这也会最小化分支因子。
Pos MinimumRemainingValues(MyCell[,] branch)
{
int min = m_gridSize + 1;
Pos p=new Pos() ;
for (int i = 0; i < m_gridSize; i++)
for (int j = 0; j < m_gridSize; j++)
{
if ((!branch[i, j].assigned) &&
(branch[i, j].Value.Length < min))
{
p.ln = i;
p.col = j;
min = branch[i, j].Value.Length;
}
}
return p;
}
MRV + 最大度数 (MRV+MD)
好的，我们有 MRV，听起来不错，但也许我们可以做得更好。我们仍然使用 MRV，但现在作为决胜局。我们选择度数最大的单元格。单元格的度数是与该单元格受约束的未赋值单元格的数量。
Pos MRV_With_MD(MyCell[,] branch)
{
return MaxDegree(branch, MinimumRemainingValuesList(branch));
}
/// <summary>
/// gets a list of Minimum the remaining values Variables positions .
/// </summary>
/// <param name="branch">The branch.</param>
/// <returns></returns>
List<Pos> MinimumRemainingValuesList(MyCell[,] branch)
{
int min = m_gridSize + 1;
List<Pos> list = new List<Pos>();
for (int i = 0; i < m_gridSize; i++)
for (int j = 0; j < m_gridSize; j++)
{
if ((!(branch[i, j].assigned)) && (branch[i, j].Value.Length == min))
{
list.Add(new Pos(i, j));
continue;
}
if ((!(branch[i, j].assigned))&& (branch[i, j].Value.Length < min))
{
list.Clear();
min = branch[i, j].Value.Length;
list.Add(new Pos(i, j));
}
}
return list;
}
/// <summary>
/// get position of the variable it the maxumum degree from the positions in MRVS.
/// </summary>
/// <param name="branch">The branch.</param>
/// <param name="MRVS">The MRVS.</param>
/// <returns></returns>
Pos MaxDegree(MyCell [,]branch, List<Pos> MRVS)
{
int deg = -1;
Pos p =null;
for (int i = 0; i < MRVS.Count; i++)
{
int count = 0;
for (int k = 0; k < branch[MRVS[i].ln ,MRVS[i].col].Peers.Count; k++)
if (!branch[branch[MRVS[i].ln ,MRVS[i].col].Peers[k].ln,
branch[MRVS[i].ln ,MRVS[i].col].Peers[k].col].assigned)
count++;
if (count > deg)
{
deg = count;
p = MRVS[i];
}
}
return p;
}
这听起来不错，但会花费我们计算时间，所以值得吗？不总是。我们将在最后看到一些比较。
值启发式
好的，我们知道如何选择单元格，现在我们需要选择从可能性（域）中首先尝试哪个值，这称为**值启发式**。
按字典序启发式
和变量启发式一样，这里我们又从“平庸”的一个开始，我们只是选择第一个。
char LexicographicOrderFirst(MyCell[,] branch, Pos variablePosition)
{
return branch[variablePosition.ln, variablePosition.col].Value[0];
}
最小约束值启发式
在此启发式中，我们选择对所选单元格的同伴造成最小麻烦的值；例如，如果我们的单元格中可能包含 7 和 9，我们会检查 7 在该单元格的多少个同伴的域中出现，然后对 9 进行相同的操作；算法然后选择在该单元格同伴的域中出现次数最少的数字。
char LeastConstraintValue(MyCell[,] branch, Pos variablePosition)
{
int[] arr = new int[branch[variablePosition.ln, variablePosition.col].Value.Length];
for (int i = 0; i < arr.Length; i++)
arr[i] = 0;
for (int i = 0; i < branch[variablePosition.ln, variablePosition.col].Value.Length; i++)
for (int j = 0; j < branch[variablePosition.ln, variablePosition.col].Peers.Count; j++)
{
if (branch[branch[variablePosition.ln, variablePosition.col].Peers[j].ln,
branch[variablePosition.ln,
variablePosition.col].Peers[j].col].Value.Contains(
branch[variablePosition.ln, variablePosition.col].Value[i].ToString()))
arr[i]++;
}
return branch[variablePosition.ln, variablePosition.col].Value[GetMinIndex(arr)];
}
关注点
都听过了，都看过了！让我们看看它们是如何工作的
改进我的代码！！！
我发表这篇文章的关键原因是为了制作一个更好、更快的数独求解器，请帮助我做到这一点。
历史
- 首次发布于 2009 年 3 月 25 日。