N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5526 Accepted Submission(s): 2507
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1 8 5 0
Sample Output
1 92 10
Code:
//一种坑爹答案而已
#include"stdio.h"
int main()
{
int a[11] = {1,0,0,2,10,4,40,92,352,724},n,i;
while(scanf("%d",&n),n && n<=10)
{
printf("%d\n",a[n-1]);
}
return 0;
}
下文另附完全版:
超时版本:
//超时版本:
#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;
}
正确版本:
#include<iostream>
using namespace std;
#include"stdio.h"
#define MAX 12
int vst[MAX];
int cnt[MAX];
int ans;
int n;
bool flag; //vst[i]表示第i个皇后的列数,cnt[i]表示放i个皇后的可行方案个数
//ans存放的是当前方案个数,用于赋值给ans[i] ,n表示皇后个数的循环变量
//flag用来表示该位置能不能放皇后,能的话就为true
void DFS(int row) //深搜
{
int i,j;
if(row==n+1) //如果所放皇后个数大于要求个数n, 则该方案可行, ans+1
ans++;
else
for(i=1;i<=n;i++) //该皇后之前的也需要进行循环,先选定一个位置看下面能放几个,如果不够,这个也要换
{ //即首先确定一个位置,接着在剩余行放其余皇后,不行的话更换先确定的位置
flag=true;
vst[row]=i;
for(j=1;j<row;j++) //将该皇后之前的各个皇后都与之进行比较,看是否满足条件
{
if(vst[row]==vst[j]||vst[row]-row==vst[j]-j||vst[row]+row==vst[j]+j) //关键
{ //如果在同一斜线或者同一列就不能放
flag=false;
break;
}
}
if(flag)
DFS(row+1); //如果能放,考虑放置下一个皇后 ,row+1
}
}
int main()
{
int i;
for(n=1;n<11;n++)//从1~10先算出各个方案,下面直接输出~~
{
ans=0;
DFS(1); //每次都是从1开始搜索
cnt[n]=ans;
}
while(~scanf("%d",&n),n)
{
printf("%d\n",cnt[n]);
}
return 0;
}