N皇后问题是一个老掉牙的问题了,随便翻一本算法书籍都能看到对它的介绍,其实N皇后问题可以用非递归方法解决,有效避免N过大时的递归工作栈溢出,且占用的存储空间较小,运行速度也较快,达到运行速度和空间合理利用的两全,代码很简单,并不复杂,有时简单也是一种美,意味着可靠和高效。追求程序的复杂和难以理解的编程者不会认同这一点,但对用简单的设计就可以解决的问题用复杂的数据表示加以描述是没有必要的。
代码如下(C语言):
#include <stdio.h>
#include <malloc.h>
#include <math.h>
int place(int i, int k, int *p); //检查k+1行i列能否放置皇后,能返回1,否则返回0
int find(int n, int *p, int k); //在k+1行搜索可以放置皇后的位置,找到位置后返回列标,否则返回0
void output(int n, int *p); //输出n皇后问题的一个解
void main()
{
int k, n;
int m;
int *p;
printf("you want to solve n queens problem\n");
printf("n=");
scanf("%d", &n); //输入问题规模
p=(int *) malloc(n*sizeof(int)); //p[k]表示k+1行皇后所在列
for (k=0; k<n; k++)
{
p[k]=0; //初始化数组p
}
k=0; //初始化为第一行
m=0; //记录解的个数变量初始化
loop: if (k==0) //进入或回溯至第一行
{
p[k]=p[k]+1; //试探下一列
if (p[k]>n) //第一行所有列试探完毕,回溯结束
{
goto exit;
}
k++; //试探下一行
goto loop;
}
else
{
if (find(n, p, k)==0) //k+1行没有找到可放置皇后的位置
{
p[k]=0; //必要的清理
k--; //回溯
goto loop;
}
else
{
p[k]=find(n, p, k); //在k+1行找到的位置赋予p[k]
if (k!=(n-1)) //皇后没有全部放置完毕
{
k++; //试探下一行
goto loop;
}
else //皇后全部放置成功,找到解
{
m++;
printf("The %dnd solution\n", m);
output(n, p); //输出解
goto loop; //回溯
}
}
}
exit: ;
printf ("There are %d solutions in total\n", m);&nbs