在国际象棋中，皇后是最厉害的棋子，可以横走、直走，还可以斜走。棋手马克斯·贝瑟尔 1848 年提出著名的八皇后问题：即在 8 × 8 的棋盘上摆放八个皇后，使其不能互相攻击 —— 即任意两个皇后都不能处于同一行、同一列或同一条斜线上。例如：
现在我们把棋盘扩展到n×n的棋盘上摆放n个皇后，请问该怎么摆？
请编写程序，输入正整数n，输出全部摆法（棋盘格子空白处显示句点“.”，皇后处显示字母“Q”，每两个字符之间空一格）。
输入格式
正整数n(n>0)
输出格式
若问题有解，则输出全部摆法（每两种摆法之间空一行）。
若问题无解，则输出 None。
要求：试探的顺序按从上到下逐行进行，其中每一行按从左到右的逐格进行，请参看输出样例2。
输入样例1
3
输出样例1
None
输入样例2
4
输出样例2
. Q . .
. . . Q
Q . . .
. . Q .
. . Q .
Q . . .
. . . Q
. Q . .
回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。
本算法由行数作为回溯的返回条件，再依次经过遍历每一列来确定皇后应该摆放的位置。即，每一行只能放置一名皇后，因此若该行已经放置，直接判断下一行。
#include<iostream>using namespace std;int n,num = 0; //num记录可行解个数int **t = (int**)malloc(n*sizeof(int*)); //动态分配二维数组void outPrint(){ //打印结果if(num>1) cout<<endl; for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(t[i][j]==1) cout<<"Q";else cout<<".";if(j<n-1) cout<<" ";} cout<<endl;}}bool constraint(int row,int column){ //约束条件int i,j;for(i=0;i<row;i++) //判断同一列是否已经放置皇后if(t[i][column]==1)return false;for(j=0;j<column;j++) //判断同一行是否已经放置皇后if(t[row][j]==1)return false;for(i=row-1,j=column-1;i>=0&&j>=0;i--,j--) //判断左上角是否已经放置皇后if(t[i][j]==1)return false;for(i=row-1,j=column+1;i>=0&&j<n;i--,j++) //判断右上角是否已经放置皇后if(t[i][j]==1)return false;return true;}void backtrack(int row){if(row==n){ //回溯的返回条件，即到达最后一行后，得到可行解num++;outPrint();return ;}for(int column=0;column<n;column++){ //依次遍历列，判断应放在第几列if(constraint(row,column)){t[row][column] = 1; //满足约束条件，可以放置backtrack(row+1); //继续下一行t[row][column] = 0; //重置该位置，避免污染数据}}}int main(){cin>>n;for(int i=0;i<n;i++)t[i] = (int*)malloc(n*sizeof(int));for(int i=0;i<n;i++) //初始化数组，均赋值为0for(int j=0;j<n;j++)t[i][j] = 0;backtrack(0); //从第一行开始if(num==0) cout<<"None"<<endl;return 0;}
如果觉得《算法分析与设计——八皇后问题（回溯法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
