Life has its own fate, and meeting may not be accidental.

0%

N皇后问题-经典DFS

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。

然而这是N皇后哈哈哈哈哈~

题目

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

输入

测试数据由多组测试样例组成。每组测试数据第一行输入一个正整数 n ( 1 <= n <= 10 )

输出

输出有多少种合法的放置方法

样例输入

1
1
2
5

样例输出

1
1
2
10

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int t,n,m,a,b,sum;
4
int Map[20];
5
void dfs(int x){
6
    if(x==n){
7
        sum++;
8
        return;
9
    }
10
    int i,j;
11
    for(i=0;i<n;i++){
12
        for(j=0;j<x;j++){
13
            if(Map[j]==i||abs(x-j)==abs(Map[j]-i)){
14
                break;  //两个点45度直线,两条边相等
15
            }
16
        }
17
        if(j==x){
18
            Map[x]=i;
19
            dfs(x+1);
20
        }
21
    }
22
}
23
int main(){
24
    while(scanf("%d",&n)!=EOF){
25
        memset(Map,0,sizeof(Map));
26
        sum=0;
27
        dfs(0);
28
        printf("%d\n",sum);
29
    }
30
    return 0;
31
}