Skip to content

N-Queens 64×64

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. The 8×8 board has 92 solutions, and every board from 4×4 up has at least one (Bell and Stevens, 2009, Discrete Mathematics 309(1): 1-31). Here N = 64.

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 8×8, 16×16, 32×32 and 128×128 boards.

What makes it hard

The number of placements is huge: 64 queens on 4,096 squares. Even with one queen per row and column, there are 64! ≈ 1.3 × 10⁸⁹ placements. A random one has 42.3 attacking pairs on average.

The fitness is a count of conflicts, a small integer, and many placements share it. A swap moves two queens, which can fix one diagonal and break another. The search crosses plateaus of equal fitness on its way to 0.

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 63: 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 127 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 63 appears once.

The project page plays this run back.

Good results

The optimum is 0 conflicts. The run reaches it after 291 generations and 5,840 evaluations. Over seeds 1 to 100, every run reached it, after 7,110 evaluations at the median and at most 13,618; over seeds 1 to 1,000, every run too, after at most 18,339.

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

Known optimum: 0 (conflicts)

Source: examples/n_queens

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

cargo run --release --example n_queens

//! 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
//! ```

mod trace;

use genoxide::prelude::*;

const N: usize = 64;

// 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/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/main.py
"""

import numpy as np

import genoxide as gx

from trace import Trace

N = 64
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 291 generations and 5840 evaluations
columns [38, 44, 26, 8, 50, 27, 45, 32, 40, 17, 24, 51, 11, 61, 6, 15, 37, 2, 59, 12, 7, 55, 42, 36, 20, 16, 49, 56, 58, 39, 10, 48, 4, 60, 1, 63, 30, 35, 9, 21, 18, 14, 31, 52, 25, 47, 43, 54, 34, 3, 13, 62, 53, 28, 57, 23, 0, 33, 46, 29, 5, 19, 41, 22]