【算法學(xué)習(xí)】—n皇后問題(回溯法)

1. 什么是回溯法？

相信"迷宮"是許多人兒時的回憶，大家小時候一定都玩過迷宮游戲。我們從不用別人教，都知道走迷宮的策略是：

當(dāng)遇到一個岔路口，會有以下兩種情況：

存在沒走過的路。此時可以任意選一條沒走過的路深入，只要記住我們所走過的路徑即可。

倘若下次再來到這個路口，便不再沿著走過的路徑繼續(xù)深入，而是沿著沒走過的路徑深入下去；

所有路都已經(jīng)走過。如果所有岔路口都已經(jīng)遍歷，則回退至上一個最近的岔路口。

當(dāng)遇到死胡同，便回退到剛才距離最近的岔路口。

不斷前進(jìn)并重復(fù)該過程，直到找到終點(diǎn)或回退到起點(diǎn)位置。

其實(shí)，這就是回溯法：一個基于深度優(yōu)先搜索和約束函數(shù)的問題求解方法。

（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; // 方案數(shù)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{ // 繼續(xù)擺放下一個皇后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)){// 當(dāng)擺放的皇后位置為合法時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;
}