八皇后问题_c语言吧

do熊
2位粉丝

1楼

今天上午考计算方法，有个题要求编程求解八皇后问题，我把大一时写的程序写上去了，ＨＯＨＯ～！～！

在一个8×8的棋盘上放置８个皇后，使得他们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击处在同一行或者同一列或者同一斜线上的其它任何棋子。

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

int Judge(int *p, int j)
　　　　　　　　　　　　//判断当前棋子位置是否符合规则，是则返回1，否则返回0；
{
　　int i;
　　for(i=0;i<j;i++)
　　{
　　　 if(p[j]==p[i])　return 0;
　　　 if(abs(p[j]-p[i])==j-i)　return 0;
　　}
　　return 1;
}

int main()
{
　　　int a[8];　//a[i]表示第i行的后所在位置（a[3]=0表示第3行的后在第0列）
　　　int i=0,j=0,k=0;

　　　for(a[0]=0;a[0]<8;j=0,a[j]++)
　　　　 for(a[++j]=0;a[j]<8;j=1,a[j]++)
　　　　　 if(Judge(a,j))
　　　　　　 for(a[++j]=0;a[j]<8;j=2,a[j]++)
　　　　　　　 if(Judge(a,j))
　　　　　　　　 for(a[++j]=0;a[j]<8;j=3,a[j]++)
　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　 for(a[++j]=0;a[j]<8;j=4,a[j]++)
　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　 for(a[++j]=0;a[j]<8;j=5,a[j]++)
　　　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　　　 for(a[++j]=0;a[j]<8;j=6,a[j]++)
　　　　　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　　　　　 for(a[++j]=0;a[j]<8;a[j]++)
　　　　　　　　　　　　　　　　　 if(Judge(a,j))
　　　　　　　　　　　　　　　　　 {　for(i=0;i<8;i++) printf("%d",a[i]);
　　　　　　　　　　　　　　　　　　　printf("%3s"," ");
　　　　　　　　　　　　　　　　　　　if(!(++k%7)) printf("\n");
　　　　　　　　　　　　　　　　　 }
　　　printf("\n\n%d\n\n",k);
　　　printf("\n请按任意键结束...");
　　　getch();
　　　return 0;
}

2005-1-19 21:48
回复

do熊 2位粉丝	2楼明天考下午考系统结构，考完就解放了，呵呵～！～！这几天，天天考试，每天都是“痛并快乐着”——痛的是一学期过去了，却没学到什么东西，已经是奔四的人了．．．　快乐的是离放假越来越近了，已经一年没回家了，ＨＯＨＯ～！～！
2005-1-19 21:54 回复

218.87.34.*	3楼你是说这个就是皇后问题的最佳解吗？？？
2005-5-27 11:41 回复

茉莉ML
1位粉丝

4楼

这样算是最佳解

class Queen8{

static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];

public static void main(String args[]){
for (int i=0;i<QueenMax;i++)chess[i]=-1;
placequeen(0);
System.out.println("\n\n\n八皇后共有"+oktimes+"个解法 made by yifi 2003");
}

public static void placequeen(int num)
{
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i<QueenMax;i++) qsave[i]=true;

i=0;
while (i<num){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
for(i=0;i<QueenMax;i++){
if (qsave[i]==false)continue;
if (num<QueenMax-1){
chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("这是第"+oktimes+"个解法如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");

for (i=0;i<QueenMax;i++){
String row="第"+(i+1)+"行: ";
if (chess[i]==0);
else
for(int j=0;j<chess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(j<QueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
}
}

2005-5-29 20:15
回复

sufensufen 1位粉丝	5楼程序有错啊！
2005-6-17 18:32 回复

211.141.66.*	6楼不要拿c++的东西出来显。
2005-6-17 20:38 回复

202.114.47.*	7楼 8皇后问题的程序
2005-6-18 21:42 回复

218.19.34.*	8楼那就“抓我”的吧？
2005-6-18 22:04 回复

tomhanks2 0位粉丝	9楼 3awrewar
2005-6-18 22:10 回复

61.134.193.*	10楼拜托，回溯好不好！for(i=1;i<=xxxx;i++);落一块儿吓人啊！！！！
2005-8-6 18:58 回复

220.191.71.*	11楼 4楼,你用JAVA 这是c语言吧
2005-8-26 21:41 回复

202.196.235.*	12楼这怎么是c语言的呢，分明是c++，怎么连着也搞不懂？
2005-8-30 08:42 回复

222.223.70.*	13楼 wqef
2005-8-31 19:40 回复

beckhamch 0位粉丝	14楼晕怎么用这么多递归啊回溯法啊经典例题了
2005-9-1 15:17 回复

茉莉ML 1位粉丝	15楼八皇后问题 :我用的是C++,不是JAVA,摆脱!!!!!11楼
2005-9-22 13:23 回复

yjcqwliu
0位粉丝

16楼

小弟我自认为上面方法都太复杂
斗胆把自己的方法拿出来希望大虾们指点
可惜我没学C++只能用C写
#include<stdio.h>
FILE *fp;
int ha[9],i,a[24],b[24],c[24];
work(i)
{int o,j;
for(j=1;j<9;j++)
if(a[j+7]==0&&b[i-j+7]==0&&c[j+i+7]==0)
{ha[i]=j;
a[j+7]=1;
b[i-j+7]=1;
c[j+i+7]=1;

if(i<8)
work(i+1);
else
{for(o=1;o<9;o++)
{fprintf(fp,"%d ",ha[o]);
}fprintf(fp,"\n");

}
a[j+7]=0;
b[i-j+7]=0;
c[j+i+7]=0;

}
}
main()
{int k;
for(k=0;k<=23;k++)
a[k]=0;b[k]=0;c[k]=0;
fp=fopen("eight.txt","w");
work(1);
fclose(fp);
}

2005-9-25 17:18
回复

yjcqwliu 0位粉丝	17楼哎！！！我写的都没人看一下
2005-9-29 13:19 回复

202.117.64.*	18楼我先来看看谁的是最佳的1!! 呵呵。
2005-10-29 21:32 回复

222.200.164.*

19楼

这是最强的：
/*
* @author cinc 2002-09-11
*
*/

public class Queen {
int size;
int resultCount;

public void compute ( int size ) {
this.size = size;
resultCount = 0;
int data[] = new int[size];
int count; // 所有可能的情况个数
int i,j;

// 计算所有可能的情况的个数
count = 1;
for ( i=0 ; i<size ; i++ ) {
count = count * size;
}
// 对每一个可能的情况
for ( i=0 ; i<count ; i++ ) {
// 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示
// 此处可优化
int temp = i;
for ( j=0 ; j<size ; j++ ) {
data [j] = temp % size;
temp = temp / size;
}
// 测试这种情况是否可行，如果可以，输出
if ( test(data) )
output( data );
}
}

/*
* 测试这种情况皇后的排列是否可行
*
*/
public boolean test( int[] data ) {
int i,j;
for ( i=0 ; i<size ; i++ ) {
for ( j=i+1 ; j<size ; j++ ) {
// 测试是否在同一排
if ( data[i] == data[j] )
return false;
// 测试是否在一斜线
if ( (data[i]+i) == (data[j]+j) )
return false;
// 测试是否在一反斜线
if ( (data[i]-i) == (data[j]-j) )
return false;
}
}
return true;
}

/*
* 输出某种情况下皇后的坐标
*
*/
public void output ( int[] data ) {
int i;
System.out.print ( ++resultCount + ": " );
for ( i=0 ; i<size ; i++ ) {
System.out.print ( "(" + i + "," + data[i] + ") " );
}
System.out.println ();
}
public static void main(String args[]) {
(new Queen()).compute( 8 );
}
}

2006-2-19 13:36
回复

222.246.54.*	20楼大哥,我怎么运行出了102个错误啊难道是我的编译器出问题了?
2006-3-7 11:06 回复

222.246.54.*	21楼有错误 1楼的102个错误 16楼的有2个错误一个警告
2006-3-7 11:08 回复

219.221.109.*	22楼 20 and 21的大虾你会编程么，直接考过去就编译你傻不傻
2006-3-12 14:58 回复

88521apple 0位粉丝	23楼谢谢你们呀！我以前从来都没有听说过八皇后之说，如今老师布置了这个作业了才过来搜搜，原来各位都是高手呀！以后我要向你们学习了！
2006-3-15 20:20 回复

58.19.126.*	24楼那如果是一百皇后的怎么解决?
2006-3-17 12:34 回复

221.6.29.*	25楼请楼主自己算一下你的算法时间复杂度是多少，我以前也用过类似的算法，当时我也只用了八重循环。我觉得用栈或递归实现简单多了。
2006-3-28 21:19 回复

nj25
0位粉丝

26楼

/*
下列程序运行后生成Queen.com文件
再键入Queen<回车>即得92个经典解
*/
#include<stdio.h>
void main()
{FILE*fp=fopen("Queen.com","w");
unsigned char code[]={
0x6A,0x24,0x68,0x20,0x20,0x8B,0xEC,0x8D,
0x56,0xF8,0xB4,0x31,0xB1,0x00,0x8B,0xF4,
0x3B,0xF5,0x74,0x10,0xAC,0x2A,0xC4,0x74,
0x17,0x41,0x3A,0xC1,0x74,0x12,0x02,0xC1,
0x74,0x0E,0xEB,0xEC,0x50,0x44,0x3B,0xE2,
0x75,0xE0,0xB4,0x09,0xCD,0x21,0x4C,0x58,
0xFE,0xC4,0x80,0xFC,0x39,0x75,0xD5,0x3B,
0xE5,0x75,0xF3,0xCD,0x20,};
fwrite(code,1,61,fp);
fclose(fp);
}

2006-3-28 22:18
回复

219.131.159.*	27楼没注释，没算法介绍，叫谁看得懂
2006-3-29 21:41 回复

222.95.173.*	28楼这么短的代码，再要注释、要算法，才叫一个笨呢。
2006-3-30 04:56 回复

218.104.69.*	29楼 26的同志，牛，
2006-4-8 20:47 回复

nj25
0位粉丝

30楼

;谢谢楼上，在下就是26楼
;作为还报，给出汇编代码
;如有必要，可给出Ｃ程序
;毫无疑问，Ｃ无天然堆栈
;生搬硬套，哪能如此精悍
.MODEL
.286
.CODE
ORG 100H
QUEEN: PUSH '$'
PUSH ' '
MOV BP,SP
LEA DX,[BP-08]
NEWL: MOV AH,'1'
NEWC: MOV CL,00
MOV SI,SP
ISOK: CMP SI,BP
JE SAVE
LODSB
SUB AL,AH
JZ NEXT
INC CX
CMP AL,CL
JE NEXT
ADD AL,CL
JZ NEXT
JMP ISOK
SAVE: PUSH AX
INC SP
CMP SP,DX
JNE NEWL
MOV AH,9
INT 21H
BACK: DEC SP
POP AX
NEXT: INC AH
CMP AH,'1'+08
JNE NEWC
CMP SP,BP
JNE BACK
INT 20H
END QUEEN

2006-4-9 05:41
回复



内　容:
用户名:
验证码:	请点击后输入验证码，加入会员后本吧发贴免验证码。

八皇后问题

发表回复