c++ 回溯算法-八皇后

//VC6.0-------------------das白 2019.12.28
#include"stdafx.h"
#include <cmath>
#include <iostream>
using namespace std;

//----------全局变量------------
#define n 8   //n皇后
int a[n]={0}; //棋盘  a[0]=5 则表示皇后在第一行 第六列
int sum=0;    //解的个数
//-----------------n皇后-----回溯算法--------------------
//检测皇后位置是否正确
bool Check_queen(int row,int col){
	//遍历前面所有皇后 判断是否与新皇后冲突
	for(int i=0;i<row;i++){
		//之前已经row+1(且是一维数组存储行列坐标) 无需判断是否同一行
		//判断其是否为同一列 或 是否斜率为1
		if( (a[i]==col) || (abs(row-i)==abs(col-a[i])) )
			return false;
	}
	//符合要求 
	return true;
}
//输出已求解的个数以及棋盘
void output(){
	sum+=1;
	cout<<"------ "<<sum<<" ------"<<endl;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i]==j) cout<<"* ";
			else cout<<"0 ";
		}
		cout<<endl;
	}
}
//确定row+1个皇后
void Queen(int row,int col){  
	//如果已铺满棋盘 则输出棋盘
	if(row>=n){
		output();
		return ;   
	}
	if(col>=n) return;   //超出棋盘范围 放弃此解

	//确定第row+1个皇后位置
	if(Check_queen(row,col)){
		a[row]=col;
		Queen(row+1,0); //
		for(int i=row;i<n;i++)
			a[i]=0;       //下面几行皇后位置清零 寻找下一个可能的答案
	}
	//皇后位置右移
	Queen(row,col+1);
}
//------------------------------------------------------
void main()
{
	Queen(0,0);
}

八皇后输出：                            四皇后输出：