×

zbMATH — the first resource for mathematics

Random Latin squares and Sudoku designs generation. (English) Zbl 1348.62227
Summary: Uniform random generation of Latin squares is a classical problem. In this paper we prove that both Latin squares and Sudoku designs are maximum cliques of properly defined graphs. We have developed a simple algorithm for uniform random sampling of Latin squares and Sudoku designs. The corresponding SAS code is available in the supplementary material.

MSC:
62K15 Factorial statistical designs
Software:
Cliquer; SAS; igraph
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Bailey, R. A., Cameron, P. J. and Connelly, R. (2008). Sudoku, gerechte designs, resolutions, affine space, spreads, reguli, and Hamming codes., Amer. Math. Monthly 115 383-404. · Zbl 1149.05010
[2] Behrens, W. (1956). Feldversuchsanordnungen mit verbessertem Ausgleich der Bodenunterschiede., Zeitschrift für Landwirtschaftliches Versuchsund Untersuchungswesen 2 176-193.
[3] Csardi, G. and Nepusz, T. (2006). The igraph software package for complex network research., InterJournal Complex Systems 1695.
[4] Dahl, G. (2009). Permutation matrices related to Sudoku., Linear Algebra and Its Applications 430 2457-2463. · Zbl 1173.05306
[5] Fontana, R. (2011). Fractions of permutations. An application to Sudoku., Journal of Statistical Planning and Inference 141 3697-3704. · Zbl 1235.62105
[6] Fontana, R. (2014). Supplement to “Random Latin squares and Sudoku designs generation”. DOI:, 10.1214/14-EJS913SUPP. · Zbl 1348.62227
[7] Jacobson, M. T. and Matthews, P. (1996). Generating uniformly distributed random Latin squares., Journal of Combinatorial Designs 4 405-437. · Zbl 0913.05027
[8] Niskanen, S. and Östergård, P. R. (2003)., Cliquer User’s Guide: Version 1.0 . Helsinki University of Technology.
[9] Shao, B., Wang, H. and Xiao, Y. (2012). Managing and mining large graphs: Systems and implementations. In, Proceedings of the 2012 International Conference on Management of Data 589-592. ACM.
[10] Yates, F. (1933). The formation of Latin squares for use in field experiments., Empire Journal of Experimental Agriculture 1 235-244.
[11] (2012). SAS/OR(R) 12.1 User’s Guide: Network Optimization, Algorithms.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.