×
Fontana, Roberto

Random Latin squares and Sudoku designs generation. (English) Zbl 1348.62227

Electron. J. Stat. 8, No. 1, 883-893 (2014).
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.

Cited in 7 Documents

MSC:

62K15 Factorial statistical designs

Keywords:

Latin squares; Sudoku designs; random generation; cliques

Software:

Cliquer; SAS; igraph
Cite Review PDF
Full Text: DOI arXiv 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 · doi:10.1016/j.laa.2008.12.023
[5] Fontana, R. (2011). Fractions of permutations. An application to Sudoku., Journal of Statistical Planning and Inference 141 3697-3704. · Zbl 1235.62105 · doi:10.1016/j.jspi.2011.06.001
[6] Fontana, R. (2014). Supplement to “Random Latin squares and Sudoku designs generation”. DOI:, 10.1214/14-EJS913SUPP. · Zbl 1348.62227 · doi:10.1214/14-EJS913
[7] Jacobson, M. T. and Matthews, P. (1996). Generating uniformly distributed random Latin squares., Journal of Combinatorial Designs 4 405-437. · Zbl 0913.05027 · doi:10.1002/(SICI)1520-6610(1996)4:6<405::AID-JCD3>3.0.CO;2-J
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.