Search space representation and analysis of the backtracking algorithm for the N-Queens problem

Abstract

The N-Queens problem is a classical constraint satisfaction problem in artificial intelligence and combinatorial optimization. Although its formulation is simple, its search space grows rapidly as the board size increases, making exhaustive search computationally inefficient. This study analyzes the N-Queens problem within the search-space framework of the Backtracking algorithm, focusing on branching expansion, constraint checking, and early pruning of infeasible configurations. Three methods are implemented and compared: permutation-based exhaustive search, conventional Backtracking, and Bitmask Backtracking. Experimental results show that conventional Backtracking reduces the search workload from 40,320 permutations to 2,057 nodes for N=8, and from 3,628,800 permutations to 35,539 nodes for N=10. In addition, Bitmask Backtracking visits the same number of nodes as conventional Backtracking but achieves approximately 2.75× and 4.14× speed-up for N=8 and N=10, respectively. These results indicate that Backtracking improves efficiency through search-space pruning, while Bitmask representation further reduces the computational cost of constraint checking. The study provides a systematic and reproducible analysis of Backtracking for understanding constraint-based search and optimization problems.