1、环境配置：
- 系统：win10
- 编程语言：C++
- 编译器：DevC++
2、算法思想：
2.1、回溯的基本思想：
为了求得问题的解，先选择某一种可能的情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
比如迷宫问题，在进入迷宫后，先随意选择一个前进方向，一步步向前探索前进，如果碰到死胡同，说明无路可走，这时看其他方向是否有路，有路则继续探索，无路则返回一步，再看其他方向是否有路，有路则继续探索，无路则返回一步。按照如此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。
2.2、八皇后问题说明：
如下图所示，有一个8?8的棋盘，要放8个皇后棋子进去。国际象棋中的皇后有如下性质就像中国象棋里的车和象一样，所以在一个皇后占据所处的行和列还有斜线后，在对应行和列还有斜线是不允许有其他皇后出现的。规则如下图所示，在如此规则下要求在8?8的棋盘，要放8个皇后棋子进去，需要找出所有放置的可能性。
八皇后问题.png
八皇后问题规则.png
2.3、n皇后问题算法思路
-
注意下图中最后一个执行框中缺了一条语句，就是如果check（）是false，则将对应位置设置为flase。
n皇后问题.png
3、代码：
#include <iostream>
using namespace std;
const int n=8; //n皇后问题，这里要加const，否则后面在写二维数组时，会出错。
int num=0; //放置方式计数
//检查函数，检查carr[r][c]位置和之前放的位置有无冲突
bool check(bool carr[n][n],int r,int c){
if(r==0)//第0行放任何位置都行
{
return true;
}
//检查所在位置和前面所有行在同一列有没有冲突的情况
for(int i1=0;i1<r;i1++){
if(carr[i1][c]){
return false;
}
}
//检查所在位置和之前左对角线有没有冲突的情况
int lsr=r-1;
int lsc=c-1;
while((lsr>=0)&&(lsc>=0)){
if(carr[lsr][lsc]){
return false;
}
lsr--;
lsc--;
}
//检查所在位置和之前右对角线有没有冲突的情况
int rsr=r-1;
int rsc=c+1;
while((rsr>=0)&&(rsc<=(n-1))){
if(carr[rsr][rsc]){
return false;
}
rsr--;
rsc++;
}
return true;
}
//如果顺利找到最后一行，将carr[r][c]打印出来，
void carr_print(bool carr[n][n]){
for(int i2=0;i2<n;i2++){
for(int j2=0;j2<n;j2++){
if(carr[i2][j2]){
cout<<'X';
}
else cout<<'0';
}
cout<<endl;
}
cout<<"----------------------------"<<endl;
}
//递归回溯函数
void fb(bool carr[n][n],int fr){
for(int fc=0;fc<n;fc++)
{
carr[fr][fc]=true;
if(check(carr,fr,fc)){
if((fr+1)==n){
num+=1;
carr_print(carr);
}
else{
fb(carr,fr+1);
}
}
carr[fr][fc]=false;
}
}
int main()
{
//二维数组初始化
bool carr[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
carr[i][j]=false;
}
}
fb(carr,0);
cout<<"所有合适的位置总数为"<<num<<endl;
return 0;
}
4、结果展示：
结果.png
5、反思总结：
- 发现C++基础知识语法还是要加强，主要在一些类似const和system("pause");这种语句不太清晰。在函数中调用函数传参问题。
- 算法过程中二维数组始终是以“当前位置”和“之前位置”作比较，这是check（）函数的核心。
- 练过不代表记住，反复思考。
