5皇后问题:在8*8的国际象棋棋盘上，放5个皇后，使它们控制整个棋盘，即在任何一格放一个棋子，都会马上被吃掉。
下面介绍回溯解法
定义一个表示点的数据结构:
1 struct Pt {Int x,y;};
算法:
1 Void show_five_queen(Pt arr[],Int x = 0,Int y = 0,Int k = 0)
2 {
3 if(k==5)
4 {
5 check(arr);
6 return;
7 }
8 for(Int i=x; i<8; i++)
9 {
10 for(Int j=y; j<8; j++)
11 {
12 arr[k].x = i;
13 arr[k].y = j;
14 show_five_queen(arr,i+((j+1)/8),(j+1)%8,k+1); // 避免重复回溯,要求只按索引顺序显示所有点
15 }
16 }
17 }
终止条件:
1 Void check(Pt arr[])
2 {
3 for(Int i=0; i<8; i++)
4 {
5 for(Int j=0; j<8; j++)
6 {
7 Bool found = False;
8 for(Int k=0; k<5; k++)
9 {
10 if(arr[k].x==i || arr[k].y==j || abs(arr[k].x-i)==abs(arr[k].y-j))
11 {
12 found = True;
13 break;
14 }
15 }
16 if(!found)
17 return;
18 }
19 }
20
21 showboard(arr);
22 }
效果图:
posted on 2009-02-10 11:25
宋振华 阅读(2246)
评论(0) 编辑 收藏 引用