N-Queens
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Constraints:
- 1 <= n <= 9
- Each queen must be placed in a unique row and column
- No two queens can be in the same diagonal
Examples:
Input: n = 4
Output: [[".Q..","...","....","...."],["...",".Q..","....","...."],["....","....",".Q..","...."],["....","....","....",".Q.."]]
Explanation: There are two solutions for n = 4: one with the queen in the first row and one with the queen in the second row.
Solutions
Backtracking
The backtracking approach is used to solve this problem. We start by initializing an empty board and then try to place a queen in each column of the current row. If it is safe to place a queen in a column, we make a recursive call to place queens in the next row. If it is not safe, we backtrack and try the next column.
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0;
i < n;
i++) {
for (int j = 0;
j < n;
j++) {
board[i][j] = '.';
}
}
backtrack(result, board, 0);
return result;
}
private void backtrack(List<List<String>> result, char[][] board, int row) {
if (row == board.length) {
List<String> solution = new ArrayList<>();
for (char[] chars : board) {
solution.add(new String(chars));
}
result.add(solution);
return;
}
for (int col = 0;
col < board.length;
col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
backtrack(result, board, row + 1);
board[row][col] = '.';
}
}
}
private boolean isValid(char[][] board, int row, int col) {
for (int i = 0;
i < row;
i++) {
for (int j = 0;
j < board.length;
j++) {
if (board[i][j] == 'Q' && (j == col || Math.abs(j - col) == row - i)) {
return false;
}
}
}
return true;
}Follow-up:
Solve the problem for a rectangular board instead of a square board.
