Experimentation with N-Queens and Monte Carlo
Published:
If you have a chessboard, how can you place 8 queens so that none of them are attacking each other? For a board of size N, this is the N-queens problem. We could solve this directly through recursive backtracking; however, I want to see how well we could do with a pure sampling-based approach. Can we treat this “constraint satisfaction” problem as a sampling problem, where the target probability distribution is \(0\) for any boards with attacking queens, and non-zero for “satisfying” boards? For REALLY big boards, sampling-based approaches might be more efficient at finding boards that are nearly optimal.