蓝桥杯（N皇后问题）------回溯法

题目描述

在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。

输入描述

输入中有一个正整数 N≤10，表示棋盘和皇后的数量

输出描述

为一个正整数，表示对应输入行的皇后的不同放置数量。

输入输出样例

示例 1

输入

5

输出

10

 代码如下：

#include <bits/stdc++.h>
using namespace std;
int n;//n个皇后
int result[15];//result[i]记录第i个皇后存放的列
int cnt=0;//记录不同放置数量
bool isOk(int k,int j) 
{for(int i=1;i<=k;i++){//如果前面有皇后与该位置冲突（同一列或同一对角线上）if(result[i]==j||abs(i-k)==abs(result[i]-j))return false; }return true;
}void dfs(int k)
{if(k>n){cnt++;return ;} for(int j=1;j<=n;j++)//第k个皇后存放的列 {if(isOk(k,j))//判断（k,j）该位置是否ok{result[k]=j;k++;//递归搜索下一个的皇后的列 dfs(k);k--;//回溯result[k]=0;//这里一定要归零 } }
} 
int main() 
{cin>>n;dfs(1);//从第一行的皇后开始cout<<cnt<<endl; return 0;
}

 希望能帮助到各位同志，谢谢！