🏠 Home

👑 The 8 Queens Problem

Place 8 queens on a chessboard so that none can attack another

/ 22
👑 The Challenge
Topics: combinatorics, backtracking, constraints, systematic search
A chess queen can attack any square in the same row, column, or diagonal — as far as it likes.

Challenge: Place 8 queens on an 8×8 chessboard so that no two queens attack each other.

Every row and every column must contain exactly one queen. How many solutions exist?

Interactive board — click to place queens (click again to remove):

Click squares to place queens
For n queens on an n×n board, each queen must be in a different row AND different column.

This means the column positions of queens form a permutation of {1, 2, …, n}.

Additionally, no two queens can share a diagonal: |row₁ − row₂| ≠ |col₁ − col₂|.

Brute force: 8! = 40,320 permutations to check. With diagonal pruning, the real number of solutions is just 92.
Board size nSolutions
1×11
2×20
3×30
4×42
5×510
6×64
7×740
8×892
📝 Questions
1
A queen is placed at row 3, column 5. List all the constraints imposed: which rows, columns, and diagonals are now blocked? 3 marks
2
On a 4×4 board, one solution has queens at columns (2, 4, 1, 3) for rows 1–4. Verify this is valid by checking no two queens share a row, column, or diagonal. 3 marks
3
Why must each row and each column contain exactly one queen in a valid solution? 2 marks
4
If queen positions are represented as a permutation of columns, how many permutations of {1,2,3,4,5,6,7,8} exist? This is the maximum number of arrangements to check before applying diagonal constraints. 2 marks
5
The 8×8 board has 92 solutions. But many are rotations or reflections of each other. How many are fundamentally distinct (not related by rotation/reflection)? 2 marks
6
Using the interactive board, find one valid solution for the 8×8 board and write down the queen positions as a list (row: column). 4 marks
7
Extension: Describe a backtracking algorithm to solve the n-queens problem. How does pruning reduce the search space significantly? 6 marks

Answer Key

👑 8 Queens Problem

1.Row 3 blocked entirely. Column 5 blocked entirely. Diagonals: all squares (r,c) where |r−3|=|c−5| are blocked — i.e. both main diagonals through (3,5).
2.Columns: 2,4,1,3 — all distinct ✓. Diagonals: |1−2|=1≠|2−4|=2 ✓; |1−3|=2≠|2−1|=1 ✓; |1−4|=3≠|2−3|=1 ✓; |2−3|=1≠|4−1|=3 ✓; |2−4|=2≠|4−3|=1 ✓; |3−4|=1≠|1−3|=2 ✓. Valid solution.
3.A queen attacks its entire row and column. Placing two queens in the same row or column would make them attack each other immediately — so each must occupy a unique row and a unique column.
4.8! = 40,320 permutations.
5.12 fundamentally distinct solutions (92 ÷ 8 symmetries, accounting for reflections and rotations; one solution is symmetric so the exact count is 12).
6.Accept any valid 8×8 arrangement. One example: rows 1–8 at columns 1,5,8,6,3,7,2,4.
7.Backtracking: place a queen in row 1, try each column. For row 2, try each column that doesn't conflict with row 1's queen (row, col, diagonal checks). Recurse. If no valid column exists, backtrack to previous row and try the next column. Pruning: reject any column immediately if it shares a column or diagonal with an already-placed queen, dramatically reducing branches explored.

Answer Key

8 Queens Problem

1.Row 3, column 5, and both diagonals through (3,5) blocked.
2.All column and diagonal checks pass ✓.
3.Shared row or column = immediate attack.
4.8! = 40,320.
5.12 fundamentally distinct solutions.
6.Accept any valid arrangement, e.g. cols 1,5,8,6,3,7,2,4.
7.Place row by row; prune any column conflicting with placed queens; backtrack if stuck.
fractionrush.com  ·  The 8 Queens Problem  ·  92 solutions await!