import java.util.*;
public class NQueens {
public static List> solveNQueens(int n) {
List
> result = new ArrayList<>();
char[][] board = new char[n][n];
// Init board with dots
for (int i = 0; i < n; i++ ) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
solve(0, board, result);
return result;
}
public static void solve(int row, char[][] board, List
> result) {
System.out.println("solve20row: " + row);
if (row == board.length) {
result.add(constructSolution(board));
return;
}
for (int col = 0; col < board.length; col++) {
System.out.println("solve25col: " + col);
if (isValidPlacement(board, row, col)) {
board[row][col] = 'Q';
solve(row + 1, board, result);
board[row][col] = '.';
}
}
}
private static boolean isValidPlacement(char[][] board, int row, int col) {
// Check that no queens attack horiz, vertic, diagon
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q' || (col - row + i >= 0 && board[i][col - row + i] == 'Q') || (col + row - i < board.length && board[i][col + row - i] == 'Q')) {
return false;
}
}
return true;
}
private static List