N-Queens Backtracking · Data Structures and Algorithms

N-Queens Backtracking

CSC-211 · Semester III · Data Structures and Algorithms

advanced30 minAvailable

RecursionFunction call stack · divide & conquer

n =

active callreturnedwaiting

factorial(5)→ 120

└factorial(4)…

└factorial(3)…

└factorial(2)…

└factorial(1)…

Call stack depth (max)

0frames

Lab brief

Objective

Place N queens on an N×N board using backtracking, watching the search place queens row by row and retreat from dead ends.

Theory & concepts

The N-Queens problem asks to place N queens so that no two attack each other. The backtracking search places a queen in each row, tries every column, and only recurses when the square is safe — not in the same column, diagonal or anti-diagonal as an existing queen. When a row has no safe column, the search undoes the previous placement and tries the next column.

Rendering diagram…

N-Queens backtracking search

solve(row):
    if row == N: count++; return
    for col in 0..N-1:
        if safe(row, col):
            place queen (row, col)
            solve(row + 1)
            remove queen (row, col)   // backtrack
Safe tests: no other queen in column, diagonal or anti-diagonal.
A 4×4 board has 2 solutions; an 8×8 board has 92.

Prerequisites

Lab: Recursion — Factorial and Fibonacci
Lab: Tower of Hanoi

Instructions

1Choose the board size (start with 4 or 5).
2Watch the search place a queen in the first row and proceed downward.
3When a row has no safe column, watch the search backtrack one row.
4Follow the conflict highlight that shows why a square is rejected.
5Let the simulation find all solutions and compare the count with the known value.

Tasks

Trace a dead end
On a 4×4 board, identify a placement that forces a backtrack.
Solution count
Run for N=4 and N=8 and confirm 2 and 92 solutions respectively.
Pruning
State how the safe() check avoids exploring whole subtrees.

Self-check

Placed queens never attack each other.
The student explains the backtracking undo step.
Solution counts match the known values for small N.

Environment

board gridqueen placementconflict highlightbacktrack steppersolution counter