Backtracking - 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 (no two share the same row, column, or diagonal). Given an integer n, return all distinct solutions to the N-queens puzzle. Each solution contains a distinct board configuration where 'Q' indicates a queen and '.' indicates an empty space.

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There are two distinct solutions to the 4-queens puzzle.

Input: n = 1
Output: [["Q"]]

We place queens one row at a time. For each row we try every column position and check whether it is safe (no conflict in column, main diagonal, or anti-diagonal). We use three boolean sets to track occupied columns and diagonals for O(1) conflict checks.

Maintain sets for occupied columns, main diagonals (row-col), and anti-diagonals (row+col).
Recursively try each column in the current row; skip if any set contains the position.
Place the queen (update sets and board array), recurse to the next row, then backtrack.
When all n rows are filled, convert the board array to a list of strings and add to results.

import java.util.*; class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); char[][] board = new char[n][n]; for (char[] row : board) Arrays.fill(row, '.'); Set<Integer> cols = new HashSet<>(); Set<Integer> diag1 = new HashSet<>(); // row - col Set<Integer> diag2 = new HashSet<>(); // row + col backtrack(board, 0, cols, diag1, diag2, result); return result; } private void backtrack(char[][] board, int row, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2, List<List<String>> result) { int n = board.length; if (row == n) { List<String> solution = new ArrayList<>(); for (char[] r : board) solution.add(new String(r)); result.add(solution); return; } for (int col = 0; col < n; col++) { if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue; board[row][col] = 'Q'; cols.add(col); diag1.add(row - col); diag2.add(row + col); backtrack(board, row + 1, cols, diag1, diag2, result); board[row][col] = '.'; cols.remove(col); diag1.remove(row - col); diag2.remove(row + col); } } }

Complexity Analysis:

Time complexity: O(n!) in the worst case (n choices for row 1, n-2 for row 2, etc.).
Space complexity: O(n^2) for the board plus O(n) for the recursion stack and sets.