package Order300;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class T51_n_queens {
public static void main(String[] args) {
BaseNode.util.errPrintList(new Solution().solveNQueens(1), "line", "\n");
}
static class Solution_2ms {
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<List<String>>();
char[][] chessboard = new char[n][n];
for (char[] c : chessboard) {
Arrays.fill(c, '.');
}
trackback(0, n, chessboard, res);
return res;
}
public void trackback(
int row,
int n,
char[][] chessboard,
List<List<String>> res
) {
if (row >= n) {
res.add(Array2List(chessboard));
return;
}
for (int i = 0; i < n; i++) {
if (isValid(chessboard, row, i, n)) {
chessboard[row][i] = 'Q';
trackback(row + 1, n, chessboard, res);
chessboard[row][i] = '.';
}
}
}
public List<String> Array2List(char[][] chessboard) {
List<String> list = new ArrayList<String>();
for (char[] c : chessboard) {
list.add(String.copyValueOf(c));
}
return list;
}
public boolean isValid(char[][] chessboard, int row, int col, int n) {
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 'Q') {
return false;
}
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
}
static class Solution_1ms {
class Solution {
public List<List<String>> solveNQueens(int n) {
int[] queens = new int[n];
Arrays.fill(queens, -1);
List<List<String>> solutions = new ArrayList<List<String>>();
solve(solutions, queens, n, 0, 0, 0, 0);
return solutions;
}
public void solve(
List<List<String>> solutions,
int[] queens,
int n,
int row,
int columns,
int diagonals1,
int diagonals2
) {
if (row == n) {
List<String> board = generateBoard(queens, n);
solutions.add(board);
} else {
int availablePositions =
((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
int position = availablePositions & (-availablePositions);
availablePositions = availablePositions & (availablePositions - 1);
int column = Integer.bitCount(position - 1);
queens[row] = column;
solve(
solutions,
queens,
n,
row + 1,
columns | position,
(diagonals1 | position) << 1,
(diagonals2 | position) >> 1
);
queens[row] = -1;
}
}
}
public List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<String>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
}
static class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
List<List<Character>> path = new ArrayList<List<Character>>() {
{
for (int i = 0; i < n; i++) {
add(
new ArrayList<Character>() {
{
for (int i = 0; i < n; i++) {
add('.');
}
}
}
);
}
}
};
backtrace(
ans,
path,
new boolean[n],
new boolean[2 * n - 1],
new boolean[2 * n - 1],
0,
n
);
return ans;
}
private boolean backtrace(
List<List<String>> answers,
List<List<Character>> path,
boolean[] col,
boolean[] pie撇,
boolean[] na捺,
int step,
int goal
) {
if (step == goal) {
answers.add(
new ArrayList<String>() {
{
for (List<Character> list : path) {
StringBuilder builder = new StringBuilder();
for (Character c : list) {
builder.append(c);
}
add(builder.toString());
}
}
}
);
return true;
}
for (int i = 0; i < goal; i++) {
if (!(col[i] || pie撇[step + i] || na捺[goal + step - i - 1])) {
path.get(step).set(i, 'Q');
col[i] = true;
pie撇[step + i] = true;
na捺[goal + step - i - 1] = true;
backtrace(answers, path, col, pie撇, na捺, step + 1, goal);
path.get(step).set(i, '.');
col[i] = false;
pie撇[step + i] = false;
na捺[goal + step - i - 1] = false;
}
}
return false;
}
}
}
|