Faangprep Logo
LoginRegister
Browse Curriculum

N-Queens

The N-Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

N-Queens Solver

Ready

See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Intuition

We place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. If we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.

Concept

Strategy:

  1. Start in the leftmost column.
  2. If all queens are placed return true.
  3. Try all rows in the current column.
  4. If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.
  5. If placing the queen in [row, column] leads to a solution then return true.
  6. If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step 3 to try other rows.
  7. If all rows have been tried and nothing worked, return false to trigger backtracking.

How it Works

  1. Define backtrack(col).
  2. Base Case: If col == N, solution found.
  3. Loop through rows row from 0 to N-1.
  4. Check if placing queen at (row, col) is safe (check row and diagonals). (Note: We check previous columns).
  5. If safe: Place queen, call backtrack(col + 1).
  6. If recursive call returns (backtracks): Remove queen and try next row.

Step-by-Step Breakdown

Example: N=4

  • Place Q at (0,0).
  • Try (1,0) - Attack. (1,1) - Attack. (1,2) - Safe. Place Q.
  • Try (2,0)...(2,3) - All attacked. Backtrack.
  • Remove Q from (1,2). Try (1,3) - Safe. Place Q.
  • ...and so on until a valid arrangement is found.

When to Use

  • Constraint satisfaction problems.
  • Scheduling problems with hard constraints.

When NOT to Use

  • When an approximate solution is sufficient (simulated annealing might be faster for large N).

How to Identify

"Place N items such that they don't conflict", "Constraint satisfaction".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep