不得不佩服一下数学的力量

N 皇后问题。

最近想用 haskell 写一个通用遗传算法的框架，但是用来解决什么问题做测试呢？我想到了 N 皇后问题，这个很有意思。

但是我不知道对于 N 皇后问题，它是不是有解，于是 google 之，就发现了下面这个很猛的文章。

-------------------------------------------------------

n*n的棋盘，放n个皇后，互不攻击

一、当n mod 6 != 2 或 n mod 6 != 3时，有一个解为：

2,4,6,8,...,n,1,3,5,7,...,n-1       (n为偶数)

2,4,6,8,...,n-1,1,3,5,7,...,n       (n为奇数)

(上面序列第i个数为ai，表示在第i行ai列放一个皇后；... 省略的序列中，相邻两数以2递增。下同)

二、当n mod 6 == 2 或 n mod 6 == 3时，

(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)

k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1         (k为偶数,n为偶数)

k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n       (k为偶数,n为奇数)

k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1               (k为奇数,n为偶数)

k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n           (k为奇数,n为奇数)

程序清单：


#include<iostream>

using namespace std;

int main()

{

       int i,n;

       while (scanf("%d",&n),n)

       {

              if (n%6!=2&&n%6!=3)

              {

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

                            printf("%d ",i);

                     for (i=1;i<n-1;i+=2)

                            printf("%d ",i);

                     printf("%d\n",i);

              }

              else

                     if ((n/2)&1)

                     {

                            for (i=n/2;i<n;i+=2)

                                   printf("%d ",i);

                            for (i=1;i<(n/2)-1;i+=2)

                                   printf("%d ",i);

                            for (i=n/2+3;i<=n;i+=2)

                                   printf("%d ",i);

                            for (i=2;i<n/2;i+=2)

                                   printf("%d ",i);

                            printf("%d\n",i);

                     }

                     else

                     {

                            for (i=n/2;i<=n;i+=2)

                                   printf("%d ",i);

                            for (i=2;i<(n/2)-1;i+=2)

                                   printf("%d ",i);

                            for (i=n/2+3;i<n;i+=2)

                                   printf("%d ",i);

                            for (i=1;i<n/2;i+=2)

                                   printf("%d ",i);

                            printf("%d\n",i);

                     }

       }

       return 0;

}


----------------------
我的天，不服不行，什么也不说了，这就是数学的力量。比那些什么回溯法，什么法，都要快上不知道多少倍，因为它直接给出结果，不可能更快了。
等我的作业写完，一并放上来。起码它让我知道，我的问题是有解的，呵呵。
继续努力学数学了。
---------------------------
另外补充一下，
当 N = 2 和 N = 3 时，用穷举可以知道， 这时无解。
利用 N = 3 时无解，可以知道，对于任意的一个 3x3 的子棋盘，都最多放两个皇后。