  Gauss proposed the problem of how to enumerate the number of solutions for
placing $N$ queens on an $N\times N$ chess board, so no two queens attack each
other. The N-queen problem is a classic problem in combinatorics. We describe a
variety of Monte Carlo (MC) methods for counting the number of solutions. In
particular, we propose a quantile re-ordering based on the Lorenz curve of a
sum that is related to counting the number of solutions. We show his approach
leads to an efficient polynomial-time solution. Other MC methods include
vertical likelihood Monte Carlo, importance sampling, slice sampling, simulated
annealing, energy-level sampling, and nested-sampling. Sampling binary matrices
that identify the locations of the queens on the board can be done with a
Swendsen-Wang style algorithm. Our Monte Carlo approach counts the number of
solutions in polynomial time.
