【力扣-困难】51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例： 输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。 提示： 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens

【回溯】

public List<List<String>> solveNQueens(int n) { //每行的皇后所在的列 int[] queen = new int[n]; Arrays.fill(queen,-1); List<List<String>> solution = new ArrayList<>(); solve(solution,queen,n,0,0,0,0); return solution; } private void solve(List<List<String>> solution,int[] queen,int n,int row,int col, int dia1,int dia2) { if (row == n){ solution.add(generate(queen)); }else { //(col|dia1|dia2)是皇后不能放的位置,取反码再和n个位置与运算后，二进制串中1的位置就是皇后能放置的位置 int availablePositions = ((1<<n)-1) &(~(col|dia1|dia2)); while (availablePositions!=0){ //得到二进制串最低位的1所在位置 int position = availablePositions & (-availablePositions); //得到位置后最低位的1清零，继续向高位遍历 availablePositions &= (availablePositions - 1); //position二进制串的1在第几位 queen[row] = Integer.bitCount(position-1); solve(solution, queen, n,row+1, col | position, (dia1 | position) >> 1, (dia2 | position) << 1); //清掉这个皇后进行下一次尝试 queen[row] = -1; } } } private List<String> generate(int[] queen) { int len = queen.length; List<String> ans = new ArrayList<>(); for (int value : queen) { char[] res = new char[len]; Arrays.fill(res, '.'); res[value] = 'Q'; ans.add(new String(res)); } return ans; }