Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2349366
  • 博文数量: 816
  • 博客积分: 10000
  • 博客等级: 上将
  • 技术积分: 5010
  • 用 户 组: 普通用户
  • 注册时间: 2008-12-17 17:57
文章分类

全部博文(816)

文章存档

2011年(1)

2008年(815)

分类:

2008-12-17 18:08:38

在 n 行 n 列的国际象棋棋盘上,若两个皇后位于同一行、同一列、同一对角线上,则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后互不攻击的布局

  k=i+j
k=n+i-j-1




安放第 i 行皇后时,需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 )
在第 j 列安放一个皇后:
如果在列、主对角线、次对角线方向有其它皇后,则出现攻击,撤消在第 j 列安放的皇后。
如果没有出现攻击,在第 j 列安放的皇后不动,递归安放第 i+1行皇后。
   
设置 4 个数组
 col [n] :col[j] 标识第 j 列是否安放了皇后
 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后
 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后
 q[n] : q[i] 记录第 i 行皇后在第几列



void Queen( int i ) {
    for ( int j = 0;  j < n;  j++ ) {
        if ( 第 i 行第 j 列没有攻击 ) {
            在第 i 行第 j 列安放皇后;
            if ( i == n-1 ) 输出一个布局;
     else Queen ( i+1 );
   撤消第 i 行第 j 列的皇后;
        }        
    }
}

我们老师这么讲的 你看一看吧



 

--------------------next---------------------

阅读(1717) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~