八皇后问题

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int q[10][10],dl[15],dr[15],l[10],s=0;

void dfs(int h){//h代表我现在调用dfs找第h行的皇后
	if(h>8){
		s++;
		cout<<"No. "<<s<<endl;
		for(int i=1;i<=8;i++){
			for(int j=1;j<=8;j++){
				cout<<q[j][i]<<" ";
			}
			cout<<endl;
		}
		return;
	}
	for(int i=1;i<=8;i++){
		if(l[i]==0&&dl[h-i+7]==0&&dr[h+i]==0){
			q[h][i]=1;// 在第h行第i列摆上一个皇后
			l[i]=1; // 把第i列设置为被占领状态
			dl[h-i+7]=1; // 把此皇后所在的左对角线设置为占领状态
			dr[h+i]=1; // 把此皇后所在的右对角线设置为占领状态
			dfs(h+1); // 调用自己去摆下一行的皇后
			q[h][i]=0; // 回溯，把这一列的摆上的皇后撤回
			l[i]=0; // 释放占领的列
			dl[h-i+7]=0; // 释放占领的左对角线
			dr[h+i]=0; // 释放占领的左对角线
		}
	}
}

int main(){
	dfs(1);
	return 0;
}

深搜

广搜