Skip to content

N-Queens 8×8

The problem

N-Queens places N queens on an N×N chessboard so that no two attack each other: no two share a row, a column or a diagonal. Bezzel (1848) posed it for 8 queens on the usual board, and this is that board. It has 92 solutions, 12 of them distinct up to rotations and reflections. Every board from 4×4 up has at least one (Bell and Stevens, 2009, Discrete Mathematics 309(1): 1-31).

On a 4×4 board, queens in rows 1 to 4 at columns 2, 4, 1 and 3 are a solution: no two share a column, and no two are on a common diagonal.

The same search solves the 16×16, 32×32, 64×64 and 128×128 boards.

What makes it hard

On 8×8, not much. There are 4,426,165,368 ways to put 8 queens on 64 squares, but with one queen per row and column (below), there are 8! = 40,320 placements, and 92 of them are solutions: 1 in 438. A random placement has 5 attacking pairs on average.

The difficulty grows with N. The placements grow as N!, and the solutions nearly as fast: for large N, there are about (0.143 N)ᴺ (Simkin, 2021, arXiv:2107.13460). Nobody has counted them beyond 27×27. With the settings below:

Board Placements (N!) Solutions Attacking pairs of a random placement Median evaluations to a solution
8×8 40,320 92 5 100
16×16 2.1 × 10¹³ 14,772,512 10.3 729
32×32 2.6 × 10³⁵ not counted 21 2,450
64×64 1.3 × 10⁸⁹ not counted 42.3 7,110
128×128 3.9 × 10²¹⁵ not counted 85 16,590

A random placement has (2N − 1)/3 attacking pairs on average. The evaluations are the median over seeds 1 to 100, and each takes time in proportion to N.

Representation

A Permutation of 0 to 7: entry r is the column of the queen in row r. Each row then has one queen, and each column has one, since a permutation repeats no value. Row and column conflicts are impossible, and only the diagonals are left.

The fitness counts the pairs of queens on a common diagonal, to minimize. A diagonal with k queens adds k(k − 1)/2 pairs. There are 15 diagonals in each direction. The Python version counts them with numpy, a generation at a time.

Algorithm

A (μ+λ) genetic algorithm without crossover:

  • 20 parents, chosen by tournaments of size 2, make 20 children;
  • each child is its parent with two entries swapped (swap mutation): two queens trade columns, and the genome stays a permutation;
  • parents and children compete, and the best 20 survive.

A crossover can't take each row's column from either parent freely: the child would repeat columns. genoxide's guide suggests (μ+λ) for mutation-only searches and plateaus. The best placement always survives. On ties, genoxide keeps the children rather than the parents, so the population drifts across plateaus. The run stops at 0 conflicts, or after 50,000 generations.

Output

The first line gives the conflicts of the best placement, and the generations and evaluations it took. The second gives the columns: for each row from the first, the column of its queen, with rows and columns numbered from 0. Every number from 0 to 7 appears once.

The project page plays this run back.

Good results

The optimum is 0 conflicts. The run reaches it after 4 generations and 100 evaluations. Over seeds 1 to 100, every run reached it, after 100 evaluations at the median and at most 474; over seeds 1 to 1,000, every run too, after at most 1,214.

Reference: Bezzel, M. (1848). Zwei Schachfragen. Schachzeitung der Berliner Schachgesellschaft 3: 363 (signed 'Schachfreund').

Known optimum: 0 (conflicts)

Source: examples/n_queens_8

Interactive run: tachsin.gr/projects/genoxide/examples/n-queens-8

cargo run --release --example n_queens_8

//! N-Queens: place N queens on an N×N board so that no two attack each other.
//!
//! A permutation genome puts one queen in each row and each column (queen `row` is in column
//! `order[row]`), so only the diagonals can conflict. Permutations have no position-wise
//! crossover, so this uses (μ+λ) with swap mutation only.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example n_queens_8
//! ```

mod trace;

use genoxide::prelude::*;

const N: usize = 8;

// the number of pairs of queens on the same diagonal
fn conflicts(order: &Order) -> f64 {
    let mut diagonals = [0usize; 2 * N];
    let mut anti_diagonals = [0usize; 2 * N];
    for (row, &column) in order.iter().enumerate() {
        diagonals[row + N - column] += 1;
        anti_diagonals[row + column] += 1;
    }
    let pairs = |count: &usize| count * count.saturating_sub(1) / 2;
    (diagonals.iter().map(pairs).sum::<usize>() + anti_diagonals.iter().map(pairs).sum::<usize>())
        as f64
}

fn main() -> Result<()> {
    let ga = Ga::builder(Permutation::new(N)?)
        .population_size(20)
        .select(Tournament::new(2)?)
        .crossover(NoCrossover)
        .mutate(SwapMutation::new())
        .scheme(Scheme::MuPlusLambda { lambda: 20 })
        .minimize()
        .seed(1)
        .build()?;

    // with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
    let mut trace = trace::Trace::from_env();
    let outcome = Engine::new(ga, conflicts)
        .stop_when(Stop::target(0.0).or(Stop::generations(50_000)))
        .on_generation(|snapshot| trace.record(snapshot))
        .run()?;

    println!(
        "{} conflicts after {} generations and {} evaluations",
        outcome.best_fitness(),
        outcome.generations(),
        outcome.evaluations()
    );
    println!("columns {:?}", &outcome.best_genome()[..]);
    trace.write();
    Ok(())
}

python examples/n_queens_8/main.py

"""N-Queens: place N queens on an N×N board so that no two attack each other.

A permutation genome puts one queen in each row and each column (queen ``row`` is in column
``order[row]``), so only the diagonals can conflict. Permutations have no position-wise crossover,
so this uses (μ+λ) with swap mutation only. The fitness function takes a generation at a time.

With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.

    python examples/n_queens_8/main.py
"""

import numpy as np

import genoxide as gx

from trace import Trace

N = 8
ROWS = np.arange(N)


def conflicts(orders):
    """The number of pairs of queens on the same diagonal, for a genome per row."""
    # a separate range of 2N counters for each genome
    offsets = 2 * N * np.arange(len(orders))[:, None]
    pairs = 0
    for diagonal in (ROWS + N - orders, ROWS + orders):
        counts = np.bincount((diagonal + offsets).ravel(), minlength=2 * N * len(orders))
        pairs = pairs + (counts * (counts - 1) // 2).reshape(len(orders), 2 * N).sum(axis=1)
    return pairs


ga = gx.Ga(
    gx.Permutation(N),
    population_size=20,
    select=gx.Tournament(2),
    crossover=gx.NoCrossover(),
    mutation=gx.SwapMutation(),
    scheme=gx.MuPlusLambda(20),
    objective="minimize",
    seed=1,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(N)
result = ga.run(
    conflicts, batch=True, target=0, generations=50_000, on_generation=trace.on_generation
)

print(
    f"{result.best_fitness:.0f} conflicts after {result.generations} generations and "
    f"{result.evaluations} evaluations"
)
print(f"columns {result.best_genome.tolist()}")
trace.write()

What it prints, from a seeded run:

0 conflicts after 4 generations and 100 evaluations
columns [5, 2, 0, 6, 4, 7, 1, 3]