N-Queens

📋

Problem

Imagine you are organizing a chess tournament and need to place n queens on an n×n chessboard so that no two queens threaten each other. How can you arrange them safely?

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively. No two queens can attack each other horizontally, vertically, or diagonally.

1 ≤ n ≤ 10Output all distinct solutions in any order

Edge cases: n = 1 → [['Q']]n = 2 → [] (no solutions)n = 3 → [] (no solutions)

</>

IDE

def solveNQueens(n: int) -> list:public List<List<String>> solveNQueens(int n)vector<vector<string>> solveNQueens(int n)function solveNQueens(n)

def solveNQueens(n):
    # Write your solution here
    pass

class Solution {
    public List<List<String>> solveNQueens(int n) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<string>> solveNQueens(int n) {
    // Write your solution here
    return {};
}

function solveNQueens(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [["Q...","Q...","Q...","Q..."]]Placing multiple queens in the same column or row without pruning.✅ Add checks to ensure only one queen per row and column; prune columns already used.

Wrong: [["....","....","....","...."]]Returning empty boards or not placing any queens.✅ Ensure backtracking places queens and appends valid boards to solutions.

Wrong: [[".Q..","Q...","..Q.","...Q"]]Incorrect diagonal conflict checks allowing attacking queens.✅ Check both major and minor diagonals for conflicts before placing a queen.

Wrong: Partial or fewer solutions than expected for n=8 or n=10Greedy approach or incomplete backtracking pruning.✅ Implement full backtracking with column and diagonal pruning to explore all solutions.

Wrong: Timeout or no output for n=10Inefficient brute force without pruning or memoization.✅ Use pruning of columns and diagonals and consider bitmask optimization to reduce complexity.

✓

Test Cases

Focus on handling smallest and no-solution cases correctly.

Watch out for common algorithmic traps like greedy placement or off-by-one errors.

Optimize your solution with pruning and efficient conflict detection to handle large inputs.

t1_01basic

Input4

Expected[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

⏱ Performance - must finish in 2000ms

There are two distinct ways to place 4 queens so that none attack each other.

💡 Try placing queens row by row and check conflicts.

💡 Use backtracking with pruning columns and diagonals.

💡 Track columns and diagonals to avoid invalid placements.

Why it failed: Incorrect output: likely missing some solutions or invalid placements. Fix by ensuring backtracking explores all valid columns per row and checks diagonal conflicts properly.

✓ Correctly found all distinct solutions for n=4.

t1_02basic

Input5

Expected[["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]

⏱ Performance - must finish in 2000ms

There are 10 distinct solutions for n=5 where no two queens attack each other.

💡 Extend the backtracking approach to n=5.

💡 Check all columns and prune invalid diagonals efficiently.

💡 Use sets or arrays to track columns and diagonals for pruning.

Why it failed: Output missing solutions or includes invalid boards. Fix by correctly pruning columns and diagonals and exploring all valid placements.

✓ Correctly found all 10 distinct solutions for n=5.

t2_01edge

Input1

Expected[["Q"]]

⏱ Performance - must finish in 2000ms

Only one queen on a 1x1 board; trivial solution.

💡 Check base case when n=1.

💡 Ensure your code handles smallest board correctly.

💡 Return [['Q']] immediately or via backtracking.

Why it failed: Fails to handle n=1 base case; returns empty or incorrect. Fix by adding base case or allowing single queen placement.

✓ Correctly returns single solution for n=1.

t2_02edge

Input2

Expected[]

⏱ Performance - must finish in 2000ms

No solutions exist for n=2 as queens always attack each other.

💡 Check if your code can detect no-solution cases.

💡 Backtracking should return empty list if no valid placements.

💡 Verify pruning logic does not falsely allow invalid boards.

Why it failed: Incorrectly returns solutions for n=2 where none exist. Fix pruning and validation logic to reject all invalid boards.

✓ Correctly returns empty list for n=2.

t2_03edge

Input3

Expected[]

⏱ Performance - must finish in 2000ms

No solutions exist for n=3 as queens always attack each other.

💡 Similar to n=2, ensure no invalid boards are returned.

💡 Check diagonal and column pruning carefully.

💡 Return empty list if no valid configurations found.

Why it failed: Returns invalid or partial solutions for n=3. Fix pruning to correctly identify no valid placements.

✓ Correctly returns empty list for n=3.

t3_01corner

Input8

Expectednull

⏱ Performance - must finish in 2000ms

Classic 8-queens problem with 92 distinct solutions.

💡 Avoid greedy placement; backtracking explores all options.

💡 Use column and diagonal pruning to reduce search space.

💡 Implement full backtracking, not greedy, to find all solutions.

Why it failed: Greedy approach returns fewer than 92 solutions. Fix by implementing full backtracking with pruning instead of greedy column selection.

✓ Correctly finds all 92 solutions for n=8.

t3_02corner

Input4

Expected[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 constraints and unbounded placement of queens.

💡 Each row must have exactly one queen, no repeats.

💡 Do not place multiple queens in the same row or column.

💡 Ensure backtracking places exactly one queen per row.

Why it failed: Allows multiple queens in one row or column. Fix by enforcing one queen per row and pruning columns already used.

✓ Correctly enforces one queen per row and column.

t3_03corner

Input5

Expected[["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]

⏱ Performance - must finish in 2000ms

Test to catch off-by-one errors in indexing or recursion depth.

💡 Check loop boundaries carefully for rows and columns.

💡 Ensure recursion stops exactly at row == n.

💡 Verify indexing when placing and removing queens.

Why it failed: Off-by-one error causes missing or extra solutions. Fix loop and recursion conditions to match 0-based indexing and stop at row == n.

✓ Correctly handles indexing and recursion depth.

t4_01performance

Input10

Expectednull

⏱ Performance - must finish in 2000ms

Test with n=10 to verify backtracking with pruning completes within time limit (O(n!)).

💡 Use pruning of columns and diagonals to reduce search space.

💡 Avoid recomputing conflicts by tracking columns and diagonals.

💡 Bitmask optimization can further speed up the solution.

Why it failed: TLE due to brute force without pruning or inefficient conflict checks. Fix by implementing column and diagonal pruning or bitmask optimization.

✓ Solution runs within time limit using pruning/backtracking.

Practice

1. You are given a string containing parentheses and letters. The goal is to remove the minimum number of parentheses to make the string valid (balanced parentheses) and return all possible results. Which algorithmic approach guarantees finding all valid strings with the minimum removals efficiently?

easy

A. Greedy approach that removes invalid parentheses from left to right without backtracking

B. Dynamic Programming that counts valid substrings and reconstructs solutions

C. Breadth-First Search (BFS) that explores all strings by removing one parenthesis at a time level-by-level

D. Brute force generating all subsequences and checking validity

Solution

1. Step 1: Understand problem constraints

   The problem requires minimal removals and all valid results, so partial or greedy removal may miss some minimal solutions.

2. Step 2: Analyze BFS approach

   BFS explores all strings by removing one parenthesis at a time, level-by-level, ensuring the first valid strings found have minimal removals and all such strings are collected.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS guarantees minimal removals and completeness [OK]

Hint: Minimal removals require level-by-level BFS [OK]

Common Mistakes:

• Greedy misses some minimal solutions
• Brute force is correct but inefficient
• DP doesn't apply directly here

2. Suppose the Expression Add Operators problem is modified so that digits can be reused any number of times to form expressions (i.e., unlimited reuse of digits in order). Which of the following algorithmic changes correctly adapts the backtracking solution to handle this variant without infinite loops or incorrect results?

hard

A. Remove the index increment in recursive calls to allow reuse, but add a visited set to avoid infinite loops

B. Keep the index increment as is, but allow substring splits to wrap around to the start of the string

C. Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops

D. Allow index to reset to zero after reaching the end, but prune expressions longer than a fixed length to avoid infinite recursion

Solution

1. Step 1: Understand digit reuse impact

   Allowing reuse means the index does not always increment; digits can be chosen repeatedly, risking infinite recursion.

2. Step 2: Prevent infinite loops

   Not incrementing index requires limiting recursion depth (e.g., max length n) to avoid infinite loops while exploring repeated digits.

3. Step 3: Evaluate options

   Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops correctly limits recursion depth while allowing reuse; others either cause infinite loops or incorrect pruning.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Limiting recursion depth prevents infinite loops with reuse [OK]

Hint: Limit recursion depth when digits can be reused [OK]

Common Mistakes:

• Forgetting to limit recursion depth causes infinite loops

3. Suppose the problem is modified so that digits can be repeated any number of times (reuse allowed), and you want to generate all letter combinations of length n from the given digits. Which modification to the algorithm correctly handles this reuse scenario?

hard

A. Modify backtracking to allow choosing the same digit multiple times by not incrementing the index after each choice until length n is reached

B. Sort digits and generate combinations by picking letters only once per digit

C. Use dynamic programming to store combinations of length k and build up to length n without reuse

D. Use the same iterative queue approach but do not advance the digit index; instead, for each combination, append letters from all digits repeatedly until length n is reached

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means digits can be chosen multiple times to build combinations of length n.

2. Step 2: Identify correct approach

   Backtracking can be modified to not increment the digit index after choosing a letter, allowing reuse until length n is reached.

3. Step 3: Why other options fail

   Iterative queue approach as-is assumes fixed digit positions; DP without reuse does not handle repeated digits; sorting and picking once per digit ignores reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with flexible index handles reuse elegantly [OK]

Hint: Backtracking index controls reuse by not advancing [OK]

Common Mistakes:

• Trying to reuse digits in iterative approach without index control
• Ignoring reuse in DP or sorting

4. Suppose the problem is modified so that parentheses can be reused multiple times (e.g., you can insert removed parentheses back anywhere). Which of the following algorithmic changes correctly adapts the BFS approach to handle this variant?

hard

A. Switch to backtracking with memoization to explore insertions and removals explicitly, pruning invalid states

B. Use BFS as is, since it already explores all possible removals and insertions implicitly

C. Use a greedy approach to insert parentheses at earliest invalid positions without BFS or backtracking

D. Modify BFS to allow adding parentheses back by generating new states with insertions at every position

Solution

1. Step 1: Understand reuse of parentheses

   Allowing reuse means we can insert parentheses anywhere, greatly increasing state space and complexity.

2. Step 2: Analyze BFS suitability

   Standard BFS only removes characters; it does not handle insertions, so it cannot explore all states correctly.

3. Step 3: Identify correct approach

   Backtracking with memoization can explicitly explore insertions and removals, pruning invalid states to handle reuse properly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with memoization handles insertions and pruning [OK]

Hint: Reuse requires explicit insertion exploration, not just removal BFS [OK]

Common Mistakes:

• Assuming BFS handles insertions
• Using greedy for complex insertions
• Modifying BFS without pruning leads to explosion

5. Suppose the problem is modified so that IP address segments can be reused multiple times (i.e., segments can overlap and be repeated). Which modification to the backtracking algorithm correctly handles this variant without generating duplicates or invalid IPs?

hard

A. Remove the pruning condition on remaining characters and segments to allow overlapping segments

B. Use a memoization cache keyed by (start, segments formed) to avoid recomputing paths

C. Allow segments to be reused by resetting start index to previous segment start after each addition

D. Change the algorithm to generate all permutations of segments without pruning

Solution

1. Step 1: Understand reuse implies overlapping segments

   Allowing reuse means the same substring can be used multiple times, potentially causing repeated computations.

2. Step 2: Apply memoization to avoid duplicates

   Memoization keyed by (start, segments formed) prevents recomputing the same subproblems and avoids duplicates.

3. Step 3: Evaluate other options

   Removing pruning causes inefficiency; resetting start index breaks segment order; generating all permutations ignores validity and pruning.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization efficiently handles reuse without duplicates [OK]

Hint: Memoization avoids recomputation when segments can be reused [OK]

Common Mistakes:

• Removing pruning causes timeouts
• Resetting start index breaks segment order