首页 > 代码库 > Leetcode: N-Queens
Leetcode: N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
这是一道NP的题目，解题套路与Sudoku Solver类似，类似题目参见Permutations. 主要思想就是一句话：用一个循环递归处理子问题。这个问题中，在每一层递归函数中，我们用一个循环把一个皇后填入对应行的某一列中，如果当前棋盘合法，我们就递归处理下一行，找到正确的棋盘我们就存储到结果集里面。这种题目都是使用这个套路，就是用一个循环去枚举当前所有情况，然后把元素加入，递归，再把元素移除，这道题目中不用移除的原因是我们用一个一维数组去存皇后在对应行的哪一列，因为一行只能有一个皇后，如果二维数组，那么就需要把那一行那一列在递归结束后设回没有皇后，所以道理是一样的。
这道题最后一个细节就是怎么实现检查当前棋盘合法性的问题，因为除了刚加进来的那个皇后，前面都是合法的，我们只需要检查当前行和前面行是否冲突即可。检查是否同列很简单，检查对角线就是行的差和列的差的绝对值不要相等就可以。
1 public class Solution { 2 public ArrayList<String[]> solveNQueens(int n) { 3 ArrayList<String[]> res = new ArrayList<String[]>(); 4 helper(n, 0, new int[n], res); 5 return res; 6 } 7 8 public void helper(int n, int currentrow, int[] colforrow, ArrayList<String[]> res) { 9 if (currentrow == n) { //find a suitable solution, add to result list10 String[] array = new String[n];11 for (int k = 0; k < n; k++) {12 StringBuffer buff = new StringBuffer();13 for (int m = 0; m < n; m++) {14 if (colforrow[k] == m) buff.append(‘Q‘);15 else buff.append(‘.‘);16 }17 String st = buff.toString();18 array[k] = st;19 }20 res.add(array);21 return;22 }23 24 for (int i = 0; i < n; i++) {25 colforrow[currentrow] = i;26 if (check(currentrow, colforrow)) {27 helper(n, currentrow+1, colforrow, res);28 } 29 }30 }31 32 public boolean check(int currentrow, int[] colforrow) {33 for (int temp = 0; temp < currentrow; temp++) {34 if (colforrow[temp] == colforrow[currentrow] || Math.abs(colforrow[temp] - colforrow[currentrow]) == Math.abs(temp - currentrow))35 return false;36 }37 return true;38 }39 }
Leetcode: N-Queens
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。