Table of Contents
The power of solving problems by reducing them to equivalent exact cover problems lies in the fact that we just need to implement encoding and decoding functions (to translate between the two forms of a problem), then rely on an existing solver, rather than implementing the full search algorithm like in N-Queens in Python .
Encoding
The key insight is that due to how queens attack, there can be at most one queen per rank, file and (anti-)diagonal.
Placing N queens on an N by N board, we know that each rank and file must contain exactly one queen, so these will be the primary columns in the exact cover encoding.
We'll label (anti-)diagonals by their y-coordinate at x=0 and use those as secondary columns.
__ __ __ __ | f0 __ __ __ | ___ ___ ___ d0 | __ a4 __ __ __ __ __ __ | f0 __ __ __ | ___ ___ d0 ___ | __ __ a4 __ __ __ __ __ | f0 __ __ __ | ___ d0 ___ d-2 | a1 __ __ a4 r0 r0 r0 r0 | f0 __ __ __ | d0 ___ d-2 ___ | __ a1 __ __
def primary(size: int) -> set[str]: res = set() res |= {f"r{i}" for i in range(size)} res |= {f"f{i}" for i in range(size)} return res def secondary(size: int) -> set[str]: res = set() res |= {f"d{i}" for i in range(-size + 1, size)} res |= {f"a{i}" for i in range(2 * size - 1)} return res def encode_pos(x: int, y: int) -> set[str]: return { f"f{x}", f"r{y}", f"d{y - x}", f"a{y + x}" }
Decoding
In our encoding, each row contains the rank and file that we can extract to determine the positions of all queens.
def decode_row(row: set[str]) -> tuple[int, int]: mapping = {c[0]: int(c[1:]) for c in row} return (mapping["f"], mapping["r"]) def decode_solution(solution: Solution) -> list[tuple[int, int]]: return [decode_row(row) for row in solution]
Exact Cover Problem
All that's left is to create the full exact cover
Problem
by adding
a row for each square we could place a queen on and check the results.
<<init_problem>> <<encode>> <<decode>> <<svg_tile_renderer>> size = 64 p = Problem(primary(size), secondary(size)) for x in range(size): for y in range(size): p.add_row(encode_pos(x, y)) s = Solver(limit=1) solution = s.solve_single(p) queens = decode_solution(solution)
