关于八皇后回溯算法
在网上搜了一段八皇后回溯算法的代码，看了很就实在无法理解它是怎么可以输出所有的结果却不重复的、望大大们讲解一下[code=C/C++][/code]
#include <iostream>
#include <math.h>
#include <malloc.h>
using namespace std;
int *position; //放置的位置
int queen; //皇后数目
int count; //第N种可能性
//判断第n行是否放置皇后
bool SignPoint(int n)
{
for (int i=0;i<n;i++)
{
if (position[i] == position[n]) //该列已经放置过皇后了
return false;
if (abs(position[i] - position[n]) == n-i) //对角线已经放置过了
return false;
}
return true;
}
//设置皇后
void SetQueen(int n=0)
{
if (queen==n)
{
//该处可以改成自己想要的显示方式
printf("NO.%d: ",++count);
printf("\n");
for (int i=0;i<queen;i++)
{
for (int j=0;j<queen;j++)
{
if (j == position[i])
{
printf("* ");
}
else
{
printf("0 ");
}
}
printf("\n");
}
printf("\n");
return;
}
else
{
for (int i=0;i<queen;i++)
{
position[n] = i;
if(SignPoint(n))//如果该位置放置皇后正确的话,则到下一行
{
SetQueen(n+1);
}
}
}
}
int main(int argc, char argv[])
{
cout<<"请输入皇后的总数:"<<endl;
cin>>queen;
position = (int*)malloc(queen*sizeof(int));
SetQueen();
cout<<"摆放完毕"<<endl;
cin.get();
cin.get();
return 0;
}
谢谢了
[解决办法]
这个看程序将没什么意义，还是网上找找八皇后的算法看吧。
因为搜索的路径没有重复的，所以输出的结果也是没有重复的。
[解决办法]
int *position; //放置的位置
这个其实是一个数列，数列内每个元素是一个int值，这个元素的下标就是皇后的排数，int值则是这个皇后的列数，“放置的位置”这个注释感觉迷惑了……
void SetQueen(int n=0)后面的最外作用域的if和else也有点迷惑人……第一次执行的时候if不成立（假定queen不输入0），那么就执行else。
为方便解释，假定queen为2，else下的for循环会执行2次。
for循环第一次中，i=0 n=0，即（0，0）放置皇后，SignPoint（）测试这一行放不放，进入SetQueen(1)，if不成立，再次else,进入for，此时n=1,i=1,即（1，1）放皇后，signPoint()测试这一次的放置不成立，跳回for循环的底部，重新执行for,i++,i=2,此次测试（1，2），成立，进入setQueen(2),n==queen成立，构图。
for循环第二次，大致如上……
这个if和else设计很巧妙，在一个函数里，既放置又测试，if在先，先测试，然后else放置皇后，那么只需要不断的回溯调用这个函数，就可以达到目的。
[解决办法]
