易截截图软件、单文件、免安装、纯绿色、仅160KB

递归 回溯法求解8皇后问题(C)

无意中翻出了N年前写的递归-回溯法求解8皇后问题,干粹塞到博客中吧。
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define QUEENS 8
// 记录解的序号的全局变量。
int iCount = 0;
// 记录皇后在各列上的放置位置的全局数组。
int Site[QUEENS];
// 递归求解的函数。
void Queen(int n);
// 输出一个解。
void Output();
// 判断第n个皇后放上去之后,是否有冲突。
int IsValid(int n);
void main()
{
// 从第0列开始递归试探。
Queen(0);
}
//Queen:递归放置第n个皇后。
void Queen(int n)
{
int i;
// 参数n从0开始,等于8时便试出了一个解,将它输出并回溯。
if(n == QUEENS)
{
Output();
return;
}
// n还没到8,在第n列的各个行上依次试探。
for(i = 1 ; i <= QUEENS ; i++)
{
// 在该列的第i行上放置皇后。
Site[n] = i;
// 如果放置没有冲突,就开始下一列的试探。
if(IsValid(n))
Queen(n + 1);
}
}
// IsValid:判断第n个皇后放上去之后,是否合法,即是否无冲突。
int IsValid(int n)
{
int i;
// 将第n个皇后的位置依次于前面n-1个皇后的位置比较。
for(i = 0 ; i < n ; i++)
{
// 两个皇后在同一行上,返回0。
if(Site[i] == Site[n])
return 0;
// 两个皇后在同一对角线上,返回0。
if(abs(Site[i] - Site[n]) == (n - i))
return 0;
}
// 没有冲突,返回1。
return 1;
}
// Output:输出一个解,即一种没有冲突的放置方案。
void Output()
{
int i;
// 输出序号。
printf("No.%-5d" , ++iCount);
// 依次输出各个列上的皇后的位置,即所在的行数。
for(i = 0 ; i < QUEENS ; i++) {
printf("%d " , Site[i]);
}
printf("\n");
}

这一算法求出92种布局。但它们并非本质解,所以输出的布局当中,有一些经过旋转、镜像等变换后是等价的。
如果要求出本质解(应该只有12种),可以考虑将已经求出的布局放在一个链表中,然后每次得到一种新的布局时,都跟前面的依次比较一下,看看经过旋转、镜像后是否一致,如果一样则舍弃。


相关文档:

C Primer Plus里关于文件结尾判断的范例

当尝试从文件读入字符时,getc()函数会返回EOF,所以程序会在下一次读取时才会发现文件结尾。此时程序在试图读取空文件,可能会发生一些问题。所以应当在循环入口处进行判断。
int ch;
FILE * fp;
fp = fopen ("test","r");
while ((ch = getc(fp) != EOF)
{
putchar (ch);
} ......

C函数库介绍: string.h、mem.h

操作函数,所在函数库为string.h、mem.h
mem…操作存贮数组
void *memccpy(void *destin,void *source,unsigned char ch,unsigned n)
void *memchr(void *s,char ch,unsigned n)
void *memcmp(void *s1,void *s2,unsigned n)
int   memicmp(void *s1,void *s2,unsigned n)
void *memmove(void *destin ......

c标准

developerWorks 中国 > Linux > 用 C99 进行开放源代码的开发您的 C 代码符合标准吗? 文档选项 打印本页 将此页作为电子邮件发送 级别: 初级 Peter Seebach (developerworks@seebs.plethora.net), 自由作家 2004 年 4 月 01 日 C99 是什么?谁需要它?它可用了吗?Poter Seebach 讨论了 ISO C 标准的 1999 年修订版 ......

C/C++开发经验人才请进!

上周老板分下来6个职位软件开发方面的职位给我,要我按职位要求寻找合适的人才。居然是C/C++!据我所知,在人才库中,JAVA 人才倒是应有尽有,学C的,还是嵌入式开发的可真的好少啊。我又不是女娲,难道我会造人才么?要求条件还这么高!
以下是大连软件园几家知名外企委托我们招聘的职位信息。
Position 1 软件开发工程师 ......

C/C++位操作

C/C++位操作
一、传统的C方式位操作:
1.基本操作:
  使用一个unsigned int变量来作为位容器。
2.操作符:
|  按位或操作符:result=exp1|exp2;当exp1和exp2中对应位中至少有一个为1时,result中对应位为1,否则为0。
&  按位与操作符::result=exp1&exp2;当exp1和exp2中对应位全为1时 ......
© 2009 ej38.com All Rights Reserved. 关于E健网联系我们 | 站点地图 | 赣ICP备09004571号