問題描述
什么是皇后問題
八皇后問題（英文：Eight queens），是由國際西洋棋棋手馬克斯·貝瑟爾于1848年提出的問題，是回溯演算法的典型案例，
問題表述為：在8×8格的國際象棋上擺放8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法，高斯認為有76種方案，1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，后來有人用圖論的方法解出92種結果，如果經過±90度、±180度旋轉，和對角線對稱變換的擺法看成一類，共有42類，計算機發明后，有多種計算機語言可以編程解決此問題，
一起看看經典教材 計算機演算法設計與分析 對該問題的描述：
- 在 n × n 棋盤上放彼此不受攻擊的n個皇后，
- 按照國際象棋規則，皇后可以攻擊 同行、同列、同一斜線 的棋子，
- 等價于在 n × n 格的棋盤上放置 n 個皇后，任何 2 個皇后不放在 同一行 或 同一列 或 同一斜線 上，
解題思路
由于皇后的位置受到上述三條規則約束，我們必須通過一些技術手段來判斷當前皇后的位置是否合法，
1.皇后的編號從 0 ~ N - 1 （N表示皇后的數量），這樣編號的想法很簡單：陣列下標從0開始（這樣方便后續對其位置的說明），
2.使用一維陣列 putInf 對每一行皇后的存放位置進行保存，因此得到解向量 (putInf[0], putInf[1], putInf[3], … , putInf[N - 1])，putInf[i] 表示第 i 個皇后被放置到了第 putInf[i] + 1 列上（putInf陣列中存盤的是列號，范圍為 0 ~ N - 1）;
3.第二個條件：各皇后不同列， N 皇后放在 N x N 的棋盤上，那么每一列最多且必須放置一個皇后，這里我用了一個 used陣列 對每一列的擺放情況進行記錄， used[i] = true 表示 第 i 列 已經放置了皇后，used[i] = false 表示第i列暫未放置皇后，這樣我們可以保證不在一列上放置多個皇后，也就能滿足 各皇后不同列 的規則，
4.各皇后不能處于同一對角線位置：假設兩皇后位置坐標分別為(i, j) 、（l, k），那么根據直線斜率公式：
- (i - l) / (j - k) = 1 求解得 i - l == j - k ①
- (i - l) / (j - k) = -1 求解得 i - l == k - j ②
這兩種情況出現時表明處于同一對角線，那么要滿足擺放規則就必須滿足
| i - l | != | j - k | （“| |” 表示絕對值）
解空間樹
實作代碼
#include <iostream>
#include <vector>
using namespace std;
#define N 4 //N皇后
vector<int> putInf;//每一行皇后的置放位置情況
//不同行 不同列 不同斜線 |ri - rj| != |ci - cj| 第1行與
vector<int> used(N, 0);//每一列只能有一個皇后，記錄每一列的狀態
vector<vector<int>> ans;//存盤可行方案
int curRow = 0;//當前待放皇后的行數
/* 正置放皇后行↓ 置放列↓ */
bool judgeLegalPut(int& curRow, int col) {//判斷在curRow行的col列放置皇后是否合法
for (int i = curRow - 1; i >= 0; i--) {
//我們的解空間樹已經去除一行一列置放相同元素
//（每一個皇后被放在不同行以及不同列）的情況
//因此我們只需要判斷皇后是否成斜線即可
if (curRow - i == abs(col - putInf[i])) {
//當前位置與之前的皇后處于同一斜線上
return false;
}
}
return true;
}
void queensAssign(int curRow) {
if (curRow >= N) {//遞回到葉子節點，遞回結束，收集結果
ans.push_back(putInf);
return;
}
//i : 當前行皇后準備放的列數
for (int i = 0; i < N; ++i) {//curRow行i列的位置
if (used[i]) continue;//位置被使用過，直接跳過
//這樣滿足了不處于同一列的顯條件 類似于全排列
if (judgeLegalPut(curRow, i)) {
//當前位置置放與之前不沖突 將皇后加入
used[i] = true;
putInf.push_back(i);
queensAssign(curRow + 1);
used[i] = false;//撤銷之前的狀態
putInf.pop_back();
}
}
}
void printChessBoard(vector<int>& vec) {//輸出模擬棋盤
cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j != vec[i])
cout << " × ";
else
cout << " √ ";
}cout << endl;
}cout << endl;
}
/// <author>
/// nepu_bin
/// <博客域名>
/// bincode.blog.csdn.net
int main() {
queensAssign(0);
int n = 1;
cout << N << "皇后問題,方案如下:\n" << endl;
for (vector<vector<int>>::iterator it = ans.begin(); it != ans.end(); it++) {
cout << "第" << n++ << "種放置方案, 皇后被放于 " << endl;
for (int i = 0; i < it->size(); i++) {
cout << (*it)[i] + 1 << " ";
}cout <<"列" << endl;
cout << endl << "棋盤布局如下↓" << endl;
printChessBoard(*it);
}
return 0;
}
運行效果
四皇后問題運行截圖：
通過修改宏定義 N 可以得到不同數量皇后問題的解答~~~
八皇后求解：
子集樹與排列樹
附上子集樹 and 排列樹的定義
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279931.html
標籤：AI
上一篇：Python中[-1]、[:-1]、[::-1]、[n::-1]、[:,:,0]、[…,0]、[…,::-1] 的理解