【杭电】[2553]N皇后问题

问题描述

N皇后问题

[hdu-2553] [3203295595393191] @vjudge

问题分析

N皇后问题是道经典回溯问题
这里参考《算法竞赛入门经典》 dfs中记录已经下了多少个棋子
如果达到N个则说明有一种方案完成
所以这一如此进行递归判断

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
int res[15];
int flag[15];
int cnt;
int abs(int m) {
    return m>0?m:-m;
}
void f(int m,int N) {
    if(m==N)
        cnt++;
    else {
        for(int i=0; i<N; i++) {
            flag[m]=i;
            int j;
            for(j=0; j<m; j++)
                if(flag[m]==flag[j]||abs(flag[m]-flag[j])==abs(m-j))
                    break;
            if(j==m)
                f(m+1,N);
        }
    }
}
void get() {
    for(int i=1; i<=10; i++) {
        cnt=0;
        f(0,i);
        res[i]=cnt;
    }
    return ;
}
int main() {
    get();
    int n;
    while(scanf("%d",&n),n)
        printf("%d\n",res[n]);
    return 0;
}