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

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

2008-08-28

arxiv.org/abs/0808.4003v1

Physics

Condensed Matter

Statistical Mechanics

10 pages, 4 figures

Scientific paper

10.1103/PhysRevE.79.016703

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^10000$ 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.

Affiliated with

Also associated with

No associations

Rating

Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541845