Balancing Time, Memory, and Accuracy: Algorithmic Insights into the N-Queens Challenge

The N-Queens problem remains a benchmark for evaluating optimization strategies in artificial intelligence due to its combinatorial complexity. This study investigates the performance of four algorithmic approaches—Exhaustive Search (Depth-First Search with Backtracking), Greedy Search (Hill Climbing), Simulated Annealing, and Genetic Algorithm—on varying board sizes (N = 10, 30, 50, 100, 200). The aim is to assess each method's ability to find conflict-free queen placements, and to evaluate their computational efficiency, scalability, and memory usage.
Each algorithm was implemented in Python and tested under identical hardware settings. We designed specific parameter tuning strategies for metaheuristic methods, including cooling schedules for Simulated Annealing and crossover/mutation rates for Genetic Algorithms. Experiments revealed that Exhaustive Search is suitable only for small boards (N ≤ 10), while Greedy Search performs effectively up to N = 50 but struggles with local optima on larger boards. Simulated Annealing offered the best trade-off between time and memory, successfully solving instances up to N = 100. Genetic Algorithm also scaled to N = 100 but with significantly higher memory demands and runtime.
These findings demonstrate that no single algorithm excels universally, highlighting the need for hybrid strategies and parameter optimization to extend scalability. This comparative analysis contributes to understanding algorithm behavior under combinatorial constraints and supports the development of more adaptive optimization techniques for complex real-world problems.