C++数据结构--回溯算法--八皇后问题

太过爱你忘了你带给我的痛 2021-11-01 11:10 416阅读 0赞

**1.回溯算法：**

**回溯算法也叫试探法，它是一种系统地搜索问题的解的方法**

**Example：八皇后问题**

**在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、  
同一列或同一斜线上，问有多少种摆法。  
![20130812101358640][]  
  
  
  
  
对于方格（ROWi,COLj)内的皇后，可对其攻击的皇后位置坐标（row,col)满足  
上对角线：  
col+row=COLj+ROWi;  
下对角线：  
col-row=COLj-ROWi;  
行：  
（ROWi,col)  
列：  
（row,COLj)  
  
  
用8个元素的整数向量qeensList存储row,向量的索引值对应着col,例如  
qeensList\[col\]=row,就表明一个皇后占据着方格（row,col)=(queensList\[col\],col);**

**\*回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试**

**\*第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了**

**实现代码：  
  
  
\#include<iostream>  
\#include<vector>  
using namespace std;**

**/\*row，col为皇后将要被放入的位置的坐标**

**\*queensList为存储所有皇后的向量数组  
\*/   
bool safeLocation(int row,int col,vector<int> &queensList)  
\{  
int qRow,qCol;  
for(qCol=0;qCol<col;qCol++) //从第0列遍历到col-1列  
\{   
qRow=queensList\[qCol\];//queensList\[qCol\]记录着列下标为qCol的皇后的横坐标   
if(row==qRow)  //同行   
 return false;  
if(row+col==qRow+qCol||row-col==qRow-qCol) //同对角线   
 return false;  
\}  
  
return true;  
\}  
  
  
//打印皇后信息   
void printQueens(vector<int> queensList)  
\{  
static int cnt=0;  
if((cnt++)%8==0)  
 cout<<endl;  
for(int x:queensList)  
 cout<<(x+1);  
cout<<ends;  
\}  
  
  
//求8皇后问题的所有解   
void allSolution(vector<int> queensList,int col)  
\{  
  
  
if(col==8) //找到了一种可能的排列，输出皇后列表信息   
printQueens(queensList);  
 else  
\{   
 int row=0; //从第0行开始   
 while(row<8)  
\{   
 if(safeLocation(row,col,queensList)) //找到安全位置   
 \{   
queensList\[col\]=row; //记录坐标  
 allSolution(queensList,col+1);//当递归开始返回时，说明找到了一种可能   
 row++; //从下一行开始继续查找另一种可能的排列   
 \}  
 else //找不到安全位置   
 row++;//从下一行开始查找安全位置   
\}  
\}  
  
\}  
  
  
  
  
  
  
测试代码  
  
  
int main()  
\{  
vector<int > vec(8,0);  
allSolution(vec,0);  
return 0;  
\}**

**运行结果：**

**![SouthEast][]**

[20130812101358640]: /images/20211101/c2a18a0279b44900be5a67f03d948f91.png
[SouthEast]: /images/20211101/18acf82f021440429f83801c5b5714cd.png