DFS-C

C - N皇后问题

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

Input共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。Output共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。Sample Input

1
8
5
0

Sample Output

1
92
10

#include<bits/stdc++.h>
using namespace std;

int n, sum;
int a[10];//存放每一行皇后的横坐标 
int b[10];//打表 

int check(int x){
    for(int i=0; i<x; i++)
        if(a[i]==a[x] || abs(a[x]-a[i])==abs(x-i))    return 0;
    return 1;
}

void DFS(int x){
    for(int i=0; i<n; i++){
        a[x] = i;
        if(check(x)){
            if(x == n-1)    sum++;
            else            DFS(x+1);
        }
    }
}

int main(){
    while(~scanf("%d", &n) && n){
        if(b[n])    printf("%d
",b[n]);
        else{
            sum = 0;
            DFS(0);
            b[n] = sum;
            printf("%d
",sum);
        }
        
    }
}