主题：我自己写的求N皇后 比较短吧
orangelegend
[专家分：860] 发布于 2006-12-09 23:33:00
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<math.h>
#define MAX 100
int pos[MAX]={0};//位置
int n=4;//n为四代表四皇后，为八代表八皇后
void Display(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
if(pos[i]==j) printf("* ");
else printf("0 ");
printf("\n");
}
printf("\n");
}
int OK(int i,int j){//判断布局合法
int k,flag;
flag=1;
for(k=1;k<i;k++)
if(pos[k]==j||abs(j-pos[k])==abs(i-k)) {
flag=0;
break;
}
return flag;
}
void Trial(int i,int n){
int j;
if(i>n) Display();
for(j=1;j<=n;j++)
if(OK(i,j)) {pos[i]=j;Trial(i+1,n);pos[i]=0;}
}
int main(){
Trial(1,n);
return 0;
}
回复列表 （共9个回复）
沙发
orangelegend [专家分：860] 发布于 2006-12-09 23:35:00
四皇后
0 * 0 0
0 0 0 *
* 0 0 0
0 0 * 0
0 0 * 0
* 0 0 0
0 0 0 *
0 * 0 0
六皇后
0 * 0 0 0 0
0 0 0 * 0 0
0 0 0 0 0 *
* 0 0 0 0 0
0 0 * 0 0 0
0 0 0 0 * 0
0 0 * 0 0 0
0 0 0 0 0 *
0 * 0 0 0 0
0 0 0 0 * 0
* 0 0 0 0 0
0 0 0 * 0 0
0 0 0 * 0 0
* 0 0 0 0 0
0 0 0 0 * 0
0 * 0 0 0 0
0 0 0 0 0 *
0 0 * 0 0 0
0 0 0 0 * 0
0 0 * 0 0 0
* 0 0 0 0 0
0 0 0 0 0 *
0 0 0 * 0 0
0 * 0 0 0 0
Press any key to continue
板凳
argentmoon [专家分：13260] 发布于 2006-12-10 00:42:00
可以压在一个函数里，这样就很短了。
判重用数组就可以了，写函数判断效率不高。
3 楼
雪光风剑 [专家分：27190] 发布于 2006-12-12 07:08:00
建立在boolean型可以用int型表示基础上的不严密程序
ok函数应该用boolean写吧
4 楼
orangelegend [专家分：860] 发布于 2007-05-19 22:24:00
今天的我写的
#include<stdio.h>
#include<windows.h>
#define MAX 100
int x[MAX];
int OK(int pos,int n){
int i;
for(i=1;i<=n-1;i++)
if(x[i]==pos||pos-x[i]==n-i||pos-x[i]==i-n)
return 0;
return 1;
}
void Output(int n){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
if(j==x[i]) printf("*");
else printf("&");
printf("\n");
}
printf("\n");
}
void NQueen(int n){
int i;
x[1]=0;
i=1;
while(i>0){
x[i]=x[i]+1;
while(x[i]<=n&&!OK(x[i],i))//剪枝
x[i]=x[i]+1;
if(x[i]<=n){
if(i==n)
Output(n);
if(i<n){//放下一个
i=i+1;
x[i]=0;
}
}
else i=i-1;
}
}
int main(){
int n;
long tstart,tend;
while(1){
scanf("%d",&n);
tstart=GetTickCount();
NQueen(n);
tend=GetTickCount();
printf("Time is %ldms\n",tend-tstart);
}
return 0;
}
5 楼
orangelegend [专家分：860] 发布于 2007-05-19 22:26:00
8皇后的数据与时间 Time is 125ms
&&&&*&&&
&&&&&&*&
&*&&&&&&
&&&&&*&&
&&*&&&&&
*&&&&&&&
&&&*&&&&
&&&&&&&*
&&&&*&&&
&&&&&&*&
&*&&&&&&
&&&&&*&&
&&*&&&&&
*&&&&&&&
&&&&&&&*
&&&*&&&&
太多了，删除了一些
Time is 125ms
6 楼
orangelegend [专家分：860] 发布于 2007-05-19 22:31:00
time is 110ms
time is 110ms
time is 110ms
time is 110ms
0 0 0 0 0 0 0 *
0 0 0 * 0 0 0 0
* 0 0 0 0 0 0 0
0 0 * 0 0 0 0 0
0 0 0 0 0 * 0 0
0 * 0 0 0 0 0 0
0 0 0 0 0 0 * 0
0 0 0 0 * 0 0 0
time is 110ms
8 楼
Fangfangff [专家分：30] 发布于 2007-05-23 16:25:00
我也来顶一个
真的很好!!!!!
你真强啊!!
佩服!!!!
9 楼
chuangjun [专家分：220] 发布于 2007-05-24 12:52:00
那个运行的时间怎么算啊，我相知道哪个算法啊
我来回复
您所在位置：