讨论/《深度优先搜索》 - 例题:「力扣」第 51 题:N 皇后(困难)/
《深度优先搜索》 - 例题:「力扣」第 51 题:N 皇后(困难)
共 9 个回复

皇后们,你们的皇上来喽~

🥰

5

第26帧动画是多余的

3

软考原题,2019年上半年软件设计师考试下午真题

第4题(案例题):
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
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;
                }
        }
        return2)      ;
}
        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) 。

思路我都明白,但是我就是coding不出来,我尼玛

N皇后,2019年软考 软件设计师 程序解析题原题 2015年也曾经出现过,经典回溯法的考察。

一上来讲回溯就拿个困难题真的好吗

1

是的

图片里那个对角线的数量应该是2N-1吧。