DSA 450 Notes

Problem Statement

The N-Queens puzzle is the problem of placing N chess queens on an N×N chessboard so 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 where 'Q' represents a queen and '.' represents an empty space.

Example:

Input: n = 4
Output: [
  [".Q..",
   "...Q",
   "Q...",
   "..Q."],
  
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."]
]

Explanation: There are 2 distinct solutions for 4-Queens problem.

Approach 1: Brute Force (Check All Positions)

Intuition

Place queens row by row and for each placement, check if it's safe by examining all previously placed queens. This involves checking the column, upper-left diagonal, and upper-right diagonal.

Algorithm

Start from the first row
Try placing a queen in each column of the current row
For each placement, check if it's safe by examining all previously placed queens
If safe, move to the next row
If all queens are placed, store the solution
Backtrack and try the next column

java

import java.util.*;

class Solution {
    public boolean isSafe(char[][] board, int row, int col, int n) {
        // Check column above
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        
        // Check upper-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        
        // Check upper-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }
    
    public void solve(int row, char[][] board, List<List<String>> result, int n) {
        // Base case: all queens placed
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) {
                solution.add(new String(r));
            }
            result.add(solution);
            return;
        }
        
        // Try placing queen in each column
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col, n)) {
                board[row][col] = 'Q';
                solve(row + 1, board, result, n);
                board[row][col] = '.';  // Backtrack
            }
        }
    }
    
    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, '.');
        solve(0, board, result, n);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n! × n) - n! arrangements, O(n) to check each
Space Complexity: O(n²) - For the board

Approach 2: Optimal (Using Hash Sets for O(1) Validation)

Intuition

Instead of checking safety by iterating through the board, use hash sets to track which columns and diagonals are occupied. This reduces the safety check from O(n) to O(1).

Algorithm

Use three sets: columns, left diagonals (row-col), right diagonals (row+col)
Before placing a queen, check if the position conflicts with any set
If safe, add to sets, place queen, and recurse
Backtrack by removing from sets

java

import java.util.*;

class Solution {
    private Set<Integer> cols = new HashSet<>();
    private Set<Integer> leftDiag = new HashSet<>();   // row - col
    private Set<Integer> rightDiag = new HashSet<>();  // row + col
    
    public void solve(int row, char[][] board, List<List<String>> result, int n) {
        // Base case: all queens placed
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) {
                solution.add(new String(r));
            }
            result.add(solution);
            return;
        }
        
        // Try placing queen in each column
        for (int col = 0; col < n; col++) {
            // Check if position is safe using sets
            if (cols.contains(col) || leftDiag.contains(row - col) || rightDiag.contains(row + col)) {
                continue;
            }
            
            // Place queen and update sets
            board[row][col] = 'Q';
            cols.add(col);
            leftDiag.add(row - col);
            rightDiag.add(row + col);
            
            solve(row + 1, board, result, n);
            
            // Backtrack
            board[row][col] = '.';
            cols.remove(col);
            leftDiag.remove(row - col);
            rightDiag.remove(row + col);
        }
    }
    
    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, '.');
        solve(0, board, result, n);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n!) - At most n choices for first row, n-1 for second, etc.
Space Complexity: O(n) - For the three sets (each can have at most n elements)

Key Takeaways

Diagonal Property: Left diagonal (row-col) and right diagonal (row+col) have constant values
Hash Set Optimization: Reduces validation from O(n) to O(1)
Row by Row: Place one queen per row, no need to check row conflicts
Symmetry: Solutions come in symmetric pairs (can use to reduce search space)
LeetCode #51: Classic backtracking problem - N-Queens
Constraint Propagation: Using sets is a form of constraint tracking

Printing all solutions in N-Queen Problem

Problem Statement

Approach 1: Brute Force (Check All Positions)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Using Hash Sets for O(1) Validation)

Intuition

Algorithm

Complexity Analysis

Key Takeaways