Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations

Abstract

We apply Monte Carlo simulations to count the numbers of solutions of two well-known combinatorial problems: the N-queens problem and Latin square problem. The original system is first converted to a general thermodynamic system, from which the number of solutions of the original system is obtained by using the method of computing the partition function. Collective moves are used to further accelerate sampling: swap moves are used in the N-queens problem and a cluster algorithm is developed for the Latin squares. The method can handle systems of $10^4$ degrees of freedom with more than $10^{1}0000$ solutions. We also observe a distinct finite size effect of the Latin square system: its heat capacity gradually develops a second maximum as the size increases.

10 pages, 4 figures

References in corpus (8)

• An efficient, multiple range random walk algorithm to calculate the density of states
• Simulated Tempering: A New Monte Carlo Scheme
• Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
• Residual Entropy of Ordinary Ice from Multicanonical Simulations
• Simulation via Direct Computation of Partition Functions
• Number of Magic Squares From Parallel Tempering Monte Carlo
• Wang-Landau/Multibondic Cluster Simulations for Second-Order Phase Transitions
• Entropy-based analysis of the number partitioning problem

Cited by in corpus (5)

• Multicanonical MCMC for Sampling Rare Events
• Enhanced sampling in generalized ensemble with large gap of sampling parameter: case study in temperature space random walk
• Thermodynamic Characterization of Synchronization-Optimized Oscillator-Networks
• Computing Tighter Bounds on the $n$-Queens Constant via Newton's Method
• A lower bound for the $n$-queens problem