国际象棋八皇后问题是很经典的使用回溯解决实际问题的例子,以前也看过一些很麻烦的例子,索性自己简化一下,使八皇后问题的理解变得简而易懂了
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
宋振华 阅读(4212)
评论(1) 编辑 收藏 引用