Heuristic and Evolutionary Strategies for the N-Queens Problem: Strengths and Trade-offs

The N-Queens problem is a classic combinatorial challenge in artificial intelligence, where the objective is to place n queens on an n×n chessboard such that no two queens threaten each other. As n increases, the search space expands factorially, demanding robust and scalable optimisation strategies. This study presents a comparative analysis of four algorithmic approaches: Depth-First Search (DFS), Hill Climbing, Simulated Annealing, and Genetic Algorithms. Each method was implemented in Python and tested across varying board sizes (n = 10, 30, 50, 100, 200) to evaluate solution accuracy, execution time, memory usage, and scalability.

DFS proved reliable for smaller instances but became computationally infeasible as n grew. Hill Climbing showed efficiency for mid-sized boards but often stagnated in local optima beyond n = 100. Simulated Annealing consistently delivered high-quality solutions with excellent time and memory efficiency across all test cases. The Genetic Algorithm, while slower and more memory-intensive, achieved solutions for all tested n values after extensive tuning of hyperparameters.

The results highlight trade-offs between deterministic and stochastic approaches, emphasizing that no single algorithm outperforms across all dimensions. Simulated Annealing emerged as the most balanced method in terms of scalability and efficiency. This work contributes a practical benchmark for researchers evaluating optimisation techniques on NP-complete problems and provides a foundation for developing hybrid or parallelised methods for large-scale constraint satisfaction challenges.