问题描述:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q'
and '.'
both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
原问题链接:https://leetcode.com/problems/n-queens/
问题分析
这是经典的8皇后问题的一个衍生。对于这个问题的要求来说,我们需要在给定的n行n列的 矩阵里找到n个元素,它们每个元素即不在同一行,也不在同一列,同时也不在对角线上。以下图为例:
在图中a点上,它所在的行与列,以及两个方向的对角线上的位置都不能放其他的元素。这样才算是一个合格的位置。这样,由于我们需要在每一行放置一个元素,所以这些所有n个元素必须都满足上面这个条件。
那么,现在该怎么来实现它呢?因为我们要找到所有符合条件的布局,所以一种思路就是我们从第一行起遍历这一行的每一个位置,然后递归的去下一行设置下一个元素,直到最后一行。每次我们选择可以在当前行放置的元素才能递归到下一步。
从实现的细节来看,我们可以定义一个递归的函数nQueens(List<List<String>> result, int[] positions, int cur, int n)。这里result用来保存最终的结果,在每次递归调用到最后一行的时候表示找到了一个符合条件的结果,要把结果加入到result中间,所以需要把它作为一个参数传递进来。positions这个数组用来保存在当前行之前每一步所放置元素的位置。比如说第一行元素放置的是第一列,那么positions[0] = 0,0即是这个位置的索引。每次当前位置找到合格的元素之后就将该元素的索引设置到positions[cur]这个位置。这个递归函数的一个返回条件是当cur == n的时候。n表示矩阵的行数。
另外一个,对于任意两个点所在行i, j,我们要判断它们是否构成合法的布局,可以通过判断它们两个是否在同一行(i == j), 同一列(positions[i] == positions[j])以及同一对角线(Math.abs(j - i) == Math.abs(positions[j] - positions[i]))来确定。所以经过上述的讨论,可以得到如下的代码:
public class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); if(n < 1) return result; int[] positions = new int[n]; nQueens(result, positions, 0, n); return result; } public void nQueens(List<List<String>> result, int[] positions, int cur, int n) { if(cur == n) { result.add(generatePosition(positions, n)); return; } for(int i = 0; i < n; i++) { if(validPosition(i, cur, positions)) { positions[cur] = i; nQueens(result, positions, cur + 1, n); } } } public boolean validPosition(int i, int cur, int[] positions) { for(int j = 0; j < cur; j++) { if(positions[j] == i || Math.abs(j - cur) == Math.abs(i - positions[j])) return false; } return true; } public List<String> generatePosition(int[] positions, int n) { List<String> list = new ArrayList<>(); for(int i = 0; i < positions.length; i++) { StringBuilder sb = new StringBuilder(); for(int j = 0; j < n; j++) { if(j == positions[i]) sb.append('Q'); else sb.append('.'); } list.add(sb.toString()); } return list; } }
相关推荐
leetcode 71 Python用 Python 编写 Leetcode (数据科学家的解决方案) - 易于理解的最佳解决方案,可以通过所有 Leetcode 测试用例,对于非 ...leetcode ...leetcode ...N-Queens (HARD) Leetcode 52. N-
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码写的很飘逸,果然是有LISP...N-Queens N-Queens II Balanced Binary Tree Binar
leetcode怎么销号 LeetCode-Solutions :green_heart:My ...N-Queens Hard 回溯 0053 Maximum Subarray Easy 动态规划 0069 Sqrt(x) Easy 二分、牛顿迭代 0070 Climbing Stairs Easy 动态规划 0075 Sort Colors M
051:N-Queens 052:N-Queens II 071: Letter Combinations of a Phone Number 093:Restore IP Addresses 树的遍历问题也可以用这种思想来解释。只不过是特殊的递归而已。(只有两路,不用循环) 题型二:动态规划...
比如n-queens-ii对应链接为: 题目 url add-two-numbers find-peak-element longest-common-subsequence longest-consecutive-sequence max-area-of-island next-greater-element-ii serialize-and-deserialize-...
leetcode中国力码 我的 Leetcode 生活经历! 我创建了这个存储库来分享我对 leetcode 问题的解决方案。 另外,我会补充一下我在解决问题时的想法,也会补充一些简单的测试用例以供...N-Queens(硬) 56. 合并间隔(中)
leetcode 推开箱子进深 Leetcode-May-Challenge-2021 它包含 Leetcode May Challenge 2021 的解决方案 比赛链接: 问题 问题名称 点击打开问题 无向图中的连通分量数 ...N-皇后 ...N-Queens II 最大差距 搜索建议系统
leetcode ...N-Queens II 最大子阵列 螺旋矩阵 跳跃游戏 合并间隔 插入间隔 螺旋矩阵 II 排列顺序(无法访问文章) 61-70 轮换名单 独特的路径 独特的路径 II 最小路径和(无法访问文章) 有效号码 加一
leetcode 530 leetcode 我对 leetcode 的解决方案。 使用c++解决问题。 # 标题 解决方案 标签 方法 1185 一周中的天 大批 5499 检测长度模式重复 k 次或多次 大批 ...n-queens-ii DFS,搜索 1003 替
N-Queens II 平衡二叉树 二叉树中序遍历 二叉树最大路径和 将排序数组转换为二叉搜索树 将排序列表转换为二叉搜索树 将二叉树展平到链表 二叉树的最大深度 二叉树的最小深度 路径和 排列 排列二 在每个节点中填充下...
leetcode力扣是什么 leetcode-按类别 看了一些leetcode刷题指南,总结一下两个重点,一是...N-Queens (hard) 132 Palindrome Partitioning (hard) 212 Word Search II (hard) DFS /二叉树 the difference between df
leetcode ...NQueens * 回溯法- 网易2017算法工程师笔试题3 * 贪心法- Dijkstra算法 ShortestDistanceAlgorithm * 动态规划- Floyd最短路径算法 ShortestDistanceAlgorithm * 动态规划- 最长公共子序列 ...
leetcode 530 力码练习 前 250 个问题 1 二和 :check_mark: 3 无重复字符的最长子串 :check_mark: 4 两个有序数组的中位数 5 最长回文子串 7 反转整数 8 字符串到整数 (atoi) 10 正则表达式匹配 11 盛水的容器 12 ...
leetcode 棋盘算法实现 有趣的算法或有趣的算法实现 动态规划(非常基础)/递归 ...nQueens.py 很少包含外部库,所以下面的就可以了。 编译任何 C 程序: gcc -o X Xc 执行 python 脚本: chmod 755 X.py --> ./X.py
49组Anagrams视频讲解50 Pow(x,n)视频讲解51 N-Queens视频讲解52 N-Queens II视频讲解53最大子数组视频讲解54螺旋矩阵视频讲解55跳转游戏视频讲解56合并间隔视频讲解57插入间隔视频讲解59螺旋矩
leetcode 2 和 c PlayLeetCode 基于c++的LeetCode训练 尖端: 单击问题的Number (#) 单击Solution ([00xx-Solution]) 到解决方案 # 标题 困难 方法 解决方案 二和 简单的 ...N ...N-皇后 ...N-Queens II 难的
N-Queens II 59.44% 97 交错串 TLE 146 LRU缓存 83.44% 174 地牢游戏 100% 的 Go 提交 354 俄罗斯娃娃信封 23.99% 中等评价 数量 问题 殴打 2 添加两个数字 35.18% 3 无重复字符的最长子串 79.27% 5 最长回文子串 87...
lru缓存leetcode leetcode 版权所有 (C) 2015-2016 Cloudzfy。 版权所有。 ================================================== ====== 二和 两个数字相加 ...N ...n) N-皇后 N-Queens II 最大子阵列 螺旋矩阵
leetcode中文版lintcode题解 相关链接 目录 指数 标题 代码 困难 1 A + ...N-皇后 ...N-Queens II 中等的 35 反向链表 简单的 36 反向链表 II 中等的 37 反转 3 位整数 幼稚的 38 搜索二维矩阵 II 中等
NQueens CPP 回溯 哇 052. NQueensII CPP 回溯 088. 合并排序数组 CPP 大批 118. 帕斯卡三角形 CPP 大批 217. 包含重复 CPP 大批 219. 包含副本 II CPP 大批 283. 移零 CPP 大批 321. 创建最大数 CPP DP,贪婪 402....