首页 > 代码库 > POJ 3239 n皇后放置问题

POJ 3239 n皇后放置问题

以前那个是8皇后问题,用的递归写法,然后这个可以求n皇后放置问题,用的纯粹数学方法……神奇!

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <stack>
#include <set>
#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;
}