题目描述
N皇后问题
深度搜索
(暴力枚举) $O(n^2)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 10
int n,ans[N];
//ans[i]=j,表示第i行的皇后摆放在第j列上
int check(int x,int y);
//判断当前摆放位置是否与之前的摆放结果冲突
void dfs(int row);
//深度优先搜索
void print(int count);
//输出成功摆放结果
int main()
{
scanf("%d",&n);
dfs(1); // 从第一行开始深度优先搜索
return 0;
}
int check(int x,int y)//条件判断函数,根据所寻找的规律进行判断
{
int flag=1,i,res;
for(i=1; i<x&&flag; i++)
{
res=ans[i];
if(res==y||abs(x-i)==abs(y-res))
//abs(x-i)==abs(y-res)如果两个位置是斜对齐的,那么两个位置的差值等于行数差
//判断是否冲突
{
flag=0;
}
}
return flag;
}
void print()
{
int i,j;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(ans[i]==j)
printf("Q");
else
printf(".");
}
// printf(" j=%d",ans[i]);
printf("\n");
}
printf("\n");
}
void dfs(int row)
{
if(row==n+1) //如若成功遍历
{
print();
return;
}
int col;
for(col=1; col<=n; col++)//col即做标志又做占位
{
if(check(row,col))
{
ans[row]=col; //将当前列存入数组
dfs(row+1); //继续遍历下一行
}
}
return;
//回溯算法,试探性进行
//在递归之中凡是需要返回上一步操作直接return;
}