基于C++的递归和回溯国际象棋女王安全算法

资源下载地址：https://download.csdn.net/download/sheziqiong/85722216

熟悉递归的基本思想 能够设计自己的递归函数。

关键是设计基本案例和感应步骤 了解回溯算法。

可以使用递归和回溯来解决特定问题。

Windows 7（或更高版本）+ Visual Studio 2010（或更高版本）

制定并验证一个程序，将八个女王放在棋盘上，这样就不会有女王受到任何其他女王的攻击。

定义一个名为 eightqueen 的类。我把所有的方法都放进去了，包括递归方法。 通过构造函数创建默认棋盘。然后定义方法 printchess（） 和 goBack（） 它们是更简单的。

最重要的方法是 isValid（） 和 findPosition（）。 但首先，我需要仔细考虑如何在 main（）函数中放置 8 个女王。事实证明，最简单的方法是从国际象棋[0][0]开始逐排放置皇后，因为每行必须有 1 个 queen。

因此，在 isValid（） 中，我只检查参数 r 和 c（即 chess[r][c]）给出的位置“上面的行和列”，即：行 r 的每一列，左上角线和右上角的对角线。由于每次我每排放 1 个女王，就没有必要检查行中的国际象棋[r][c]。此外，默认返回值应为 1，因为除上述三种情况外，所有情况均有效。 在方法 findPosition（）中，第一步应该是检查位置 chess[r][c]，之后，如果它有效，它可以转到下一行找到一个可能的位置。

为了在下一行中搜索可能的女王并考虑到每列可能都有一个，我使用循环遍历每列，检查是否存在有效位置，即使用参数 r + 1，i 回溯 findPosition（）（i 是循环中的列）。换句话说，我对每一行都调用此方法来搜索女王。如果有一个有效的位置，在国际象棋中输入 1[r+1][i]。

相反，如果最后一行没有有效的女王（即直到位置国际象棋[7][7]无效），它应该 goBack（）这意味着最后一个位置 - 国际象棋[r][c]是错误的。（r+1 被转移到 findPosition（） 所以当它被返回时，最后一个位置是 chess[r][c]）

还需要提到的是，由于我转移参数 r+ 1 以在下一行中找到女王，因此 findPosition（）的末尾应该是 r + 1

以下是输出 92 个解决方案的过程： 为了找到位置并记录它们，并考虑到每行中必须有一个女王，我将 row 设置为数组，其值表示有效列。此外，棋盘（a[9][9]）和解数（t）是外部变量。 为了方便起见，我将棋盘设置为具有 9 列和行的数组。在 Judge（） 中，使用 abs（） 也更容易使用 abs（） — 查找对角线位置的绝对函数。在 findQueens（） 中，有一个递归调用，以便在下一行中找到一个位置。如果它返回 void，这意味着下一行中没有有效位置，则每个位置将有 0。

检查的顺序是 Valid（）和回溯以及如何同时在每条行中找到位置是困难的。很长一段时间以来，我一直在思考这两个序列，因为反向搜索和 goBack（）的结束决定了 findPosition（）的位置。

事实证明，理解回溯的最简单方法是首先找到递归的结尾，然后返回所需的值。这意味着，在找到有效位置之前对回避的停止进行编码。 为了找到可能的位置，我的方法是遍历每一列。虽然这不是一个有效的方法，但它仍然是找到一个可能的女王的安全方法。我的方法只能从国际象棋[0][0]开始找到一个解决方案。
是找到一个可能的女王的安全方法。我的方法只能从国际象棋[0][0]开始找到一个解决方案。

资源下载地址：https://download.csdn.net/download/sheziqiong/85722216
资源下载地址：https://download.csdn.net/download/sheziqiong/85722216