本文共 3571 字，大约阅读时间需要 11 分钟。

Solution to the n Queens Puzzle

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 4006		Accepted: 1466		Special Judge

Description

The eight queens puzzle is the problem of putting eight chess queens on an 8 × 8 chessboard such that none of them is able to capture any other. The puzzle has been generalized to arbitrary n × n boards. Given n, you are to find a solution to the n queens puzzle.

Input

The input contains multiple test cases. Each test case consists of a single integer n between 8 and 300 (inclusive). A zero indicates the end of input.

Output

For each test case, output your solution on one line. The solution is a permutation of {1, 2, …, n}. The number in the ith place means the ith-column queen in placed in the row with that number.

Sample Input

80

Sample Output

5 3 1 6 8 2 4 7

Source

, Yao, Jinyu

大致题意：

N皇后问题:

      在NxN棋盘内 纵、横、斜不重叠放置棋子，

      当给定N (N ∈ [8, 300]) 时, 输出任意一种解法

解题思路：

采用构造法：

 而目前网上流传的通解公式，则是为了便于编程，在坐标变换后得到的：

     变换坐标后的求解公式如下：      ① 当m mod 6 != 2 且 m mod 6 != 3时：        (A1):[2,4,6,8,...,m], [1,3,5,7,...,m-1]            (m为偶)        (A2):[2,4,6,8,...,m-1], [1,3,5,7,...,m-2], [m]     (m为奇)        ② 当m mod 6 == 2 或 m mod 6 == 3时，       令 n= m / 2 (m为偶数) 或 n = (m-1)/2 (m为奇数)        (B1):[n,n+2,n+4,...,m], [2,4,...,n-2], [n+3,n+5,...,m-1], [1,3,5,...,n+1]        (m为偶,n为偶)        (B2):[n,n+2,n+4,...,m-1], [1,3,5,...,n-2], [n+3,...,m], [2,4,...,n+1]            (m为偶,n为奇)        (B3):[n,n+2,n+4,...,m-1], [2,4,...,n-2], [n+3,n+5,...,m-2], [1,3,5,...,n+1], [m] (m为奇,n为偶)        (B4):[n,n+2,n+4,...,m-2], [1,3,5,...,n-2], [n+3,...,m-1], [2,4,...,n+1], [m]     (m为奇,n为奇)             上面有六条解序列:         一行一个序列(中括号是我额外加上的，以便辨认子序列)        第i个数为j，表示在第i行j列放一个皇后.        子序列与子序列之间的数序是连续关系(无视中括号就可以了), 所有子序列内j的递增值为2   

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
         using namespace std;  void queens_puzzle(int n)//n>=8{    if(n%6!=2 && n%6!=3)    {        printf("2");        for(int i=4;i<=n;i+=2)            printf(" %d",i);        for(int i=1;i<=n;i+=2)            printf(" %d",i);        printf("\n");    }    else    {        int k=n/2;        if(n%2==0 && k%2==0)        {            printf("%d",k);            for(int i=k+2;i<=n;i+=2)                printf(" %d",i);            for(int i=2;i<=k-2;i+=2)                printf(" %d",i);            for(int i=k+3;i<=n-1;i+=2)                printf(" %d",i);            for(int i=1;i<=k+1;i+=2)                printf(" %d",i);        }        else if(n%2==1 && k%2==0)        {            printf("%d",k);            for(int i=k+2;i<=n-1;i+=2)                printf(" %d",i);            for(int i=2;i<=k-2;i+=2)                printf(" %d",i);            for(int i=k+3;i<=n-2;i+=2)                printf(" %d",i);            for(int i=1;i<=k+1;i+=2)                printf(" %d",i);            printf(" %d",n);        }        else if(n%2==0 && k%2==1)        {            printf("%d",k);            for(int i=k+2;i<=n-1;i+=2)                printf(" %d",i);            for(int i=1;i<=k-2;i+=2)                printf(" %d",i);            for(int i=k+3;i<=n;i+=2)                printf(" %d",i);            for(int i=2;i<=k+1;i+=2)                printf(" %d",i);        }        else        {            printf("%d",k);            for(int i=k+2;i<=n-2;i+=2)                printf(" %d",i);            for(int i=1;i<=k-2;i+=2)                printf(" %d",i);            for(int i=k+3;i<=n-1;i+=2)                printf(" %d",i);            for(int i=2;i<=k+1;i+=2)                printf(" %d",i);            printf(" %d",n);        }        printf("\n");    }}int main(){    int n;    while(~scanf("%d",&n))    {        if(!n) break;        queens_puzzle(n);    }    return 0;}
       
      
     
    
   

 

转载地址：https://joycez.blog.csdn.net/article/details/82790724 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！