Algorithm Comparison
Nodes / Steps Explored (Log Scale)
| N | Backtracking (nodes) | Forward Checking (nodes) | Min-Conflicts (avg steps) |
|---|---|---|---|
| 4 | 8 | 5 | 3 |
| 6 | 152 | 38 | 8 |
| 8 | 876 | 210 | 12 |
| 10 | 975 | 390 | 7 |
| 12 | 3,066 | 1,100 | 14 |
| 14 | 17,756 | 5,200 | 10 |
| 16 | 542 | 189 | 9 |
| 18 | 10,094 | 3,800 | 11 |
| 20 | 55,590 | 19,800 | 15 |
Forward Checking explores ~58% fewer nodes than Backtracking but runs ~3x slower due to domain copying overhead. Min-Conflicts achieves O(n) average-case — orders of magnitude faster.
Pruning Efficiency by Depth
Nodes Explored (Log Scale) — With & Without Pruning
| Depth | Nodes (no pruning) | Nodes (with α-β) | Pruning % | Time (ms) |
|---|---|---|---|---|
| 2 | 49 | 27 | 44.9% | <1 |
| 4 | 2,401 | 440 | 81.7% | 2 |
| 6 | 117,649 | 5,217 | 95.6% | 45 |
| 8 | 5,764,801 | 45,810 | 99.2% | 380 |
Pruning effectiveness increases with depth: from 44.9% at depth 2 to 99.2% at depth 8. The deeper you search, the more you save.
Guess Distribution
Codes Solved per Guess Count (of 360 total)
| Guesses | Codes Solved | Cumulative % |
|---|---|---|
| 1 | 1 | 0.3% |
| 2 | 8 | 2.5% |
| 3 | 62 | 19.7% |
| 4 | 168 | 66.4% |
| 5 | 108 | 96.4% |
| 6 | 13 | 100% |
Average: 4.15 guesses. The first guess eliminates ~82% of candidates. By guess 3, 19.7% of codes are already cracked.
The Pruning Cost-to-Benefit Ratio
The central finding across all four problems: an algorithm's real-world efficiency depends not on theoretical complexity alone, but on the ratio between the cost of its optimization strategy and the savings that strategy produces.
Alpha-Beta Pruning
Connect 4Verdict: Always worth it — the optimization is essentially free
Forward Checking
N-QueensVerdict: Not always worth it — overhead exceeds savings at small N
Constraint Elimination
MastermindVerdict: Worth it — finite search space makes per-step cost acceptable
This cross-problem analysis sits alongside a separate research paper: “From Game-Theoretic Poker to the Collapse of Trust: Modelling Strategic Behaviour in Multi-Agent Systems” (Polygence, 2025). Where this project studies algorithms playing against known rules, the paper studies what happens when the “rules” are other agents — adaptive, strategic, potentially deceptive. The shared thread: how rational agents behave under constraint, and when their optimizations break down.
Complexity Summary
| Algorithm | Problem | Time | Space | Optimal? | Key Strength |
|---|---|---|---|---|---|
| Backtracking | N-Queens | O(n!) | O(n) | Yes (finds all) | Simplicity |
| Forward Checking | N-Queens | O(n!) | O(n²) | Yes | Early pruning |
| Min-Conflicts | N-Queens | O(n) avg | O(n) | Probabilistic | Speed |
| Minimax | Connect 4 | O(bd) | O(bd) | Yes | Optimal play |
| Alpha-Beta | Connect 4 | O(bd/2) | O(bd) | Yes | Pruned optimal |
| Constraint Elim | Mastermind | O(k·n) | O(n) | Near-optimal | Information gain |