n-+-

N-皇后问题线性时间算法 O(n)复杂度

可以在线性时间构造出一个解
但是要找出所有解得话，还是要回溯搜索


#include "stdio.h"
#include "stdlib.h"

int gs[10001];
int n;
int found;

int qmod(int r,int n)
{
        return (2*r + n/2 - 3)%n;
}

/*
 * works for even n when n%6 != 2
 *
 */
void eq1()
{
        int i;
        for(i=1;i<=n/2;i++)
                gs[i]=2*i;
        for(i=n/2+1;i<=n;i++)
                gs[i]=2*i-n-1;
}

/*
 * works for even n when n%6 != 0
 *
 */
void eq2()
{
        int i;
        for(i=1;i<=n/2;i++)
                gs[i]=qmod(i,n)+1;
        for(i=n/2+1;i<=n;i++)
                gs[i]=n-qmod(n-i+1,n);
}
/*
 * for odd n,we just put a queen at (n,n)
 * then put the others as a n-1 queen problem
 */
void oq()
{
        n--;
        if (n%6 != 2)
                eq1();
        else
                eq2();
        gs[n+1]=n+1;
}

int main()
{
        int i,j;
        int oldn;
        while(scanf("%d",&n) != EOF)
        {
                if (n < 4)
                {
                        printf("Impossible\n");
                        continue;
                }
                oldn=n;
                if (n % 2 == 0 && n%6 != 2)
                        eq1();
                else if (n%2 == 0)
                        eq2();
                else
                        oq();
                for(i=1;i<=oldn;i++)
                        printf("%d ",gs[i]);
                printf("\n");
        }
}