Solving N-Queens Problem using Exhaustive Search and a Novel Genetic Algorithm

Abstract

The N-Queen problem is an interesting and complex combinatorial problem that has proved to be challenging for mathematicians, computer scientists, and other experts for a while now. The main idea in solving a N-Queen problem is to place N queens on a N × N chessboard such that no two queens will attack each other on the board. This puzzle is a typical textbook example for evaluating algorithms and techniques for solving optimization problems, constraint solving, and backtracking problems, and has been widely studied in computer science and mathematics. It also has applications in fields such as artificial intelligence and parallel computing. Despite the fact that substantial research has been done on this matter, comparisons between exhaustive search and genetic algorithms for solving the N-Queens problem remain limited. Specifically, not much work has been done to analyze their performance across different board sizes and explore the trade-offs between accuracy and computational efficiency. This study fills this gap by examining these two methods in detail and assesses their scalability, accuracy, and computational requirements. The findings highlight that while exhaustive search always provides an exact solution, its computational cost grows rapidly with N, making it impractical for larger board sizes. On the other hand, genetic algorithms offer a faster, more scalable approach, though they sacrifice guaranteed accuracy for speed and adaptability.

Topics & Concepts