N Queens
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: N Queens * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: NQueens * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * The N-queens puzzle is the problem of placing N queens on an N×N chessboard such that * no two queens attack each other. * * Rules: * - A queen attacks other pieces on the same row, same column, and same diagonals. * - We must place exactly one queen per row. * * Task: * Given an integer A (denoting N), return all distinct solutions to the N-queens puzzle. * - Each solution is a 2D grid of strings where 'Q' represents a queen and '.' is an empty space. * - The final list of solutions should be sorted in REVERSE lexicographical order. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let board[row][col] be the grid. * We attempt to place a queen in 'row' from 0 to N-1. * * Validity Check (O(1) approach): * Instead of scanning the board to check if a position (r, c) is safe, we use 3 sets: * 1. Columns: Tracks if column 'c' is occupied. * 2. Main Diagonals: For any cell (r, c), (r - c) is constant along the main diagonal. * 3. Anti-Diagonals: For any cell (r, c), (r + c) is constant along the anti-diagonal. * * Backtracking Algorithm: * 1. Start at row 0. * 2. Try placing a queen in columns 0 to N-1. * 3. If valid (col, r-c, and r+c not occupied): * - Mark these as occupied. * - Recurse to row + 1. * - Backtrack: Unmark them. * 4. Base Case: If row == N, we successfully placed N queens. Add configuration to results. * * Ordering Requirement: * The problem requires Reverse Lexicographical Order. * - Standard backtracking (trying cols 0 to N-1) naturally finds solutions in lexicographical * order (e.g., solution starting with column 1 is found before column 2). * - To satisfy the constraint, we can either: * a) Iterate columns from N-1 down to 0, OR * b) Collect all solutions and simply reverse the final list. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A <= 10 * * Time Complexity: * O(N!) - In the worst case, we explore permutations of column placements. * With N=10, 10! = 3.6 million, which is feasible. * The valid checks prune the search space significantly. * * Space Complexity: * O(N^2) to store the result strings, O(N) for recursion stack and tracking sets. * * --------------------- * 4. Input / Output Format * --------------------- * Input: Integer A. * Output: ArrayList of ArrayLists of Strings (representing the boards). * * --------------------- * 5. Examples * --------------------- * Input: A = 4 * * Standard DFS finds: * Sol 1: [..Q., Q..., ...Q, .Q..] (Cols: 2, 0, 3, 1) -> Start string "..Q." * Sol 2: [.Q.., ...Q, Q..., ..Q.] (Cols: 1, 3, 0, 2) -> Start string ".Q.." * * Comparison: * ".Q.." starts with dot, Q... * "..Q." starts with dot, dot... * Lexicographically, "..Q." < ".Q..". * * Requirement: Reverse Order (Descending). * Output should be: [Sol 2, Sol 1]. * * ============================================================================================ */ public class NQueens { public int solve(int A) { // TODO: Implement solution return 0; }
public ArrayList<ArrayList<String>> solveNQueens(int i) {
return new ArrayList<>();
}
}