This code solves the eight queens puzzle using Gibbs sampling

8queens_gibbs.py

import random
import math
from typing import List, Optional

def total_conflicts(state: List[int]) -> int:
    """Count total number of attacking pairs (each pair counted once)."""
    n = len(state)
    conflicts = 0
    for i in range(n):
        for j in range(i + 1, n):
            if state[i] == state[j] or abs(state[i] - state[j]) == abs(i - j):
                conflicts += 1
    return conflicts

def conflicts_if_placed(state: List[int], col: int, row: int) -> int:
    """Count how many conflicts the queen at (row, col) would have with other columns."""
    n = len(state)
    c = 0
    for j in range(n):
        if j == col:
            continue
        rj = state[j]
        if rj == row or abs(rj - row) == abs(j - col):
            c += 1
    return c

def gibbs_8queens(
    n: int = 8,
    max_iters: int = 200000,
    beta_schedule: Optional[List[float]] = None,
    seed: Optional[int] = None,
) -> (List[int], int, bool):
    """
    Gibbs sampling solver for n-queens.
    - n: size of board (8 for classic 8-queens).
    - max_iters: maximum number of single-variable updates (not full sweeps).
    - beta_schedule: list or function giving beta for each iteration index (if None, use constant beta=1.0).
    - seed: optional RNG seed.
    Returns (state, iterations_used, success_flag).
    """
    if seed is not None:
        random.seed(seed)

    # initialize: one queen per column, random rows
    state = [random.randrange(n) for _ in range(n)]

    if beta_schedule is None:
        def beta_at(_i): return 1.0
    elif callable(beta_schedule):
        beta_at = beta_schedule
    else:
        # list provided -> cycle or clamp to last value
        def beta_at(i, sched=beta_schedule):
            if i < len(sched):
                return sched[i]
            return sched[-1]

    for it in range(max_iters):
        # pick column to update (you can also sweep columns sequentially)
        col = it % n  # sweep columns cyclically (deterministic order)
        beta = beta_at(it) if callable(beta_at) else beta_at(it)

        # compute unnormalized log-probabilities (or energies) for each possible row
        energies = []
        for r in range(n):
            c = conflicts_if_placed(state, col, r)
            energies.append(-beta * c)  # log-proportional to exp(-beta * conflicts)

        # convert log-energies to probabilities robustly
        maxE = max(energies)
        exps = [math.exp(e - maxE) for e in energies]
        total = sum(exps)
        probs = [e / total for e in exps]

        # sample a row according to probabilities
        r_choice = random.random()
        accum = 0.0
        chosen_row = 0
        for r, p in enumerate(probs):
            accum += p
            if r_choice <= accum:
                chosen_row = r
                break

        state[col] = chosen_row

        # quick success check after a full sweep (every n updates)
        if (it + 1) % n == 0:
            if total_conflicts(state) == 0:
                return state, it + 1, True

    # reached max iterations without finding a solution
    return state, max_iters, False

def print_board(state: List[int]) -> None:
    n = len(state)
    for r in range(n):
        row = ""
        for c in range(n):
            row += "Q " if state[c] == r else ". "
        print(row)
    print(f"Conflicts: {total_conflicts(state)}\n")

if __name__ == "__main__":
    # Example usage:
    n = 8
    # A simple beta schedule: start low (more exploration), gradually increase (more exploitation)
    # Here we create a list of betas for first 5000 iterations then stick to the last one.
    betas = [0.5 + 2.5 * (i / 4999) for i in range(5000)]  # from 0.5 to 3.0

    # Run several independent restarts if needed
    for attempt in range(10):
        state, iters, success = gibbs_8queens(n=n, max_iters=1400, beta_schedule=betas, seed=None)
        print(f"Attempt {attempt+1}: iterations={iters}, success={success}")
        print_board(state)
        if success:
            break

A version using the thrml library is available here