回溯法实现“八皇后“问题（解答斜上方和斜下方判断问题）

问题描述：国际象棋里，棋盘为8×8格。皇后每步可以沿直线、斜线走任意格。假设将8个皇后放到国际象棋盘上，使其两两之间无法相互攻击，共有几种摆法？

代码如下：

#include <stdio.h>
int Queenes[8]={
    0},Counts=0;
int Check(int line,int list){
    
    //遍历该行之前的所有行
    int index;
    for (index=0; index<line; index++) {
    
    	//挨个取出前面行中皇后所在位置的列坐标
        int data=Queenes[index];
        //如果在同一列，该位置不能放
        if (list==data){
    
            return 0;
        }
        //如果当前位置的斜上方有皇后，在一条斜线上，也不行
        if ((index+data)==(line+list)){
    
            return 0;
        }
        //如果当前位置的斜下方有皇后，在一条斜线上，也不行
        if ((index-data)==(line-list)){
    
            return 0;
        }
    }
    //如果以上情况都不是，当前位置就可以放皇后
    return 1;
}

//输出语句
void print()
{
    
     int line;
     for (line = 0; line < 8; line++)
     {
    
           int list;
           for (list = 0; list < Queenes[line]; list++)
				printf("0");
           	printf("#");
           for (list = Queenes[line] + 1; list < 8; list++){
    
				printf("0");
           }
          printf("\n");
    }
     printf("================\n");
}

void eight_queen(int line){
    
     int list;
     //在数组中为0～7列
     for (list=0; list<8; list++) {
    
     //对于固定的行列，检查是否和之前的皇后位置冲突
           if (Check(line, list)) {
    
           //不冲突，以行为下标的数组位置记录列数
                Queenes[line]=list;
                 //如果最后一样也不冲突，证明为一个正确的摆法
                if (line==7) {
    
                     //统计摆法的Counts加1
            	     Counts++;
                    //输出这个摆法
                     print();
                    //每次成功，都要将数组重归为0
                    Queenes[line]=0;
                    return;
               }
              //继续判断下一样皇后的摆法，递归
              eight_queen(line+1);
              //不管成功失败，该位置都要重新归0，以便重复使用
              Queenes[line]=0;
           }
     }
}

int main() {
    
    //调用回溯函数，参数0表示从棋盘的第一行开始判断
    eight_queen(0);
    printf("摆放的方式有%d种",Counts);
    return 0;
}

实现原理流程

1. 初始化: 使用一个长度为8的数组Queenes[]来表示棋盘上皇后的位置，数组的下标代表行号，值代表列号。变量Counts用于记录找到的正确摆放方式数量。
2. 检查函数（Check）: 对于给定的行line和列list，判断当前位置是否可以放置皇后。通过遍历之前所有行的皇后位置，比较是否存在在同一列、同一斜线的情况，若存在则返回0（不可放），否则返回1（可放）。
3. 递归函数（eight_queen）: 逐行尝试每一列的位置，对于当前行的每一列，使用Check函数检查是否可以放置皇后，如果可以，则记录位置并递归地尝试放置下一行的皇后。如果到达最后一行且成功放置，增加解的计数并打印当前棋盘布局。无论成功与否，离开当前位置时需重置该位置，以便其它尝试使用。
4. 输出函数（print）: 打印当前棋盘的一个解。使用‘#’表示皇后位置，‘0’代表空位。

代码执行例子

为了更具体地解释代码执行过程，我们将逐步走过前几个步骤的详细例子。注意，因为八皇后问题有92种解法，这里只展示找到第一个解的过程。假设我们开始时棋盘为空，目标是放置8个皇后到棋盘上，使得它们互不攻击。

初始状态

plaintextCopy棋盘为空，Counts=0。
Queenes 数组初始化为 [0,0,0,0,0,0,0,0]。

第一步：放置第一个皇后

我们从第一行（line=0）开始，尝试在第一列（list=0）放置皇后。

plaintextCopy检查位置 (0,0) 是否合法：通过 Check 函数检查，无冲突，故可以放置皇后。

更新 Queens 数组为 [0,...]；实际上皇后已经放在第一行第一列，但由于数组下标和值都是从0开始计数，看起来像没有变化。
接着进入递归处理第二行。

第二步：放置第二个皇后

现在，我们尝试在第二行放置皇后。根据算法，我们从第一列开始尝试每个位置直到找到一个合适的。

plaintextCopy第一次尝试位置 (1,0)：失败，因为与第一行的皇后在同一列。
第二次尝试位置 (1,1)：失败，因为与第一行的皇后在对角线上。
尝试位置 (1,2)：成功，无冲突。

更新 Queens 数组为 [0,2,...]。
接着递归处理第三行。

第三步：放置第三个皇后

接下来，尝试在第三行放置皇后。

plaintextCopy尝试位置 (2,0)：失败，因为与第一行的皇后在同一列。
尝试位置 (2,1)：失败，因为与第二行的皇后在对角线上。
尝试位置 (2,2)：失败，因为与第一行的皇后在对角线上。
尝试位置 (2,3)：成功，无冲突。

更新 Queens 数组为 [0,2,3,...]。
接着递归处理第四行。

继续放置剩余皇后

按照上述过程继续尝试放置剩余的皇后。

这个过程中，我们会遇到需要回溯的情况，即当前行所有列都尝试过后仍然找不到合适的位置放置皇后。这时，算法会回到上一行，改变上一个皇后的位置，然后再次尝试。

找到第一个解

最终，当递归函数成功放置了第八个皇后，并且没有冲突时，我们找到了第一个解，并且Counts增加1，然后打印当前棋盘布局。

例如，其中一个可能的正确放置方式（不一定是第一种找到的）是Queenes数组为 [0, 4, 7, 5, 2, 6, 1, 3]，表示：

• 第1行的皇后在第1列
• 第2行的皇后在第5列
• …
• 第8行的皇后在第4列

注意

本例所述的步骤和对应的Queenes数组值可能并不代表真实运行程序时的首次找到的解或者实际的执行顺序，因为全过程涉及大量尝试和回溯操作。

进一步解释

让我们以更细节化的方式通过一个具体数值的示例来演示如何逐步执行代码，特别关注Check函数的执行。为了清晰起见，我们将从尝试放置第一个皇后开始，并展示前几步的详细过程。

初始状态：

• Queenes数组初始化为 [0, 0, 0, 0, 0, 0, 0, 0]，表示棋盘上还没有皇后被放置。
• Counts初始化为0，表示还没有找到任何合法的摆放方式。

第一步：放置第一个皇后

1. 尝试将第一个皇后放在第一行第一列（即line = 0, list = 0）。
   • 执行Check(0, 0)：由于这是第一个皇后，之前没有皇后被放置，所以无需检查冲突，直接返回1（表示可以放置）。
2. 更新Queenes数组为 [0, ...,]，实际上位置没变因为是从0开始计数的。

第二步：放置第二个皇后

1. 尝试将第二个皇后放在第二行第一列（即line = 1, list = 0）。

   • 执行

     Check(1, 0)
     

     • 需要检查与第一行的皇后是否冲突。
     • 列冲突：因为Queenes[0] == 0且list == 0，说明在同一列，返回0（不可放置）。

2. 尝试第二行第二列（line = 1, list = 1）。

   • 执行

     Check(1, 1)
     

     • 检查list == Queenes[0]（列冲突），不成立。
     • 检查(index + Queenes[index]) == (line + list)（主对角线冲突），即0 + 0 == 1 + 1，条件不成立，不冲突，不成立。
     • 检查(index - Queenes[index]) == (line - list)（主对角线冲突），即0 - 0 == 1 - 1，条件成立，说明冲突，返回0。

3. 继续尝试，直至找到Check(1, 2)返回1，意味着第二行第三列可以放置皇后。

   • 更新Queenes数组为 [0, 2, ...,]。

变量解释和设计理由：

• int Queenes[8]: 用来存储每一行皇后的列位置。其设计使得我们能够快速访问和更新每一行皇后的放置位置，同时保证每行只有一个皇后。
• int Check(int line, int list): 核心验证函数，它接受正在尝试放置的皇后的行号line和列号list，并遍历所有已放置的皇后进行冲突检查。
  • int index: 循环变量，用于遍历之前所有行中皇后的位置。
  • int data=Queenes[index]: 获取在已处理的index行中皇后的列位置。用于与当前尝试位置进行比较，判断是否冲突。
  • 纵向、对角线冲突检查：通过列号直接比较及与行号结合的方式（如line + list和line - list），判断是否在同一列或对角线上。设计这种方式是因为在棋盘上，两点在同一对角线上当且仅当它们行列号的差或和相等。

设计理由：

此设计利用了数组索引和值的映射关系简化了皇后位置的存储和冲突检查逻辑，使问题的空间复杂度降低。回溯算法通过逐行尝试每一列的策略，并在发现当前尝试路径不可能导致解时立即回溯，这样可以有效地遍历所有可能的摆放方式，而不必搜索整个解空间，提高了算法的效率。

最后再看看加入第一行中非第一列选择的情况

回溯过程举例

假设在棋盘的第一行，我们不是选择第一列放置皇后，而是选择了第二列（即Queenes[0] = 1）。此时Queenes数组更新为[1, 0, 0, 0, 0, 0, 0, 0]。

尝试放置第二个皇后

1. 尝试在第二行第一列放置皇后 （即line = 1, list = 0）。

   • 执行

     Check(1, 0)
     

     ：

     • 列冲突检查：list != Queenes[0]，无列冲突。
     • 主对角线冲突检查：(0 + 1) != (1 + 0)，无主对角线冲突。
     • 副对角线冲突检查：(0 - 1) != (1 - 0)，无副对角线冲突。

   • 所有检查通过，可以在该位置放置皇后。

2. 更新Queenes数组为[1, 0, ...,]。

如果发现冲突，如何回溯

假设在接下来的尝试中，我们发现某一行无论放在哪个位置都会与之前的皇后产生冲突，例如：

1. 接下来几步尝试后，假设Queenes数组变成了[1, 0, X, X, X, ...,]（X表示已经尝试过并放置了皇后但未详细展示）。
2. 在尝试放置第六个皇后时，我们发现无论放在哪里都会冲突，即对任何list值，Check(5, list)都返回0。

此时，算法需要回溯：

• 首先，我们需要撤销第五个皇后的放置，即将其所在行的Queenes数组值重置为0。
• 然后，回到第四个皇后的放置，尝试将其放在不同的列，也就是改变Queenes[3]的值并重新进入尝试放置第五个皇后的流程。
• 如果更改第四个皇后的位置仍旧找不到合法摆放方法，我们继续回溯到第三个皇后，以此类推。

Check函数判断的不同

Check函数负责核实在尝试的行line和列list上放置皇后是否会与之前放置的任何一个皇后冲突。它通过检查以下情况来确保放置的安全：

• 列冲突：确保没有其他皇后在同一列上。
• 主对角线冲突：确保没有其他皇后在当前尝试放置的皇后的左上角到右下角这条线上。
• 副对角线冲突：确保没有其他皇后在当前尝试放置的皇后的右上角到左下角这条线上。

无论是在第一行中选择了第一列还是非第一列，Check函数的这些判断标准保持不变。关键在于理解皇后的位置是如何通过行列索引的相对位置来确定冲突的：通过列的绝对位置判断列冲突，通过行列索引的和或差判断对角线冲突。

为什么算法中的(index+data)(line+list）和(index-data)(line-list)分别代表了斜上方和斜下方？

这个设计利用了棋盘格的几何特性来检测对角线冲突。在一个棋盘上，任意两个处于同一对角线上的点（无论是主对角线还是副对角线）都遵循特定的数学关系。我们通过行（index或line）和列（data或list）的加法和减法来描述这种关系。

主对角线（从左上到右下）

当两个皇后在同一主对角线上时，它们满足的条件是行与列的差或和相等。为什么是这样的？

• 观察规律：在主对角线方向上，如果你从一个格子移动到右下方的相邻格子，行号和列号都会各自增加1。这意味着，无论你沿着主对角线移动多远，行号和列号的差（index - data 或 line - list）保持不变。
• 应用规律：因此，如果两个皇后(index, data)和(line, list)的行号和列号的差相等，即index - data == line - list，则它们位于同一主对角线上。不过这里有个小失误，在原问题中，检测主对角线的条件应该是行号和列号的和相等，即(index + data) == (line + list)。

副对角线（从右上到左下）

副对角线的情况稍有不同，但也遵循一个简单的数学规律：

• 观察规律：在副对角线方向上，如果你从一个格子移动到左下方的相邻格子，行号会增加1，但列号会减少1（或行号减少1，列号增加1，取决于你的移动方向）。这意味着，无论你沿着副对角线移动多远，行号和列号的和保持不变。
• 应用规律：因此，如果两个皇后(index, data)和(line, list)的行号和列号的和相等，即index + data == line + list，则它们位于同一副对角线上。而正确的检测副对角线冲突的条件实际上是行号和列号的差相等，即(index - data) == (line - list)。

总结来说：

• 位于同一主对角线的条件是其位置的行号和列号之和相等。（(index + data) == (line + list)）
• 位于同一副对角线的条件是其位置的行号和列号之差相等。（(index - data) == (line - list)）

这些几何特性使得我们能够有效地使用简单的算术运算来检测两个皇后是否处于对角线上的冲突位置。

如果觉得文章对您有帮助，请帮忙点赞或者收藏，如果在文章中发现什么错误或不准确的地方，欢迎与我交流。