N-Queens Backtracking · Design and Analysis of Algorithms

N-Queens Backtracking

CSC-325 · Semester V · Design and Analysis of 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

Watch backtracking place N queens on an N x N board, retreating whenever a placement conflicts with earlier queens.

Theory & concepts

The N-queens problem asks for a placement of N queens on an N x N chessboard such that no two queens attack each other. Since queens attack along rows, columns and both diagonals, a placement is valid only if every square shares a row, column or diagonal with no other queen.

Rendering diagram…

Backtracking search for the N-Queens board

Backtracking places queens one row at a time. Each placement is checked for conflicts with the already placed queens; if a conflict appears, the algorithm backtracks to the previous row and tries the next column. The recursion either finds all solutions or exhausts the search space.

Prerequisites

Lesson: Backtracking
Lesson: Recursion
Lesson: Constraint satisfaction

Instructions

1Choose the board size N (try 4, then 8).
2Run the solver and watch queens placed row by row.
3Observe the conflicts: when a column or diagonal is attacked, the queen moves on.
4Watch the backtracking step when no column works in a row.
5Count how many complete solutions the solver finds.

Tasks

Spot a conflict
Given a partial board, find all attacked squares in the next row.
Explain backtracking
Describe what happens when every column in a row conflicts.
Try N = 4
Verify the two distinct solutions for a 4 x 4 board.

Self-check

Every completed board is a valid non-attacking placement.
The student can identify row, column and diagonal conflicts.
The student can explain the backtrack step.
The student can state the worst-case exponential complexity.

Environment

board size selectorconflict highlightingstep and pausesolution counter