JAVA练习335- N 皇后

题目概览按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n皇后问题的解决方案。每一种解法包含一个不同的n 皇后问题的棋子放置方案该方案中Q和.分别代表了皇后和空位。示例 1输入n 4输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]解释如上图所示4 皇后问题存在两个不同的解法。示例 2输入n 1输出[[Q]]提示1 n 9来源51. N 皇后 - 力扣LeetCode解题分析方法回溯按照每行进行遍历令当前行为 row每行需要从 [0, n-1] 进行遍历找到第一个元素然后去下一行重复操作下一行以及后面行都遍历完成回溯当前相关参数遍历下一个元素。相关判断条件推理如下列需要保证不重复定义集合 columns 来存储 列 和做判断。从左上往右下的斜线保证不重复斜线可以看做 y -x k 即 x y k同一条斜线 行列 的值是相等的因此定义集合 rightSlash 来存储 x y 和做判断。从左下往右上的斜线保证不重复斜线可以看做 y x k 即 y - x k同一条斜线 行 - 列 的值是相等的因此定义集合 leftSlash 来存储 y - x 和做判断。当 row n 时遍历完成存储结果 然后 回溯直到得到所有答案。时间复杂度O(n!)空间复杂度O(n)class Solution { public ListListString solveNQueens(int n) { ListListString result new ArrayList(); backTracking(result, n, new HashSet(), new HashSet(), new HashSet(), 0, new int[n]); return result; } public void backTracking(ListListString result, int n, SetInteger columns, SetInteger leftSlash, SetInteger rightSlash,int row,int[] queen) { if (row n) { result.add(buildQueen(queen, n)); return; } for (int i 0; i n; i) { if (columns.contains(i)) { continue; } if (leftSlash.contains(row - i)) { continue; } if (rightSlash.contains(row i)) { continue; } columns.add(i); leftSlash.add(row - i); rightSlash.add(row i); queen[row] i; backTracking(result, n, columns, leftSlash, rightSlash, row 1, queen); queen[row] 0; columns.remove(i); leftSlash.remove(row - i); rightSlash.remove(row i); } } public ListString buildQueen(int[] queen, int n) { ListString result new ArrayList(); for (int i 0; i n; i) { char[] row new char[n]; Arrays.fill(row, .); row[queen[i]] Q; result.add(new String(row)); } return result; } }