随笔-20  评论-12  文章-0  trackbacks-0
国际象棋八皇后问题是很经典的使用回溯解决实际问题的例子,以前也看过一些很麻烦的例子,索性自己简化一下,使八皇后问题的理解变得简而易懂了

 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] ? "" : "");
10         }
11         printf("\n");
12     }
13 }



posted on 2009-02-04 16:31 宋振华 阅读(4212) 评论(1)  编辑 收藏 引用

评论:
# re: {5分钟系列}回溯经典教程(八皇后问题)(算法) [原创] 2009-07-25 21:51 | happen23
好代码!很清晰!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理