在 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---------------------
阅读(1713) | 评论(0) | 转发(0) |
