苏木三少
错的不是你,而是这个世界。

递归-n皇后问题

N皇后

一、题目

N皇后问题
输入一个正整数N,则程序输出N皇后问题的全部摆法。输出结果里的每一行都代表一种摆法。行里的第i个数字 如果是n,就代表第i行的皇后应该放在第n列。皇后的行、列编号都是从1开始算。

样例输入:

4

样例输出:

2 4  1 3

3 1 4 2

二、解题思路

1、对于N*N的棋盘,每行都要放置1个且只能放置1个皇后,利用递归对棋盘的每一行放置皇后,放置时,按列顺序寻找可以放置皇后的列,若可以放置皇后,将皇后放置该位置,并更新mark标记数组,递归进行下一行皇后放置,当该次递归结束后,恢复mark数组,并尝试下一个可能放皇后的列;当递归可以完成N列的N个皇后放置,则将该结果保存并返回。

2、我们使用递归代替循环。

三、C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cmath>
using namespace std;
int N;
int queenPos[100];
//用来存放算好的皇后位置,最左上角是(0,0)
void NQueen(int k);
int main(){
    cin>>N;
    NQueen(0);//从第0行开始摆皇后
    return 0;
}
void NQueen(int k){//在0~k-1行皇后已经摆好的情况下,摆第k行及其后的皇后
    int i;
    if(k == N){//N个皇后已经摆好
        for(i =0;i<N;i++){
            cout<<queenPos[i] + 1 <<"";
        }
        cout<<endl;
        return ;
    }
    for (i=0;i<N;i++){//逐尝试第k个皇后的位置
        int j;
        for(j=0;j<k;j++){
            //和已经摆好的k个皇后的位置进行比较,看是否冲突
            if(queenPos[j]==i || abs(queenPos[j] - i)==abs(k-j))
            break;//冲突检测下一个位置
        }
        if(j == k){//当前的位置i不冲突
            queenPos[k] = i;//将第k个皇后摆放在位置i
            NQueen(k+1);
        }
    }
   
}

 

四、C++截图

赞(1) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » 递归-n皇后问题

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约