八皇后问题(回溯)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN = 10;
int pre[MAXN];
int Queen_Num = 8;
int num = 0;

void Output(int pre[]){
	for(int i = 0; i < Queen_Num; i++){
		printf("(%d, %d)\t",pre[i] + 1, i + 1);        // 输出坐标
	}
	printf("\n");
	num++;            // 方案数++
}

bool check(int pre[], int col){
      for(int i = 0; i < col; i++){           // 因为时从第一列开始放，所以只需判断之前的列的行是否重复
	  if(pre[i] == pre[col] || abs(pre[i] - pre[col]) == col - i){  // 当在同一对角线上时，无论主副都有|pre[i]-pre[col]|==|i-col|
		return false;
	 }
     }
     return true;
}

void dfs(int pre[], int col){
	if(col == Queen_Num){            // 当列数达到8时调用输出函数
		Output(pre);
		return ;
	}
	for(int i = 0; i < Queen_Num; i++){    // col为列，遍历行
		pre[col] = i;                  // 将第i行col列存入数组
		if(check(pre,col)){            // 判断这样放是否可行
			dfs(pre,col+1);              // 进行下一列
		}
	}
}

int main()
{
	memset(pre,0,sizeof(pre));
	dfs(pre,0);                    // 从第0列开始
	printf("总方案数：%d\n",num);
	return 0;
}