程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3239 n皇後放置問題

POJ 3239 n皇後放置問題

編輯：C++入門知識

以前那個是8皇後問題，用的遞歸寫法，然後這個可以求n皇後放置問題，用的純粹數學方法……神奇！

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 2005
#define INF 100004
#define eps 1e-7
using namespace std;
typedef long long ll;
//輸出的是當前列的哪一行需要放置皇後
//比如:5 3 1 6 8 2 4 7
//即第一列的第五行放置皇後，第二列的第三行放置皇後
void solveQueen(int n) //n皇後問題
{
    
    int k,i,first=1; 
    if(n%6!=2&&n%6!=3)
    {
        for(i=2;i<=n;i+=2) printf("%d ",i);
        for(i=1;i<=n;i+=2) printf("%d ",i);
    }
    else
    {
        k=n/2;
        if(!(k&1))
        {
            for(i=k;i<=n;i+=2)     printf("%d ",i);
            for(i=2;i<=k-2;i+=2)   printf("%d ",i);
            for(i=k+3;i<=n-1;i+=2) printf("%d ",i);
            for(i=1;i<=k+1;i+=2)   printf("%d ",i);
            if(n&1) printf("%d ",n);
        }
        else
        {
            for(i=k;i<=n-1;i+=2) printf("%d ",i);
            for(i=1;i<=k-2;i+=2) printf("%d ",i);
            for(i=k+3;i<=n;i+=2) printf("%d ",i);
            for(i=2;i<=k+1;i+=2) printf("%d ",i);
            if(n&1) printf("%d ",n);
        }
    }
    puts("");
}
int main()
{
    int n;
    while(sca(n)&&n) solveQueen(n);
    return 0;
}