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
宋振華 閱讀(2317)
評論(0) 編輯 收藏 引用