既然能搜到这篇文章,八皇后问题的规则就不多说了。。。。那什么是回溯算法:回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。
简单地举个例子十进制来说:你从零数到一百过程中(000--100),个位满10时,需要回溯到十位并在十位加1并且个位归零。当十位满10时(如099+1),又要在百位加1并且十位和个位归零。。。。。八皇后问题就类似如此。
-
/*
-
* 1)八皇后问题是在N×8的棋盘上
-
* 2)可以利用一个queen[8]数组存放每行皇后在这行的位置
-
* 如:queen[3]=7 表示第3行的皇后在第七个位置(从0开始)
-
* 3)八皇后位置成立的公式:queen[now_row]!=queen[row],| queen[now_row]-queen[row] | != |now_row-row|
-
* (其中now_row为当前行,row为前now_row-1行,row=0.1.2.3.....now_row-1)
-
*/
-
#include <stdio.h>
-
#include <math.h>
-
#define N 8
-
-
main()
-
{
-
int queen[N];
-
int now_row,row;
-
int count = 1;
-
-
for(now_row = 0; now_row < N; now_row++) queen[now_row] = 0;
-
-
for(now_row = 0;;)
-
{
-
if(queen[now_row] < N)
-
{
-
row = 0;
-
/* 拿那当前第now_row行的皇后位置与前面的第row行(从0开始)皇后位置的比较,
-
* 如果有冲突跳出while循环,且row一定小于;则执行后面的queen[now_row]++(走后一位),然后重新比较
-
* 如果没有冲突,是由于row=now_row推出的,则这次的位置是可以的,继续下一行(now_row+1)
-
*/
-
while( row<now_row && queen[now_row]!=queen[row] && abs(queen[now_row]-queen[row])!=abs(now_row-row)) row++;
-
if( row < now_row)
-
{
-
queen[now_row]++;
-
continue;
-
}
-
if( queen[now_row] >= N) continue; /*如果第now_row行都摆完没有合适的位置,则回到now_row-1行*/
-
now_row++; /*如果第now_row行有合适的位置,则继续摆第now_row+1行*/
-
if(now_row < N) continue; /*如果摆完最后一行(也就是now_row++为8),则出来一个结果*/
-
print(queen,N,count);
-
count++;
-
queen[N-1]++; /*尝试最后一行剩下的位置*/
-
now_row = N-1;
-
}
-
else
-
{
-
/*回溯,第now_row行满时,回到第now_row-1行,queen[now_row]归零,queen[now_row-1]后走一位*/
-
queen[now_row] = 0;
-
now_row--;
-
if(now_row < 0)
-
{
-
printf("THE END\n");
-
return 0;
-
}
-
else
-
queen[now_row]++;
-
}
-
-
}
-
}
阅读(398) | 评论(0) | 转发(0) |