n皇后问题描述为：在一个n×n的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即任意两个皇后不在同一行、同一列或者同一斜线上。
算法的基本思想如下：
将第i个皇后摆放在第i行，i从1开始，每个皇后都从第1列开始尝试。尝试时判断在该列摆放皇后是否与前面的皇后有冲突，如果没有冲突，则在该列摆放皇后，并考虑摆放下一个皇后；如果有冲突，则考虑下一列。如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后，……，直到找到所有合理摆放方案。
【C代码】
下面是算法的C语言实现。
（1）常量和变量说明
n:皇后数，棋盘规模为n×n
queen[]:皇后的摆放位置数组，queen[i]表示第i个皇后的位置，1≤queen[i]≤n
（2）C程序
#include＜stdio.h>
#define n 4
int queen[n+1];
void Show（ ）{/*输出所有皇后摆放方案*/
int i;
printf("(");
for(i=1;i＜=n;i++){
printf("%d",queen[i]);
}
printf(")\n");
}
int Place(int j){/*检查当前列能否放置皇后，不能放返回0，能放返回1*/
int i;
for(i=1;i＜j;i++){/*检查与已摆放的皇后是否在同一列或者同一斜线上*/
if((（1）)‖abs(queen[i]-queen[j])==(j-i)){
return 0;
}
}
return（2）;
}
void Nqueen(int j){
int i;
for(i=1;i＜=n;i++){
queen[j]=i;
if(（3）){
if(j==n){/*如果所有皇后都摆放好，则输出当前摆放方案*/
Show（ ）;
}else{/*否则继续摆放下一个皇后*/
（4）;
}
}
}
}
int main（ ）{
Nqueen(1);
return 0;
}
【问题1】（8分）
根据题干说明，填充C代码中的空（1）（4）。
【问题2】（3分）
根据题干说明和C代码，算法采用的设计策略为（5）。
【问题3】（4分）
当n=4时，有（6）种摆放方式，分别为（7）。
正确答案及解析
正确答案
解析
【问题1】
（1）queen[i]==queen[j]或其等价形式
（2）1
（3）Place(j)或其等价形式
（4）Nqueen(j+1)
【问题2】
（5）回溯法
【问题3】
（6）2个
（7）（2413）或（2,4,1,3）
（3142）或（3,1,4,2）
【问题1】
（1）第一空根据代码上下文：
for(i=1;i＜j;i++){/*检查与已摆放的皇后是否在同一列或者同一斜线上*/
if(（1）)‖abs(queen[i]-queen[j])==(j-i)){
return 0;
}
}
abs(queen[i]-queen[j])==(j-i)判断是否在同一斜线上，此处还缺少对同一列的判断，即queen[i]==queen[j]或其等价形式。
（2）第二空根据Place(int j)函数首行注释：
int Place(int j){/*检查当前列能否放置皇后，不能放返回0，能放返回1*/
此处是成功后的返回，返回值应该是1。
（3）第三空根据代码上下文
if(（3）){
if(j==n){/*如果所有皇后都摆放好，则输出当前摆放方案*/
Show();
}else{/*否则继续摆放下一个皇后*/
（4）;
}
}
（3）与j==n结合可以判断所有皇后都摆好，（3）与j!=n结合可以判断继续摆放下一个皇后，即前面的皇后已摆放好。
所以（3）的判断条件应该是摆放函数Place()返回值为1，即（3）Place(j)或其等价形式。
（4）第四空填写摆放下一个皇后，即（4）Nqueen(j+1)。
【问题2】
根据题干描述“如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后”，本题采用的是回溯法的设计策略。
【问题3】
当n=4时，可以有2种摆放方式，如下所示：
即（2413）（3142）。
包含此试题的试卷
你可能感兴趣的试题
E-mail地址由分隔符“（）”分为前后两部分，分别指明用户名及邮件
-
- A.//
- B.\\
- C.@
- 查看答案
某 html 文档中有如下代码，则在浏览器中打开该文档时显示为（ ）。
＜form>
Listl:
＜input type="text" name="List1" />
＜br / >
List2:
＜input type="text" name="List 2 " />
＜ /form>
-
- A.见图A
- B.见图B
- C.见图C
- D.见图D
- 查看答案
设有商品关系P（商品名，条形码，供应商号，价格，数量）， “条形码”唯一标识关系P中的每一个元组，商品名不能为空，供应商号是关系P的外键。另有供应商关系S（供应商号，供应商名，地址，电话）。关系 P 中的商品名是唯一的。建立商品关系 P 的 SQL语句如下所示：
CREATE TABLE P( 商品名CHAR(30)（ ），
条形码CHAR(30) （ ） ，
供应商号 CHAR(5) ，
价格 CHAR(20) ，
数量CHAR(20)
（ ）(供应商号) REFERENCES S(供应商号));
查询供应商及价格小于等于 2500 元且大于等于 1280 元的“电冰箱”的数量的SQL语句为：
SELECT商品名，供应商名，价格，数量
FROM P
WHERE商品名= ’电冰箱’ AND （ ） ;
将供应商号“12021”所供应的商品价格上涨3％的SQL语句为：
UPDATE P
（ ）
WHERE 供应商号= ’12021’;
查询供应商地址包含“西安”的供应商名及电话的SQL语句为：
SELECT供应商名，电话
FROM S
WHERE （ ）;
-
- A.NULL
- B.UNIQUE
- C.NOT NULL
- D.NOT NULL UNIQUE
- 查看答案
函数f()、g()的定义如下所示。已知调用f时传递给其形参x的值是1，若以传值方式调用g，则函数f的返回值为（ ）；若以传引用方式调用g，则函数f的返回值为（ ）。
-
- A.3
- B.4
- C.6
- D.7
- 查看答案
-
- A.见图A
- B.见图B
- C.见图C
- D.见图D
- 查看答案