August 9, 2008
[算法] 回溯法：八皇后问题
下面还是贴代码，程序会对树进行遍历（共 2057 个节点），从中找出所有可能的解（不同解共 92 个，非唯一解）。
#include <stdio.h>
#define N 8
int solution[N], j, k, count, sols;
int place(int row, int col)
{
for (j = 0; j <row; j++)
{
if (row - j == solution[row] - solution[j] || row + solution[row] == j + solution[j] || solution[j] == solution[row])
return 0;
}
return 1;
}
void backtrack(int row)
{
count++;
if (N == row)
{
sols++;
for (k = 0; k <N; k++)
printf("%d\t", solution[k]);
printf("\n\n");
}
else
{
int i;
for (i = 0; i <N; i++)
{
solution[row] = i;
if (place(row, i))
backtrack(row + 1);
}
}
}
void queens()
{
backtrack(0);
}
int main(void)
{
queens();
printf("Total Solutions: %d\n", sols);
return 0;
}
张家口 at 21:28 Aug 12, 2008 ₪
看不懂代码啊。博主不写点注释。
偶爱偶家 at 13:05 Aug 20, 2008 ₪
你这个算法很好, 但好像跟题目不符, 你这个算法应该是递归, 而不是回溯
北极冰仔 at 14:16 Aug 20, 2008 ₪
@偶爱偶家 正是利用递归来实现回溯。^_^
偶爱偶家 at 16:16 Aug 20, 2008 ₪
好像回溯是不用递归的吧? 有专门的回溯算法写的代码的.
Jiang at 06:37 Aug 21, 2008 ₪
回溯是一种深度优先的搜索算法，所以它可以通过递归来实现，也可以利用栈来实现避免递归，不过本质是一样的。
偶爱偶家 at 08:44 Aug 21, 2008 ₪
jiang的理论很丰富也很高深, 我只能敬仰, 自己是达不到这个深度和广度的.
北极冰仔 at 08:47 Aug 21, 2008 ₪
@偶爱偶家 正是在Jiang的指点之下我才去了解“八皇后”问题的。^_^
偶爱偶家 at 15:14 Aug 22, 2008 ₪
我在学语言的过程中碰到的几个自认为经典的问题， 一个是八皇后， 一个是汉诺塔， 还有一个是围圈报数出列（不知道怎么说）
就是N人围成一个圈， 然后从1－m报数， 报到m的人出列， 接下来继续报， 求最后剩下的是哪一位？
汉诺塔应该是最经典的递归法的习题， 不过汉诺塔也有二叉树的解法， 相比之下， 递归程序简洁， 但效率低， 资源占用大。 而二叉树就快和精简了。