2020-05-03 51. N-Queens Hard
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);
}
}
}
}*/
