N-Queens Problem

The problem is defined by a single, global constraint: no two queens may threaten each other. This decomposes into three specific, binary constraints for any pair of queens (Qᵢ, Qⱼ) placed at positions (rowᵢ, colᵢ) and (rowⱼ, colⱼ):

• Row Constraint: rowᵢ ≠ rowⱼ (implicitly satisfied by standard formulation).
• Column Constraint: colᵢ ≠ colⱼ.
• Diagonal Constraint: |rowᵢ - rowⱼ| ≠ |colᵢ - colⱼ|. This precise formulation allows it to be modeled directly as a Constraint Satisfaction Problem (CSP) with N variables (one per column) and domains of size N (possible rows).

The naive search space is enormous, with Nᴺ possible placements. For a standard 8-queens board, this is 8⁸ = 16,777,216 arrangements. However, the effective search space for the standard CSP model (one queen per column) is N! (N factorial), as we choose a distinct row for each column. For N=8, this is 40,320 possibilities. The number of solutions grows roughly with N but is not monotonic; for example, there are 92 solutions for N=8, 724 for N=10, and 14,200 for N=12. This property makes it an excellent benchmark for measuring an algorithm's pruning efficiency.

The N-Queens problem serves as a fundamental benchmark for evaluating:

• Backtracking Search: The baseline complete search algorithm.
• Constraint Propagation: Techniques like forward checking and maintaining arc consistency (MAC) to prune domains.
• Heuristic Search: Variable and value ordering heuristics like Minimum Remaining Values (MRV) and Least Constraining Value (LCV).
• Local Search: Incomplete methods like the min-conflicts heuristic, which can solve very large N (e.g., N=1,000,000) in near-linear time by iteratively repairing a random assignment. Its structure allows clear measurement of backtracks, nodes visited, and propagation effort.

The chessboard possesses inherent symmetries that generate multiple equivalent solutions. The primary symmetries are:

• Rotational Symmetry: 90°, 180°, 270° rotations.
• Reflection Symmetry: Vertical, horizontal, and diagonal reflections. For N=8, the 92 distinct solutions reduce to just 12 fundamental solutions under these symmetries. Advanced solvers often incorporate symmetry breaking constraints (e.g., forcing the queen in the first column to be in the first half of the board) to eliminate redundant search branches, dramatically improving performance.

The core problem has inspired numerous variants that test different algorithmic capabilities:

• N-Queens Completion: Given a partial placement of k < N queens, can it be completed to a full solution? This variant is NP-Complete.
• N-Queens Optimization: Maximize the number of placed queens on an N×N board without conflict (for N where a full solution is impossible).
• Superqueens (or Amazon) Problem: Queens that also move like knights, adding a fourth constraint.
• Modular N-Queens: Queens threaten each other modulo N, often studied in number theory.
• 3D N-Queens: Queens placed in an N×N×N cube, with constraints extended through three dimensions.

While seemingly abstract, the N-Queens problem directly models real-world scheduling and configuration challenges:

• Parallel Task Scheduling: Assigning N tasks to N time slots on different processors without resource conflicts (modeled as diagonals).
• VLSI Chip Layout: Placing components so that their power planes do not interfere.
• Air Traffic Control: Scheduling runway landings with required separation times.
• Benchmarking SAT/SMT Solvers: It can be encoded into Boolean Satisfiability (SAT) or Satisfiability Modulo Theories (SMT) formulas, testing the performance of solvers like Z3 or CDCL algorithms on structured problems.

A Constraint Satisfaction Problem (CSP) is the formal framework underlying the N-Queens puzzle. It is defined by:

• A set of variables (e.g., the column position for each queen in rows 1 to N).
• A domain for each variable (e.g., {1, 2, ..., N} for column positions).
• A set of constraints that specify allowable combinations of values (e.g., no two queens share a column or diagonal). Solving a CSP means finding an assignment of values to all variables that satisfies every constraint. The N-Queens problem is a pure, binary CSP where all constraints are between pairs of variables.

Backtracking search is the foundational complete search algorithm for solving CSPs like N-Queens. It operates as a depth-first search that:

• Incrementally assigns values to variables.
• Checks constraints after each assignment.
• Backtracks (undoes the most recent assignment) upon encountering a constraint violation, then tries a new value. For N-Queens, a naive backtracker places queens row by row, backtracking when a newly placed queen conflicts with any previous queen. Its worst-case runtime is exponential, but it guarantees finding all solutions or proving none exist.

Constraint propagation is an inference technique used to prune the search space before and during search. For N-Queens, the most relevant technique is arc consistency. A constraint between two variables is arc consistent if, for every value in one variable's domain, there exists a compatible value in the other variable's domain.

• The AC-3 algorithm is used to enforce arc consistency.
• In N-Queens, propagation can eliminate column choices for future rows as soon as a queen is placed, because those columns and diagonals become invalid. This dramatically reduces the number of nodes explored in the search tree.

Heuristics guide backtracking search to be more efficient. Two critical ones are:

• Minimum Remaining Values (MRV): The 'fail-first' heuristic. Choose the variable with the fewest legal values left. In N-Queens, this might mean choosing to place the next queen in the row with the most constrained column options.
• Least Constraining Value (LCV): When choosing a value for a variable, prefer the one that rules out the fewest choices for neighboring variables. For a queen, this means placing it in the column that blocks the fewest future rows/diagonals. Combining backtracking with propagation (MAC) and these heuristics solves large N-Queens instances (N>1000) in seconds.

Local search is an incomplete, but often extremely fast, alternative to backtracking for finding a single solution. It starts with a complete but invalid assignment (e.g., all N queens on the board, some attacking) and iteratively repairs it.

• The min-conflicts heuristic is highly effective for N-Queens. At each step, it selects a queen that is involved in a conflict and moves it to the column in its row that minimizes the total number of conflicts with other queens.
• This approach can routinely solve the million-queens problem in under a minute, making it the method of choice for very large N where any single solution suffices.