对回溯法提问

august

看严蔚敏书上树的那章，最后提到了一下回溯法，看完不太懂，不知有否简单一点的完整实现的程序，可以参考一下呢(最好是求幂集的)？谢了。

Zelsazgh

关于回溯算法,最简单的应该就是8皇后问题了吧,就是指在8*8的国际象棋盘上摆8个皇后,且符合每个皇后的横,竖,斜线不存在其它皇后
#include <stdio.h>
#define MAX 8
int kpos[MAX];
int place(int count)
{
    int i;
    for(i=0;i<count;i++)
    {
        if(abs(i-kpos)==abs(count-kpos[count] || kpos==kpos[count])
            return 0;
    }
    return 1;
}
int main()
{
    
    int kcount=0;
    while(kcount<MAX)
    {
        kpos[kcount]++;
        for(kpos[kcount];kpos[kcount]<=8;kpos[kcount]++)
        {
            if(placs(kcount))
            {
                kcount++;
                break;
            }
        }
        if(kpos[kcount]>MAX)
    {   
                kpos[kcount]=0;
        kcount--;
        }
    }
     int i;
     for(i=0;i<MAX;i++)
            printf("No.%d:%d",i,kpos);
    return 0;
}

august

怎么感觉好像只是很单纯的递归？

Zelsazgh

呃,递归与回溯的区别不大,要说区别的话,递归是不会有回退再选择其它路径的