回溯法 N皇后问题 hud题目2553

 

N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5563    Accepted Submission(s): 2518


Problem Description
在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。

 


 

Input
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
 


 

Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。
 


 

Sample Input
1 8 5 0
 


 

Sample Output
1 92 10

 

思路:

给棋盘的行和列都编上1到N的号码,皇后也给编上1到N的号码。

由于一个皇后应在不同的行上,为不失一般性,可以假定第i个皇后将放在第i行上的某列。

因此N皇后问题的解空间可以用一个N元组(X1,X2,.....Xn)来表示,其中Xi是放置皇后i所在的列号。

这意味着所有的解都是N元组(1,2,3,.......,N)的置换。解空间大小为N!。

其次我们看约束条件:因为解空间已经给我们排除了不在同一行(因为每个皇后分别已经对应不同的行号)的约束条件。

我们要判断的是不在同一列和不在同一斜线的约束。因为Xi表示皇后所在的列号,所以如果存在X(k)=X(i)那么肯定存在第k个皇后和第i个皇后同列。所以不同列的判段条件是X(k)!=X(i),1<k<i 。又因为同一斜线的特征是要么行号和列号之和不变(右高左低)要么是行号和列号只差相等(左高右低),所以同斜线的判断条件是 i+X(i)=  k+X(k) 或 i-X(i) =k-X(k),两式合并得 |X(i)-X(k)|=|i-k|

 

 

第一次递归代码:超时

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int sum,x[11];

bool place(int k)
{
    //int i;
    //printf("k=%d\n",k);
    //for(i=1;i<=n;i++) printf("%d ",x[i]);
//    printf("\n");
    int j;
    for(j=1;j<k;j++)
    {
        if(abs(j-k)==abs(x[j]-x[k]) || x[j]==x[k] ) return false; //在同一斜线或同一列    
    }
    return true;
}
void backtrack(int t,int n)
{
    int i;
//    printf("t=%d,n=%d\n",t,n);
//    for(i=1;i<=n;i++) printf("%d ",x[i]);
//    printf("\n");
    if(t>n) {
        sum++;
    //    printf("sum=%d\n",sum);
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            x[t]=i;    
        //    printf("%d\n",place(t,x));
            if(place(t)) backtrack(t+1,n);
        }
    }
}

int main()
{
    int n,i;    
    while(scanf("%d",&n),n)
    {    
        sum = 0;
        for(i=1;i<=n;i++) x[i]=0;
        backtrack(1,n);
        printf("%d\n",sum);
    }
    return 0;
}     


第二次AC 简单打表,因为是N《= 10 ,因此用1中代码,将N等于1 to10都计算出来,放在一维数组

#include <stdio.h>
 
int main()
{
    int a[11]={0,1,0,0,2,10,4,40,92,352,724};
    int n,i;    
    while(scanf("%d",&n),n)    
        printf("%d\n",a[n]);
    return 0;
} 


 

 

 

 

AC代码:15MS  228KB

#include <stdio.h>
#include <math.h>
#include <iostream>

int x[11],cnt[11],n,sum;
bool flag; 

void DFS(int k)//放置第k个皇后 
{
    int i,j,flag;
    if(k>n) {//放置的皇后个数大于n时,表示一种解决方案 
        sum++; 
        return;    
    } 
      for(i=1;i<=n;i++)//将第k个皇后依次放在第1 to n列 
     {
        flag = 1;
          x[k] = i;//列値1 to n
        for(j=1;j<k;j++) //依次与前1到k-1个皇后比较 
        {
            if(x[k]==x[j]||abs(j-k)==abs(x[k]-x[j]))
            {//在同一列或在同一斜线 
                flag = 0; 
                break;    
            } 
        } 
        if(flag) DFS(k+1);//第k个皇后与前k-1个都比交完,互不冲突再放置第k+1个皇后 
       } 
}
 
int main()
{
    for(n=1;n<11;n++)
    {
        sum =0;
        DFS(1);
        cnt[n] = sum;    
    }    
    while(scanf("%d",&n),n)    
        printf("%d\n",cnt[n]);
    return 0;
}