首页 > 代码库 > LeetCode: 【L4】N-Queens 解题报告
LeetCode: 【L4】N-Queens 解题报告
【L4】N-Queens 解题报告
N-Queens Total Accepted: 16418 Total Submissions: 63309 MySubmissions
The n-queens puzzle is the problem of placing n queens on an n×nchessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queenspuzzle.
Each solution contains a distinct board configuration of then-queens‘ placement, where ‘Q‘ and ‘.‘ both indicate a queen and anempty 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.."]
]
经典的八皇后问题。
SOLUTION 1:
<此题的难度级别为LEVEL-4>
使用DFS来求解。
主页君写了二个版本来求解。
第一个版本,放置一个皇后之后,从某皇后之后找所有的可能的放置点。这样在Eclipse中可以测试通过,但是
过不了Leetcode的检查。也就是说复杂度过高了。
解法1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
经典的八皇后问题。
SOLUTION 1:
<此题的难度级别为LEVEL-4>
使用DFS来求解。
主页君写了二个版本来求解。
第一个版本,放置一个皇后之后,从某皇后之后找所有的可能的放置点。这样在Eclipse中可以测试通过,但是
过不了Leetcode的检查。也就是说复杂度过高了。
解法1
SOLUTION 2:
后来查资料后,得知为了加快搜索速度,我们应该以这样的思路来思考:
1. 假如我们要放置8个皇后,皇后是会攻击同行的,所以8行必须一行放置一个皇后。
所以前面主页君从某个皇后一直搜索到最后是没有必要的。我们要做的是:放置好一个皇后后,搜索下一行中
能否再放一个皇后,如果是不可以,直接就能返回了。这样子可以节省大量的计算量:
主页君代码如下:
GitHub代码链接
后来查资料后,得知为了加快搜索速度,我们应该以这样的思路来思考:
1. 假如我们要放置8个皇后,皇后是会攻击同行的,所以8行必须一行放置一个皇后。
所以前面主页君从某个皇后一直搜索到最后是没有必要的。我们要做的是:放置好一个皇后后,搜索下一行中
能否再放一个皇后,如果是不可以,直接就能返回了。这样子可以节省大量的计算量:
主页君代码如下:
GitHub代码链接
December 17th, 重写如下:
1 public class Solution { 2 public List<String[]> solveNQueens(int n) { 3 List<String[]> ret = new ArrayList<String[]>(); 4 5 if (n == 0) { 6 return ret; 7 } 8 9 dfs(n, new ArrayList<Integer>(), ret);10 return ret;11 }12 13 public String[] createSolution(ArrayList<Integer> path) {14 /*15 [16 [".Q..", // Solution 117 "...Q",18 "Q...",19 "..Q."],20 21 ["..Q.", // Solution 222 "Q...",23 "...Q",24 ".Q.."]25 ]26 */27 int size = path.size();28 String[] ret = new String[size];29 30 for (int i = 0; i< size; i++) {31 StringBuilder sb = new StringBuilder();32 for (int j = 0; j < size; j++) {33 // a queen.34 if (j == path.get(i)) {35 sb.append(‘Q‘);36 } else {37 sb.append(‘.‘);38 }39 }40 41 ret[i] = sb.toString();42 }43 44 return ret;45 }46 47 //ArrayList<Integer> path: store the index of the columns of one solution.48 public void dfs(int n, ArrayList<Integer> path, List<String[]> ret) {49 if (path.size() == n) {50 String[] solution = createSolution(path);51 ret.add(solution);52 return;53 }54 55 for (int i = 0; i < n; i++) {56 // Judge if this is a solution;57 if (!isValid(path, i)) {58 continue;59 }60 61 path.add(i);62 dfs(n, path, ret);63 path.remove(path.size() - 1);64 }65 }66 67 public boolean isValid(ArrayList<Integer> path, int index) {68 int size = path.size();69 for (int i = 0; i < size; i++) {70 // Same column as one queen.71 if (index == path.get(i)) {72 return false;73 }74 75 // 在两条对角线之上76 // bug 3: 少一个)77 if (size - i == Math.abs(index - path.get(i))) {78 return false;79 }80 }81 82 return true;83 }84 }
步骤:
1. 建立一个arraylist存储每一行的皇后的列值。
例如:第一行皇后在第三列,第二行皇后在第五列,我们会记录3,5在arraylist中,依次这样推下去。
2. 进入DFS后,首先判断array是不是满,满的话说明8个皇后都放好了,创建一个解并返回。
3. 如果没有满,扫描当前行所有的位置,查找是不是能放一个皇后。如果可以放,继续DFS。不能放的话,就退出就好了。
虽然本题了解了思路后,写出来并不难,但主页君认为难点是在于:你怎么能思考到一行一行放皇后?而不是放好一个再找下一个可能放的点?如果想清楚了这一点也就不难了。
LEVEL 4还是实至名归的。
LeetCode: 【L4】N-Queens 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。