國際象棋八皇后問題是很經典的使用回溯解決實際問題的例子,以前也看過一些很麻煩的例子,索性自己簡化一下,使八皇后問題的理解變得簡而易懂了
1 Void fill_queen(Int board[], Int nRow = 0, Int nSize = 8) // board[i]記錄了第i行皇后所在的位置
2 {
3 if(nRow==nSize) // 設置遞歸返回條件
4 {
5 display(board,nSize); // 顯示棋盤
6 return;
7 }
8 for(Int col=0; col<nSize; col++)
9 {
10 for(Int i=0; i<nRow; i++) //尋找有沒有跟(nRow,col)沖突的位置
11 {
12 if(abs(nRow-i) == abs(col-board[i]) || col == board[i]) //對角線或者豎線沖突
13 {
14 goto next; // 有沖突就測試下一列
15 }
16 }
17 board[nRow] = col;
18 fill_queen(board,nRow+1,nSize);
19 next:;
20 }
21 }
1 Void display(Int board[], Int nSize) // 顯示棋盤(非算法部分)
2 {
3 static Int count = 0;
4 printf("\n************* 第%2d種 *************\n",++count);
5 for(Int i=0; i<nSize; i++)
6 {
7 for(Int j=0; j<nSize; j++)
8 {
9 printf(j==board[i] ? "1 " : "0 ");
10 }
11 printf("\n");
12 }
13 }
posted on 2009-02-04 16:31
宋振華 閱讀(4221)
評論(1) 編輯 收藏 引用