回溯法之N皇后問題
1. 問題描述
? 在n*n格的棋盤上放置彼此不受攻擊的n個皇后，按照國際象棋的規則，皇后可以攻擊與之在同一行或同一列或同一斜線上的旗子，n后問題等價于在n*n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上，
2. 問題分析（以n=4皇后問題為例）
? 有倆種解法，第一種采用解空間為N(4)叉樹的解法、第二種是采用解空間為排列數的解法，
2.1. N(4)叉樹的解法
? 每個皇后在一行上有四個可選位置，即每個非葉結點有4個子節點，4叉樹如下：
? 
? 解向量：(x1,x2,x3,......,xn)
? 顯約束：任意倆皇后不同行，
? 隱約束：(1) 不同列：xi ≠ xj (2) 不處于同一正反對角線：|i - j| ≠ |xi - xj|
? 核心代碼：
// 剪枝函式，排除同列和同一對角線的分支
int place1(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k])
return 0;
return 1;
}
// t > n代表當前解已經求出，將總數+1
// 利用回圈遍歷節點的n叉，同時判斷分叉是否符合條件
// 符合條件的分叉繼續遍歷下去
void BackTrack1(int t) {
if (t > n)
sum++;
else
for (int i = 1; i <= n; i++) {
x[t] = i;
if (place1(t))
BackTrack1(t + 1);
}
}
2.2 排列數的解法
? 
? 解向量：(x1,x2,x3,......,xn)
? 顯約束：任意倆皇后不同行、不同列，x1,x2,x3,......,xn是1,2,3.......n排列
? 隱約束：不處于同一正反對角線：|i - j| ≠ |xi - xj|
? 核心代碼：
// 交換倆行皇后的位置
// 實作切換排列數的分支作用
void swap(int i, int j) {
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
// 剪枝函式，排除在同一對角線上的情況
int place2(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]))
return 0;
return 1;
}
// t > n時表示當前排列符合條件，總數 + 1
// 利用for回圈，和swap函式，將節點對應的所有排列遍歷一次
// 同時采用剪枝函式，減去錯誤的分支
// 對正確的分支繼續求解下去
// 最后遞回求解結束后，再次呼叫swap函式將狀態回傳到原本的節點狀態
void BackTrack2(int t) {
if (t > n) sum++;
else
for (int i = t; i <= n; i++) {
swap(t, i);
if (place2(t))
BackTrack2(t + 1);
swap(t ,i);
}
}
3. 完整代碼
/**
* 回溯法求解n皇后問題
* 使用x解向量，x1,x2,x3分別表示在1,2,3行上皇后的列號
**/
#include <stdio.h>
#include <stdlib.h>
#define MAX 4
/**
* n 皇后個數
* x 當前解
* sum
**/
int n = MAX;
int x[MAX + 1];
long sum = 0;
// 剪枝函式，排除同列和同一對角線的分支
int place1(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k])
return 0;
return 1;
}
// t > n代表當前解已經求出，將總數+1
// 利用回圈遍歷節點的n叉，同時判斷分叉是否符合條件
// 符合條件的分叉繼續遍歷下去
void BackTrack1(int t) {
if (t > n)
sum++;
else
for (int i = 1; i <= n; i++) {
x[t] = i;
if (place1(t))
BackTrack1(t + 1);
}
}
// 交換倆行皇后的位置
// 實作切換排列數的分支作用
void swap(int i, int j) {
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
// 剪枝函式，排除在同一對角線上的情況
int place2(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]))
return 0;
return 1;
}
// t > n時表示當前排列符合條件，總數 + 1
// 利用for回圈，和swap函式，將節點對應的所有排列遍歷一次
// 同時采用剪枝函式，減去錯誤的分支
// 對正確的分支繼續求解下去
// 最后遞回求解結束后，再次呼叫swap函式將狀態回傳到原本的節點狀態
void BackTrack2(int t) {
if (t > n) sum++;
else
for (int i = t; i <= n; i++) {
swap(t, i);
if (place2(t))
BackTrack2(t + 1);
swap(t ,i);
}
}
void main() {
for (int i = 0; i <= n; i++)
x[i] = i;
BackTrack1(1);
printf("%d\n", sum);
for (int i = 0; i <= n; i++)
x[i] = i;
sum = 0;
BackTrack2(1);
printf("%d\n", sum);
system("pause");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233439.html
標籤：其他
上一篇：事務與隔離級別
下一篇：Python排序函式用法