N皇后問題(DFS)


N皇后問題
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3579    Accepted Submission(s): 1654
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

 
Author
cgf
 
Source
2008 HZNU Programming Contest
 
Recommend
lcy
DFS+メーター
検索コード:
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXI 2147483647
#define MAXL 9223372036854775807
#define dg(i) cout << "*" << i << endl;
using namespace std;

int n, q[11]; //      , i        q[i]

bool check(int r)
{
    int i;
    for(i = 1; i < r; i++)
        if(q[i] == q[r])
            return false;
    for(i = r - 1; i > 0; i--)
        if(q[i] == q[r] - (r - i) || q[i] == q[r] + r - i)
            return false;
    return true;
}

//r       
int DFS(int r)
{
    if(r == n + 1) return 1;
    int cnt = 0;
    for(q[r] = 1; q[r] <= n; q[r]++)
    {
        if(check(r))
        {
            cnt += DFS(r + 1);
        }
    }
    return cnt;
}

int main()
{
    int ans;
    while(scanf("%d", &n) && n)
    {
        memset(q, 0, sizeof(q));
        ans = 0;
        for(q[1] = 1; q[1] <= n; q[1]++)
        {
            ans += DFS(2);
        }
        printf("%d
", ans); } return 0; }

そして配列で保存して...わかりました