N皇后

N皇后问题是计算机科学中最为经典的问题之一,该问题可追溯到1848年,由国 际西洋棋棋手马克斯·贝瑟尔于提出了8皇后问题。 将N个皇后放摆放在N*N的棋盘中,互相不可攻击,有多少种摆放方式,每种摆 放方式具体是怎样的? LeetCode 51. N-Queens

皇后的攻击范围

若在棋盘上已放置一个皇后,它实 际上占据了哪些位置?

以这个皇后为中心,上、下、左、 右、左上、左下、右上、右下,8个方向的位置全部被占据。

思考: 若在棋盘上放置一个皇后,如右图 ,标记为红色位置即不可再放 其他皇后了,如何设计算法与 数据存储,实现这一过程?

方向数组:

static const int dx[]= {-1,1,0,0,-1,-1,1,1}
static const int dy[]= {0,0,-1,1,-1,1,-1,1}

分别表示上,下,左,右,左上,右上,左下,右下。

第X行,y列放置皇后,mark[行][列]表示一张期盼

void put_down_the_queen(int x, int y, std::vector<std::vector<int>> & mark){
    static const int dx[]= {-1,1,0,0,-1,-1,1,1}
    static const int dy[]= {0,0,-1,1,-1,1,-1,1}//方向数组;
}
    mark[x][y] = 1;//(x,y)放置皇后,进行标记
    for(int i = 1; i < mark.size(); i++){ //8个方向,每个方向向外延伸至1至N-1
        for( int j = 0; j < 8; j++){
            int new_x = x + i *dx[j];
            int new_y = y + i *dy[j];
            if(new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()){
                mark[new_x][new_y] = 1;
            } 
        }
     }
算法设计

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

class Solution{
public:
    std:: vector<std::vector<std::string>> solveNQueens(int n){
    std::vector<std::vector<std::string>> result;//储存最终结果的数组
    std::vector<std::string> location;//存储某个摆放结果,当完成一次递归找到结果后,将location push进result
    std::vector<std::vector<int>> mark;//标记棋盘是否可以放置皇后的数组
    for(int i = 0 ; i < n; i++){
        mark.push_back((std::vector<int>()))//初始化mark
        for(int j = 0;j<n;j++){
            mark[i] = push_back(0);
        }
        location.push_back("");
        location[i].append(n,'.');   
    } 
    generate(0, n, location, result, mark);
    return result;
private:
    void put_down_the_queen(int x, int y, std:: vector<std::vector<int>> &mark){}
}
};
//k 代表完成了几个皇后的位置(正在放置第k)
void generate(int k, int n , std::vector<std::string> & location, std:: vector<std:: vector<std::vector<std:: string>>> & result, std:: vector<std::vector<int>> &mark){
    if(k == n ){// 当k==n时,代表完成了第0至n-1行
      result.push_back(location);//皇后的放置,所有皇后完成放置后,将记录皇后位置的location数组push进入result
      return ; 
    }
    for( int i = 0; i < n; i++){//按顺序尝试第0-n-1列
        if(mark[k][i] == 0){// 如果mark[k][i] ==0,即可以放置皇后
            std::vector<std::vector<int>> tmp_mark = mark;//记录回溯mark镜像
            location[k][i] = 'Q';// 记录当前皇后的位置
            put_down_the_queen(khi,mark);//放置皇后
            generate(k+1,n,location,result,mark);//递归下一行皇后放置
            mark == tmp_mark;//将mark重新赋值为回溯前状态
            location =='.';
           
        }
    }
    
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏哈雷彗星撞地球

设计模式中的设计原则

翻了三本书《设计模式之禅》、《设计模式:可复用的面向对象软件元素》、《Head First 设计模式》,也看了不少博客和关于设计模式原则的文章。关于设计模式有几...

893
来自专栏Nian糕的私人厨房

腾讯课堂 IMWeb 七天前端求职提升营 Day 5

本次的系列博文主要是针对 腾讯课堂七天前端求职提升营 课程中,所推送的面试题目及编程练习的一次汇总,期间还包括三次直播课的分享,均由腾讯导师给大家讲解,该系列博...

1084
来自专栏CDA数据分析师

怎么样才算是精通 Python?

CDA专题线上活动“Python Week”即将上线,一大波Python技能马上来袭,敬请期待! 本文是对知乎问题“怎么样才算是精通 Python?”的回答,作...

4788
来自专栏平凡文摘

关于Java的10个误解

1654
来自专栏老码农专栏

原 OSGL 工具库 - IO 操作的艺术

1485
来自专栏互联网大杂烩

6大设计原则

所有引用基类的地方必须能透明地使用其子类对象。 只要父类能出现的地方子类就可以出现。

973
来自专栏Core Net

一个插排引发的设计思想 (一) 观察者模式

2966
来自专栏前端新视界

关于面试题 Array.indexof() 方法的实现及思考

这是我在面试大公司时碰到的一个笔试题,当时自己云里雾里的胡写了一番,回头也曾思考过,最终没实现也就不了了之了。 昨天看到有网友说面试中也碰到过这个问题,我就重新...

2429
来自专栏IT派

两句话轻松掌握 Python 最难知识点

千万不要被所谓"元类是99%的python程序员不会用到的特性"这类的说辞吓住。因为每个中国人,都是天生的元类使用者

1392
来自专栏点滴积累

shapeless官方指南翻译写在前面

目录 前言 Shapeless简介 The Type Astronaut's Guide to Shapeless简介 总结 一、前言        在我的20...

3787

扫码关注云+社区

领取腾讯云代金券