Skip to content

N-Queens 128×128

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. Every board from 4×4 up has at least one solution (Bell and Stevens, 2009, Discrete Mathematics 309(1): 1-31). Here N = 128.

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 64×64 boards.

What makes it hard

Even with one queen per row and column (below), there are 128! ≈ 3.9 × 10²¹⁵ placements. A random one has 85 attacking pairs on average, and a swap moves only two of the 128 queens.

The fitness is a count of conflicts, a small integer, and many placements share it. A swap 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. Each doubling of N multiplies them by 2.3 to 7, less for the larger boards. Large boards are easier than their size suggests: Minton, Johnston, Philips and Laird (1992, Artificial Intelligence 58(1-3): 161-205) solved a million queens by repairing conflicts one queen at a time.

Representation

A Permutation of 0 to 127: 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 255 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 127 appears once.

The project page plays this run back.

Good results

The optimum is 0 conflicts. The run reaches it after 821 generations and 16,440 evaluations. Over seeds 1 to 100, every run reached it, after 16,590 evaluations at the median and at most 37,600; over seeds 1 to 1,000, every run too, after at most 37,920.

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

Known optimum: 0 (conflicts)

Source: examples/n_queens_128

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

cargo run --release --example n_queens_128

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

mod trace;

use genoxide::prelude::*;

const N: usize = 128;

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

import numpy as np

import genoxide as gx

from trace import Trace

N = 128
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 821 generations and 16440 evaluations
columns [102, 93, 50, 10, 79, 95, 25, 21, 64, 9, 49, 104, 29, 57, 84, 23, 123, 20, 42, 119, 92, 27, 62, 78, 0, 67, 7, 81, 1, 105, 34, 5, 100, 91, 12, 19, 73, 26, 124, 106, 15, 70, 36, 45, 35, 22, 58, 112, 28, 99, 6, 72, 17, 110, 41, 66, 108, 98, 96, 90, 83, 122, 44, 56, 127, 114, 54, 101, 69, 89, 60, 2, 115, 16, 59, 126, 94, 63, 88, 8, 13, 117, 107, 52, 47, 120, 85, 39, 3, 111, 116, 121, 18, 125, 24, 30, 46, 31, 43, 97, 51, 55, 48, 82, 71, 76, 38, 65, 14, 75, 4, 103, 74, 33, 53, 37, 86, 40, 113, 61, 77, 32, 118, 87, 68, 11, 109, 80]