【算法学习】—n皇后问题(回溯法)

【算法学习】—n皇后问题(回溯法)

1. 什么是回溯法？

相信"迷宫"是许多人儿时的回忆，大家小时候一定都玩过迷宫游戏。我们从不用别人教，都知道走迷宫的策略是：

当遇到一个岔路口，会有以下两种情况：

存在没走过的路。此时可以任意选一条没走过的路深入，只要记住我们所走过的路径即可。

倘若下次再来到这个路口，便不再沿着走过的路径继续深入，而是沿着没走过的路径深入下去；

所有路都已经走过。如果所有岔路口都已经遍历，则回退至上一个最近的岔路口。

当遇到死胡同，便回退到刚才距离最近的岔路口。

不断前进并重复该过程，直到找到终点或回退到起点位置。

其实，这就是回溯法：一个基于深度优先搜索和约束函数的问题求解方法。

（1）、n皇后问题

📢 非递归求解n皇后问题

#include <math.h>
#include <stdio.h>
#include <stdlib.h>#define N 4int q[N + 1]; // 存储皇后的列号int check(int j)
{ // 检查第i个皇后的位置是否合法int i;for (i = 1; i < j; i++){if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])){ // 判断是否在同一斜线上return 0;}}return 1;
}void queen()
{ //int i;for (i = 1; i <= N; i++){q[i] = 0;}int answer = 0; // 方案数int j = 1;      // 表示正在摆放第j个皇后while (j >= 1){q[j] = q[j] + 1; // 让第j个皇后向后一列摆放while (q[j] <= N && !check(j)){                    // 判断第j个皇后的位置是否合法q[j] = q[j] + 1; // 不合法就往后一个位置摆放}if (q[j] <= N){ // 表示第j个皇后的找到一个合法的位置if (j == N){ // 找到了一组皇后的解answer = answer + 1;printf("放案%d:", answer);for (i = 1; i <= N; i++){printf("%d", q[i]);}printf("\n");}else{ // 继续摆放下一个皇后j = j + 1;}}else{ // 表示第j个皇后找不到一个合法的位置q[j] = 0;  // 还原第j个皇后的位置j = j - 1; // 回溯}}
}
int main()
{queen();return 0;
}

📢 递归求解n皇后问题

#include <math.h>
#include <stdio.h>
#include <stdlib.h>#define N 4int answer=0;int q[N + 1]; // 存储皇后的列号int check(int j)
{ // 检查第i个皇后的位置是否合法int i;for (i = 1; i < j; i++){if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])){ // 判断是否在同一斜线上return 0;}}return 1;
}void queen(int j){int i;for(i=1;i<=N;i++){q[j]=i;
if(check(j)){// 当摆放的皇后位置为合法时if(j==N){//找到了N皇后的一组解answer=answer+1;printf("方案%d:",answer);for(i=1;i<=N;i++){printf("%d",q[i]);}printf("\n");}else{queen(j+1);//递归摆放下一个位置}
}}
}int main()
{queen(1);return 0;
}