- 注册时间
- 2005-2-6
- 最后登录
- 2019-7-20
⑥精研
- 积分
- 2641
|
发表于 2009-2-8 22:37:28
|
显示全部楼层
关于回溯算法,最简单的应该就是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;
} |
|