N皇后问题
参考链接：https://www.cnblogs.com/henuliulei/p/10117304.html（讲解得很详细）
题目描述
请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个nxn的棋盘上放置n个棋子，使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。给定一个int n，请返回方法数，保证n小于等于15
基本思路
皇后问题一个重要的判断该点能否取的标准是不能在同一行列和对角。判断约束函数判断第k个后能不能放在x[k]处 两个皇后不能放在统一斜线上： 若2个皇后放置的位置分别是（i,j）和（k,l）, 且 i-j = k -l 或 i+j = k+l，则说明这2个皇后处于同一斜线上。
- 使用回溯法的思路
对皇后每一行不断进行尝试x[k]，判断在此之上的数据时候会发生冲突，如果没有，则k+1.判断下一行。如果发生了冲突，就x[k]++继续进行尝试。当x[k] = = N时，表示此行完全没解，需要回溯到上一行，也就是进行k-1操作，在之前的基础是哪个x[k]++继续进行尝试。
当k = = N时，表明已经实现了一个n皇后的解，将x[k]数据输出则为解。随后，再上一次解的基础上，x[k]再次加一操作，进行下一个解的操作。
当时由于此解的最后一行必然已经没有解，所以k必然会回溯到上一行，k-1，在此摸索x[k]+1的其他解法。如果没有解，则不断的回溯到上一行k，然后再x[k]的基础上再次进行尝试。
知道最后k = =0，返回到第0行，表示已经无解，全部解法已输出。
- 使用递归法的思路
使用递归的方法是，对没有一行的位置x[k] = i,依次进行尝试，如果没有冲突，则进行递归进行下一行k+1；，当k = n时说明已经完成一次放置。但是由于处于递归上的其他位置还没有完成，循环没有结束，所以会不断递归查看全部位置是否合适。（感觉有点像广度优先遍历）
代码如下
#include<bits/stdc++.h> using namespace std; int n; int x[100]; int sum=0; /* 判断第k个后能不能放在x[k]处 两个皇后不能放在统一斜线上： 若2个皇后放置的位置分别是（i,j）和（k,l）, 且 i-j = k -l 或 i+j = k+l，则说明这2个皇后处于同一斜线上。 */ void output(){ cout << "第" <<sum << "种放置方法为：" << endl; for(int i=1;i<=n;i++){ cout << "(" <<i << "," << x[i] << ")" << endl; } } int place(int k){ for(int j=1;j<k;j++){ if(x[j]==x[k] || abs(x[j]-x[k])== abs(j-k)) //对于此时的x[k]，在此之上的同一列和对角线存在冲突 return 0; //表示不能放 } return 1; //表示可以放 } void BackTrace(int t,int n){//递归 if(t>n){如果t>n说明已经完成一次放置 sum++; output(); } else{ for(int i=1;i<=n;i++){ x[t]=i; if(place(t)){// //可以放在i位置处，则继续搜索 BackTrace(t+1,n); } } } } void BackTrace1(int n){//非递归 int k; x[1]=0; k=1; while(k>=1){ x[k]+=1;先放在第一个位置 while((x[k]<=n && !(place(k)))){//如果不能放 x[k]++;// //放在下一个位置 } if(x[k]<=n){ if(k==n){// //如果已经放完了n个皇后 sum++; output(); } else{// //没有处理完，让k自加，处理下一个皇后 k++; x[k]=0; } }else{// 当前无法完成放置，则进行剪枝，回溯回去，回到第k-1步 k--; } } } int main() { memset(x,0,sizeof(x)); cin >> n; cout << n << "皇后的放置方法为" << endl; BackTrace(1,n); //BackTrace1(n); return 0; }
