File NQueens.h

↰ Parent directory (ADS/backtrack)

The n queens (exercise 16.5): n queens on an n x n board, no two on a row, a column or a diagonal.

Definition (ADS/backtrack/NQueens.h)

Detailed Description

A row holds exactly one queen, and so the solution is the vector Q of their columns, a permutation: n! candidates instead of 2^{n^2} placements; the backtrack prunes the columns and the two diagonals already taken, kept as masks of bits, so that a choice is checked in O( 1 ). The numbers of solutions are 1, 0, 0, 2, 10, 4, 40, 92, 352, 724 for n = 1 , … , 10.

The contracts [see File Contract.h]: 1 <= n <= 32, the solutions are admissible (checked at level 3), and board() needs a column of the board for each row. The operations are defined in NQueens.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, exercise 16.5, https://algoritmicamente.it/materiali/libro/capitoli/cap16.pdf

  1. Bell, B. Stevens, A survey of known results and research areas for n-queens, Discrete Mathematics 309(1), 1-31, 2009, doi:10.1016/j.disc.2007.12.043

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions