回溯解决八皇后问题

• 下载 EightQueens.zip - 16.6 KB

摘要

回溯是一种标准的方法，用于解决特定类型的“约束满足”问题。这些问题定义了一组约束来验证任何尝试。最原始的解决方法是“蛮力法”——也就是说：简单地尝试所有可能性;-)

现在，如果可以将尝试分步构建，则回溯是适用的（并且是一个极大的改进）。然后，您可以在每一步检查规则，并在失败时跳过该方向上所有进一步的步骤。

注意：例如，在路径查找问题中，回溯是可能的，但效率不高。最好使用 FloodFill 变体、Dijkstra 或其他方法。

即使是骑士游走谜题或青蛙跳跃，通过考虑附加的启发式方法也可以做得更好。

八皇后问题

是一个很好的示例谜题，回溯方法适用且高效——它的定义是：

“找出在棋盘上放置八个皇后的所有方法，每个皇后占位：1) 自己的行 2) 自己的列 3) 自己的升对角线 4) 自己的降对角线”

我的皇后问题

对我来说，最困难的是改变看待棋盘的方式：从回溯的角度来看，它不是一个二维矩阵，而是一个深度为八、每个节点有八个子节点的树状结构。

或者让我换种说法：在八皇后问题中，回溯不使用嵌套的 x/y 迭代。取而代之的是，它逐行前进，在每一行上，它会检查可以继续前进的列。如果没有当前行中可以放置皇后的有效列，它会（按行）回溯。

这种视角从一开始就至关重要：上面提到的四个约束中的第一个可以被删除，因为从行到行的移动意味着行冲突永远不会发生。

一项“数学发现” ;-)

在思考一种有效的方法来检查剩余的三个规则时，我产生了使用 3 个哈希集合的想法，它们存储了已占用的 1) 列 2) 升对角线 3) 降对角线的标识符。
1) 是微不足道的，因为列是编号的。
2) 也广为人知（对我而言）：在二维矩阵中，降对角线上的 x-y 差是恒定的。
3) （你无法想象，我花了多大的力气才弄清楚这个简单的真理）：在升对角线上，x+y和是恒定的。

为了弄清楚我的意思，我创建了一张图片（红色数字：x-y，蓝色数字：x+y）

代码

约束验证机制

您可以看到：最简单的数学可以推导出每个棋盘格在 3 个（剩余的）“维度”中的“约束 ID”：1) 列 2) 升对角线 3) 降对角线。
Hashset<int> 是存储这些约束 ID 的完美方式，因为它的 Add() 方法会拒绝添加重复的 ID。此外，在拒绝时，该方法会返回 false。

// 3 constraints: column, ascending diagonale, descending diagonale
private static HashSet<int>[] _Occupieds = Enumerable.Range(0, 3).Select(i => new HashSet<int>()).ToArray();
private static Func<int, int, int>[] _GetOccupyIds = new Func<int, int, int>[] { 
         (x, y) => x, 
         (x, y) => x + y, 
         (x, y) => x - y };

private static bool Occupy(int col, int row) {
   int[] tempIds = new int[3];  // to store Ids for possibly rollback
   for (var i = 3; i-- > 0; ) {
      tempIds[i] = _GetOccupyIds[i](col, row);
      if (!_Occupieds[i].Add(tempIds[i])) {
         while (++i < 3) _Occupieds[i].Remove(tempIds[i]);  // rollback
         return false;
      }
   }
   return true;
}
private static void DeOccupy(int col, int row) {
   for (var i = 3; i-- > 0; ) _Occupieds[i].Remove(_GetOccupyIds[i](col, row));
}

有 3 个 HashSets 和 3 个 Func<int, int> 委托。
在尝试“在棋盘上放置皇后”时，Occupy() 方法使用委托来计算每个“维度”（列、升对角线、降对角线）的“ID”。
然后尝试将其添加到相应的哈希集中。如果失败，则在退出并返回 false 之前，删除可能之前添加的其他“维度”的 ID。
另一个方法——DeOccupy()——在回溯步骤后退时（“从棋盘上移除皇后”）需要移除先前存储的约束 ID。

搜索算法

public static List<int[]> FindAll() {
   var queens = new Stack<int>();
   var output = new List<int[]>();
   Action recurse = null;
   recurse = () => {
      var row = queens.Count;
      if (row == _BoardSize) {
         output.Add(queens.ToArray());
         return;
      }
      for (var col = 0; col < _BoardSize; col++) {
         if (Occupy(col, row)) {
            queens.Push(col);
            recurse();
            queens.Pop();
            DeOccupy(col, row);
         }
      }
   };
   recurse();
   return output;
}

如摘要中所述，回溯是逐步构建尝试的。对于八皇后问题，这意味着：逐行。每一步都占用一个特定的列（皇后放置在该列中——针对该行）。
长话短说：queens 堆栈中的整数是当前尝试及其进展状态的完整表示。

注意我最喜欢的一个——本地递归
整个算法都包含在显示的方法中，并且递归部分由局部变量中的匿名方法完成，即命名为“recurse”;-)
这样我就可以保留 queens 堆栈和 output 列表作为局部变量——既不需要将它们设计为类变量，也不需要将它们作为参数传递给所有将发生的递归调用。

让我们更深入地研究匿名递归方法做了什么
var row = queens.Count;
正如所说，堆栈计数等于当前尝试的进展状态，也等于正在检查的行。
相应地，接下来的 3 行检查尝试状态是否“完成”，并在完成时做出反应。

否则，检查每一列，如果您找到一个您可以成功占用的位置，请将其记录在堆栈上并递归。
递归之后是回溯算法的回溯：从堆栈中移除尝试步骤，并移除其“占用 ID”。

您可以看到：一个绝对普通的递归方法。

输出

如上所示，FindAll() 返回解决方案作为 List<int[]>。让我们看看如何将一个 int[] 转换为国际象棋爱好者能理解的“A1”格式的 string

static void Main(string[] args) {
   Func<int[], string> getA1addresses = columnList => string.Concat(columnList.Select((col, i) => " " + (char)('a' + col) + (i + 1)));
   List<int[]> columnLists = Find8Queens.FindAll();
   Console.WriteLine(string.Join("\n", columnLists.Select(getA1addresses)));
   Console.WriteLine(columnLists.Count.ToString() + " Results");
   Console.Read();
}

第一行完成了这项工作

Func<int[], string> getA1addresses =
   columnList => string.Concat(columnList.Select((col, i) => " " + (char)('a' + col) + (i + 1)));

通过将列 col 添加到 'a' 来获取字母
列表索引 i 是行，但它是从零开始的。因此，根据“A1”格式，将其加 1 以获得数字。
将以上内容附加到 " "，您就得到了列列表中一个条目的“A1”格式显示。
将所有八个条目连接起来，结果字符串就会告诉国际象棋爱好者需要知道什么：在哪里放置皇后;-)

第二个：做同样的事情，但非常不同

荣誉归功于 CodeProject 会员 **djmarcus**——他发表了一条评论，并提供了一种完全不同的验证八皇后规则的概念——包括实现它的代码。
如果您愿意，请参阅本文讨论部分中的他的评论。

验证概念 II

djmarcus 指出，棋盘上的所有方格都可以简单地表示为单个 uint64 中的位。这提供了为皇后可以占据的每个位置创建“攻击向量”的机会——如所述——在一个数字中。现在，通过简单的按位“And”运算，您可以检查一个位置是否“受到攻击”。此外，通过简单的“Inclusive Or”运算，您可以累积添加多个攻击向量，以及累积多个皇后位置（当多个皇后成功放置在棋盘上时）。

代码 II

我只展示递归的 solve() 函数——因为它主要部分，并且在攻击向量的准备工作更加耗时的情况下，它最具说服力。

private bool solve(int row, ulong queens, ulong attacks) {
   if (row == 8) { displayVector("Solution:", queens); return foundSolution; }
   for (var col = 0; col < 8; col++) {
      ulong positionVector = _positionVectors[row * 8 + col];
      if ((attacks & positionVector) == 0) {
         if (solve(row + 1, queens | positionVector, attacks | _attackVectors[row * 8 + col])) 
            return foundSolution;
      }
   }
   return false;   //-- no solution on this row; backup
}

if (row == 8) { displayVector("Solution:", queens); return foundSolution; }
再次，首先检查是否达到了行最大大小，这表示找到解决方案并导致输出和退出函数。

ulong positionVector = _positionVectors[row * 8 + col];
(尚未提及：) 还准备了一个“positionVectors”数组，以便为定义的行/列位置提供其 ulong 表示形式。

if ((attacks & positionVector) == 0) {
这是检查当前位置是否与任何攻击（位）冲突。

if (solve(row + 1, queens | positionVector, attacks | _attackVectors[row * 8 + col])) return foundSolution;
如果没有冲突（在前一行中已检查过），则递归向前推进。此前进的尝试进度由传递给自调用的参数的三种修改表示：

1. 增加行：row + 1
2. 累加添加成功的**新**位置：queens | positionVector
3. 累加添加相关的攻击向量：attacks | _attackVectors[row * 8 + col]

这精确地模拟了一个国际象棋玩家在下一行的可用列中放置下一个皇后的过程：1) 他进入下一行，2) 又多了一个皇后，3) 要考虑的受攻击方格组又多了一组。

如前所述：为了简洁起见，我没有展示攻击向量和位置向量的准备代码。但即便如此，这些准备工作对于性能也至关重要：每次尝试时，无需进行任何计算——而是可以直接从数组中获取准备好的结果。
请记住：存储准备好的结果而不是每次都计算它们是优化算法速度的一种非常有效的技术。

输出 II

就连输出也大不相同。当我组成一个带有“A1”格式位置的行时，djmarcus 的输出创建了一种“ASCII 艺术”——比较一下

a1 e2 h3 f4 c5 g6 b7 d8

 Q  *  *  *  *  *  *  *
 *  *  *  *  Q  *  *  *
 *  *  *  *  *  *  *  Q
 *  *  *  *  *  Q  *  *
 *  *  Q  *  *  *  *  *
 *  *  *  *  *  *  Q  *
 *  Q  *  *  *  *  *  *
 *  *  *  Q  *  *  *  *

djmarcus 的输出代码，使用两个嵌套的 for 循环

for(int row = 0; row < 8; row++) {
   Console.WriteLine();
   for (int col = 0; col < 8; col++) Console.Write((
      queens & _positionVectors[row * 8 + col]) != 0 ? " Q " : " * ");
}

关注点

对我来说，“数学发现”是我学到的最重要的事情。例如，现在我看到了定义二维矩阵的两个维度（甚至寻址元素）的替代方法，而不是列和行。
我的意思是：字段 (2, 4)——通过升/降对角线寻址，它将显示为：(6, -2)
(对照上面的图片检查一下 :-))

也许对你来说，“本地递归”这个技巧是最巧妙的——因为它相当不为人知，尽管它在很多情况下都有优势。

最后，我很高兴能展示第二种非常不同的方法，并且这两种方法都做了同样的事情，即通过回溯解决八皇后问题。
请注意，在我的方法中，我有明确的回溯操作：从尝试堆栈中弹出失败的皇后，从哈希集中移除她的“占用 ID”——这些事情 djmarcus 避免了，因为他可以将完整的尝试状态——所有皇后、所有受攻击方格——通过两个单独的数字传递给递归调用。因此，从递归返回足以实现回溯，并且他可以直接继续使用进入递归之前的状态。

关于比较这两种方法以及搜索优缺点的分析，还可以说很多。我的观点是，也要关注共同点，这使得主要原则非常清晰地显现出来，我认为。

结论

我们看到了回溯作为解决“约束满足问题”的方法，当尝试可以分步开发时适用。其原则是，一旦尝试变得无效，就将其丢弃，并返回到尝试尚未充分开发但仍然有效的前一个状态，并以另一种方式继续开发。
例如，在八皇后问题中，如果前两行已经有两个皇后互相攻击，则可以跳过所有进一步的尝试。

通常，这种回溯到前一个状态是通过递归实现的，在这两个示例中也是如此。
事实上，回溯也可以被视为将问题组织成一个决策树，并对其进行深度优先遍历，跳过所有不值得分支。
(注意：像任何深度优先遍历一样，回溯也可以通过非递归实现来完成（但本文中没有）。)