Stability and Ergodic Patterns in Permutation-Based Optimization: The Case of N-Queens

The N-Queens problem, a classical benchmark in permutation-based combinatorial optimization, has recently attracted renewed attention through the lens of stochastic dynamics and ergodic theory. In this paper, we model the configuration space of N-Queens as a discrete-time Markov chain, unveiling dynamic transitions between feasible and infeasible states. We introduce formal definitions of stability and p-stability to characterize the structural robustness of configurations and propose novel ergodic invariants to describe long-term behavior in the state space. These invariants serve as analytical tools to classify stability landscapes and quantify metastable phenomena. Algorithmic simulations support our theoretical framework, offering insights into convergence patterns, invariant measures, and the topological complexity of the solution space. Our findings bridge combinatorics, statistical physics, and theoretical computer science, offering a unified approach to stability analysis in constraint satisfaction problems.