python/C++专题课程/回溯算法/皇后问题（回溯法）/八皇后-递归法.cpp

#include<bits/stdc++.h>
using namespace std;
int const n=8;
//几种方案 
int nSolution=0;
int queenArr[n];

//打印棋盘和皇后
void showQueens(int queenArr[],int nlen,int nSolution) {
	//解法数量
	cout<<nSolution<<endl;

	for(int i = 0; i < nlen; ++i) {
		//打印皇后前面的格子
		for(int j = 0; j < queenArr[i]; ++j) {
			cout<<"1";//空格子
		}
		cout<<"Q";//皇后
		//打印皇后后面的格子
		for(int z = 0; z < nlen-queenArr[i]-1; ++z) {
			cout<<"1";
		}
		cout<<endl;
	}
	cout<<"                       "<<endl;
}


/*cur代表填数的当前行*/
void search(int cur) {
	//当cur等于行数，那么就代表摆放成功
	if(cur == n) {
		//输出 
		nSolution++;
		//打印棋谱 
		showQueens(queenArr ,8, nSolution);
		
	} else {
		for(int i=0; i<n; i++) {
			int ok = 1;
			//尝试把第cur行的皇后放入第i列
			queenArr[cur] = i;
			for(int j=0; j<cur; j++) {
				//判断是否同列同主对角线和同副对角线
				if(queenArr[cur]==queenArr[j]||cur-queenArr[cur]==j-queenArr[j]||cur+queenArr[cur]==j+queenArr[j]) {
					ok = 0;
					//如果是，则不递归并退循环，回溯
					break;
				}
			}
			if(ok) {
				search(cur+1);   //如果合法，则递归
			}
		}
	}
}
int main() {
	//数组下标是从零开始的,即0就是第一行 
	search(0);	
	return 0;
}