首页 > 试题广场 >

N皇后问题

[编程题]N皇后问题
  • 热度指数：39979 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。

数据范围:
要求：空间复杂度 ，时间复杂度

例如当输入4时，对应的返回值为2，
对应的两种四皇后摆位如下图所示：

示例1

输入

1

输出

1
示例2

输入

8

输出

92
算法知识视频讲解
开通博客
头像 ajaj
发表于 2021-07-14 13:11:19
精华题解 思路: 从题中给出的有效信息： 任何两个皇后不同行，不同列也不再同一条斜线上，计算n皇后的排列种类 由于此题需要对nxn棋盘中的每个点进行判断，在符合情况的点再进行选择，穷举棋盘是不可避免，故此我们可以使用回溯的方法进行解决此问题 方法一：常用-集合 具体做法：1.设置三个集合分别记录不能再被选 展开全文
去ta的博客 赞 (25) 回复(6) 收起
头像 牛客题解官
发表于 2022-04-22 12:31:57
精华题解 题目主要信息: 在一个n∗nn*nn∗n的棋盘上要摆放nnn个皇后，求摆的方案数，不同位置就是不同方案数 摆放要求：任何两个皇后不同行，不同列也不在同一条斜线上 举一反三： 学习完本题的思路你可以解决如下题目： BM55. 没有重复项数字的全排列 BM56. 有重复项数字的全排列 BM58. 字 展开全文
去ta的博客 赞 (20) 回复(8) 收起
头像 数据结构和算法
发表于 2021-03-21 13:19:51
之前在公众号写过和这题类似的的，有兴趣的也可以看下394，经典的八皇后问题和N皇后问题 1，4皇后问题，递归解决 我们来找规律，先看一下4皇后的问题 比如在下面的4*4的格子里，如果我们在其中一个格子里输入了皇后，那么在这一行这一列和这左右两边的对角线上都不能有皇后。 所以有一种方式就是我们一个个去 展开全文
去ta的博客 赞 (53) 回复(0) 收起
头像 思行201910201942631
发表于 2021-09-23 16:03:41
#经典回溯,极简python解答 class Solution: def Nqueen(self , n ): #col: 存储已有的列信息,如[1,4]含义为第1行第1列和第2行第4列已经存放了 #ld: 存储已有的左下对角线信息,特点是行(i) - 列 展开全文
去ta的博客 赞 (19) 回复(1) 收起
头像 漫漫云天自翱翔
发表于 2021-08-01 13:44:49
题解：回溯 首先，每个皇后不能同行，不能同列，不能同斜线。 对于一个3皇后问题，如图： 约束条件判断： 同行和同列好判断，同斜线判断如图： 可以看出斜线约束判断([ (i-1)-(j-1),(i-j),(i+1)-(j 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 Buttered_cat
发表于 2021-01-27 18:22:18
思路 列，对角线，斜对角线是否可放棋子分别用二进制数表示 每次枚举可放棋子的列，使用lowbit运算 参考链接 https://zhuanlan.zhihu.com/p/22846106 class Solution { private: int cnt = 0; int col 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 不想上班的退堂鼓鼓手很精致
发表于 2022-03-18 19:45:00
可以直接看我的博客哦 👉 https://janice143.github.io/myblog.github.io/ 题解思路 看懂此题解之前，需要会做 【BM55 没有重复项数字的全排列】。 如果BM55已经会做了，下面开始看本题解。 👇👇👇 大概思路 n个皇后分别在1，2,3...n行 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 starry陆离
发表于 2022-08-12 16:25:26
👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟 🏡个人主页：starry陆离 如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦 『牛客|每日一题』N皇后问题 1.每日一题 ************ 2.解题思路 2.1思路分析 皇后问题很简单，因为每一行，每一列，每条斜线不能有重复 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 诗云panther
发表于 2021-08-13 17:18:11
import java.util.;public class Solution { /* * * @param n int整型 the n * @return int整型 */ int ans=0; public int Nqueen (int n) 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客346787623号
发表于 2022-05-15 19:58:08
这里的关键就是判断当前的位置是否合法，这里给处最通俗的解释：判断函数输入的row和col表示当前位置的坐标，n是棋盘的大小，我们判断只需要判断当前坐标位置之前的位置知否合法即可，至于接下来的位置，我们等走到了再判断即可，给个图示就通俗了： 如上图所示，只检查箭头的方向，至于下面标红的我们等遍历到 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 温稚
发表于 2023-11-04 21:21:21
本题用递归求解（没有回溯） 题目要求，在n阶矩阵中，找到所有n个皇后摆放方式，摆放要求不能在同一直线1，同一列，以及同一对角线 刚刚开始刷递归以及dfs、回溯的题，在这里总结一下模板， 找出终结条件，即使递归结束的条件 本题为 行数递归到最后一行，代表选择完毕返回 剪枝是对于回溯过程中不合题目要求 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客281174060号
发表于 2022-04-22 15:13:51
我的解题思路如下：对于n*n的这样一个棋盘，其实N皇后问题可以转化为这样一个问题，给定一个list，[0,1,2,```,n-1]，index代表行，list[i]代表第i行的皇后所在的列，比如list[1]=2,代表第1行的皇后在第2列，皇后的方法其实有n!种，也就是这个list的一个全排列，这种 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

递归
难度：
129条回答 5257浏览

热门推荐

通过挑战的用户

相关试题

N皇后问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号