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.
Example:
Input:4Output:[ [".Q..",? // Solution 1? "...Q",? "Q...",? "..Q."], ["..Q.",? // Solution 2? "Q...",? "...Q",? ".Q.."]]Explanation:There exist two distinct solutions to the 4-queens puzzle as shown above.
这题又想吐槽了，因为题目没有给出n不超过32或64，但是最快的答案就是用位运算做出来的。如果n比较大，位运算就没法做了。
要注意的是，用位运算的时候，左移、右移的变量要分开，不能混在一起。因为一个棋子影响范围不能拐弯，只能走横、竖、斜45°其中之一走到底。
// bitmask版本，假设n <= 32
class Solution {
? ? private int lrExists = 0;
? ? private int rlExists = 0;
? ? private int vertExists = 0;
? ? private char[] row = null;
? ? private int ONE = 1 << 31;
? ? public List<List<String>> solveNQueens(int n) {
? ? ? ? List<List<String>> res = new LinkedList<>();
? ? ? ? if (n > 32) {
? ? ? ? ? ? System.out.println("n >= 32 !, n: " + n);
? ? ? ? ? ? return res;
? ? ? ? }
? ? ? ? ArrayList<String> board = new ArrayList<>(n);
? ? ? ? row = new char[n];
? ? ? ? Arrays.fill(row, '.');
? ? ? ? backtrace(board, n, res, 0, 0);
? ? ? ? return res;
? ? }
? ? private void backtrace(ArrayList<String> board, int n, List<List<String>> res, int i, int count) {
? ? ? ? if (i == n || count == n) {
? ? ? ? ? ? res.add(new ArrayList<>(board));
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? for (int j = 0; j < n; j++) {
? ? ? ? ? ? int jMask = ONE >>> j;
? ? ? ? ? ? if (((lrExists & jMask) == 0) && ((rlExists & jMask) == 0) && ((vertExists & jMask) == 0)) {? ?
? ? ? ? ? ? ? ? int oldVertExists = vertExists;
? ? ? ? ? ? ? ? int oldLrExists = lrExists;
? ? ? ? ? ? ? ? int oldRlExists = rlExists;
? ? ? ? ? ? ? ? vertExists |= jMask;
? ? ? ? ? ? ? ? lrExists = (lrExists | jMask) >>> 1;
? ? ? ? ? ? ? ? rlExists = (rlExists | jMask) << 1;
? ? ? ? ? ? ? ? row[j] = 'Q';
? ? ? ? ? ? ? ? board.add(String.valueOf(row));
? ? ? ? ? ? ? ? row[j] = '.';
? ? ? ? ? ? ? ? // System.out.println(String.format("i: %d, j: %d, count: %d", i, j, count));
? ? ? ? ? ? ? ? // System.out.println("board: " + Arrays.deepToString(board.toArray()));
? ? ? ? ? ? ? ? // System.out.println(Integer.toBinaryString(vertExists));
? ? ? ? ? ? ? ? // System.out.println(Integer.toBinaryString(lrExists));
? ? ? ? ? ? ? ? // System.out.println(Integer.toBinaryString(rlExists));
? ? ? ? ? ? ? ? backtrace(board, n, res, i + 1, count + 1);
? ? ? ? ? ? ? ? vertExists = oldVertExists;
? ? ? ? ? ? ? ? lrExists = oldLrExists;
? ? ? ? ? ? ? ? rlExists = oldRlExists;
? ? ? ? ? ? ? ? board.remove(board.size() - 1);
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
// 非位运算版本：
/*class Solution {
? ? private boolean[] lrExists = null; // top-left to right-bottom
? ? private boolean[] rlExists = null;
? ? private boolean[] vertExists = null;
? ? private char[] row = null;
? ? public List<List<String>> solveNQueens(int n) {
? ? ? ? List<List<String>> res = new LinkedList<>();
? ? ? ? ArrayList<String> board = new ArrayList<>(n);
? ? ? ? lrExists = new boolean[2 * n - 1];
? ? ? ? rlExists = new boolean[2 * n - 1];
? ? ? ? vertExists = new boolean[n];
? ? ? ? row = new char[n];
? ? ? ? Arrays.fill(row, '.');
? ? ? ? backtrace(board, n, res, 0, 0);
? ? ? ? return res;
? ? }
? ? private void backtrace(ArrayList<String> board, int n, List<List<String>> res, int i, int count) {
? ? ? ? if (i == n || count == n) {
? ? ? ? ? ? res.add(new ArrayList<>(board));
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? // System.out.println(String.format("i: %d, j: %d, count: %d", i, j, count));
? ? ? ? // System.out.println("board: " + Arrays.deepToString(board.toArray()));
? ? ? ? for (int j = 0; j < n; j++) {
? ? ? ? ? ? if (!(vertExists[j] || rlExists[j - i + (n - 1)] || lrExists[i + j])) {? ?
? ? ? ? ? ? ? ? vertExists[j] = rlExists[j - i + (n - 1)] = lrExists[i + j] = true;
? ? ? ? ? ? ? ? row[j] = 'Q';
? ? ? ? ? ? ? ? board.add(String.valueOf(row));
? ? ? ? ? ? ? ? row[j] = '.';
? ? ? ? ? ? ? ? backtrace(board, n, res, i + 1, count + 1);
? ? ? ? ? ? ? ? vertExists[j] = rlExists[j - i + (n - 1)] = lrExists[i + j] = false;
? ? ? ? ? ? ? ? board.remove(board.size() - 1);
? ? ? ? ? ? }
? ? ? ? }
? ? }
}*/
