Exact Sampling Algorithms for Latin Squares and Sudoku Matrices via Probabilistic Divide-and-Conquer

摘要

We provide several algorithms for the exact, uniform random sampling of Latin squares and Sudoku matrices via probabilistic divide-and-conquer (PDC). Our approach divides the sample space into smaller pieces, samples each separately, and combines them in a manner which yields an exact sample from the target distribution. We demonstrate, in particular, a version of PDC in which one of the pieces is sampled using a brute force approach, which we dub almost deterministic second half, as it is a generalization to a previous application of PDC for which one of the pieces is uniquely determined given the others.