GitBook

N皇后问题

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

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

Input

共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。

Output

共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。

Sample Input

1
8
5
0

Sample Output

1
92
10

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

题目地址:【杭电】[2553]N皇后问题

查看原文:<a href=http://www.boiltask.com/blog/?p=1911>http://www.boiltask.com/blog/?p=1911</a>