HUD--2553 N皇后问题

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问题，不过这题需要先打一个表吧，不然会TLE

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

const int N=;

int result[N];

int queuePos[N];

int n,ans;

void DFS(int k)

{

    if(k==n+)

    {

        ans++;

        return ;

    }

    for(int i=;i<=n;i++)

    {

        int j;

        for(j=;j<k;j++)

        {

            if(queuePos[j]==i||abs(queuePos[j]-i)==abs(k-j))

            break;

        }

        if(j==k)

        {

            queuePos[k]=i;

            DFS(k+);

        }

    }

}

int main()

{

    for(int i=;i<=;i++)

    {

        ans=;

        n=i;

        DFS();

        result[n]=ans;

    }

    while(cin>>n)

    {

        if(n==)    break;

        cout<<result[n]<<endl;

    }

    return ;

}

巴特西

HUD--2553 N皇后问题

最新文章

热门文章