Algorithm 版 (精华区)

发信人: GREnTOFEL (Crazy Plucking), 信区: Algorithm
标  题: 递归和回溯---八皇后问题(转载)
发信站: 哈工大紫丁香 (2002年07月06日21:52:05 星期六), 站内信件

【 以下文字转载自 Programming 讨论区 】
【 原文由 zjliu 所发表 】
发信人: violinist (巷战狙击手), 信区: Algorithm
标  题: 递归和回溯---八皇后问题
发信站: 日月光华 (Fri Jul  5 08:28:37 2002)

八皇后问题

------------------------------------------------------------------------------

--

〖问题描述〗
在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列

斜列只有一个皇后）。

〖问题分析〗(聿怀中学 吕思博)
这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决

以下几个问题：
1、冲突。包括行、列、两条对角线：
（1）列：规定每一列放一个皇后，不会造成列上的冲突；
（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为

下标的标记置为被占领状态；
（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i

+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(

i-j)为下标的标记置为被占领状态。
2、数据结构。
（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8
（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8

（3）对角线冲突标记数组C、D。
C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：

-7..7
D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：

2..16

〖算法流程〗
１、数据初始化。
２、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试

当前位置(n,m)是否等于０（未被占领）:
如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；

如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时

，便要进行回溯。
３、当n>8时，便一一打印出结果。


〖优点〗逐一测试标准答案，不会有漏网之鱼。
--

※ 来源:．日月光华 http://bbs.fudan.edu.cn [FROM: 10.11.12.201]




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.229.154]