没有合适的资源?快使用搜索试试~ 我知道了~
八皇后 递归实现 c++ 算法
5星 · 超过95%的资源 需积分: 10 27 下载量 190 浏览量
2010-04-16
18:07:24
上传
评论
收藏 4KB TXT 举报
温馨提示
试读
4页
〖问题描述〗 在一个8×8的棋盘里放置8个皇后,要求每个皇后两两之间不相"冲"(在每一横列竖列斜列只有一个皇后)。 〖问题分析〗(聿怀中学吕思博) 这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题: 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 〖算法流程〗 1、数据初始化。 2、从n列开始摆放第n个皇后(因为这样便可以符合每一竖列一个皇后的要求),先测试当前位置(n,m)是否等于0(未被占领): 如果是,摆放第n个皇后,并宣布占领(记得要横列竖列斜列一起来哦),接着进行递归; 如果不是,测试下一个位置(n,m+1),但是如果当n<=8,m=8时,却发现此时已经无法摆放时,便要进行回溯。 3、当n>;8时,便一一打印出结果
资源推荐
资源详情
资源评论
〖问题描述〗
在一个8×8的棋盘里放置8个皇后,要求每个皇后两两之间不相"冲"(在每一横列竖列斜列只有一个皇后)。
〖问题分析〗(聿怀中学吕思博)
这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题:
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
〖算法流程〗
1、数据初始化。
2、从n列开始摆放第n个皇后(因为这样便可以符合每一竖列一个皇后的要求),先测试当前位置(n,m)是否等于0(未被占领):
如果是,摆放第n个皇后,并宣布占领(记得要横列竖列斜列一起来哦),接着进行递归;
如果不是,测试下一个位置(n,m+1),但是如果当n<=8,m=8时,却发现此时已经无法摆放时,便要进行回溯。
3、当n>;8时,便一一打印出结果。
〖优点〗逐一测试标准答案,不会有漏网之鱼。
〖参考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
在一个8×8的棋盘里放置8个皇后,要求每个皇后两两之间不相"冲"(在每一横列竖列斜列只有一个皇后)。
〖问题分析〗(聿怀中学吕思博)
这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题:
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
〖算法流程〗
1、数据初始化。
2、从n列开始摆放第n个皇后(因为这样便可以符合每一竖列一个皇后的要求),先测试当前位置(n,m)是否等于0(未被占领):
如果是,摆放第n个皇后,并宣布占领(记得要横列竖列斜列一起来哦),接着进行递归;
如果不是,测试下一个位置(n,m+1),但是如果当n<=8,m=8时,却发现此时已经无法摆放时,便要进行回溯。
3、当n>;8时,便一一打印出结果。
〖优点〗逐一测试标准答案,不会有漏网之鱼。
〖参考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
资源评论
- Liloy_2012-12-22很不错的程序哟~~
xiansanren
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功