MS有种非递归算法 好象在 郑启华的《pascal程序设计(第二版)》清华大学出版社出版里有介绍,忘了怎么写了。。。
是回朔法吧,方法就是遍历每一种摆法,然后用递归打印结果,贪心找不到所有解。我还记得pascal源码,有人要吗?
[源码]关于八皇后问题的解决(深度优先搜索)
众所周知的八皇后问题就是在一个8*8的棋盘上放8个皇后,让她们不能互相攻击,求出所有满足条件的情况。input: n
output: all answers
以下是源码:
#define MAXN 16
int n;
int nsol,nprinted;
char row;
char col;
char updiag;
char downdiag;
void solution()
{
int i;
for(i=0; i<n; i++)
{
if(i!= 0) printf(" ");
printf("%d",row+1);
}
printf("\n");
}
void nway(i,lim)
{
int j;
if(i==n)
{
nsol++;
if (n>6&&row<n/2) nsol++;
if (nprinted++<3) solution();
return;
}
for(j=0; j<lim; j++)
{
if(!col&&!updiag && !downdiag)
{
row = j;
col++;
updiag++;
downdiag++;
nway(i+1,n);
col--;
updiag--;
downdiag--;
}
}
}
int main()
{
scanf("%d",&n);
nway(0,n>6?(n+1)/2:n);
printf("%d\n",nsol);
return(0);
}
在游戏开发中,也许有时会用到这种算法(如:迷宫问题),希望对大家有帮助。
页:
[1]