CSP N-Queens

This repository contains several constraint satisfaction problem (CSP) solvers for the N-Queens puzzle. Each solver reports timing and search statistics so you can compare their strengths on different board sizes.

Implemented approaches

• Naive enumeration (naive_enumeration.py) – depth-first enumeration of every possible placement. Only practical for very small boards and automatically skipped when N > 10.
• Backtracking + Forward Checking (backtracking_forward_checking.py) – classic backtracking search with MRV variable ordering and forward checking to prune domains eagerly.
• Backtracking + AC-3 (backtracking_ac3.py) – same backbone search as above, but enforces arc consistency with AC-3 between every assignment, making it more effective on moderate board sizes (N ≤ 24 by default).
• Min-conflicts local search (min_conflicts.py) – stochastic repair heuristic that scales well to large boards and either returns a solution or reports that it exhausted the configured step budget.

Supporting utilities live in csp_utils.py, and nQueensCSPs.py orchestrates running the solvers, printing their metrics, and formatting a sample solution board.

Requirements

• Python 3.8+ (no third-party packages needed)

Usage

Run the driver script and pass any number of board sizes (defaults to 8 if you omit arguments):

python nQueensCSPs.py 4 8 16 32

For each requested N, the script:

1. Prints which algorithms will run (skipping the ones that would be painfully slow for the chosen size).
2. Runs the solver and gathers runtime, explored nodes, checked assignments, and any algorithm-specific counters (consistency checks, AC-3 checks, etc.).
3. Displays a sample solution grid when one is found.

Example snippet:

N-Queens with N = 8
----------------------------------------
[12:00:01] Running Naive enumeration...
Method: Naive enumeration
N = 8
Runtime: 0.121435 seconds
Explored nodes: 256
...

Feel free to tweak the thresholds inside nQueensCSPs.py if you would like to force a particular algorithm to run on larger (or smaller) board sizes, or adjust the max_steps parameter inside min_conflicts.py to balance runtime versus success probability.