Counting solutions for the N-queens and Latin-square problems by Monte Carlo simulations

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⁴ degrees of freedom with more than 10^10 000 solutions.