Extended ensemble Monte Carlo approach to hardly relaxing problems Original Research Article

A set of methods based on an idea of extended ensemble has been proposed for simulating hardly relaxing systems such as spin glasses. The multicanonical method, simulated tempering and exchange Monte Carlo are typical examples of this family. We briefly review extended ensemble Monte Carlo methods, particularly focusing on the exchange Monte Carlo method. Using the method, we study the number of solutions of the N queens problem which is a kind of constraint-satisfaction problem. This problem is a typical example of hardly relaxing problems because there exist numerous solutions and energy barriers between them. Our numerical result supports the conjecture that the number of solutions is proportional to NN in the large N limit. We also discuss the thermodynamic properties of the N queens problem at finite temperatures introduced artificially.