Reference : Sudokus' ranks
E-prints/Working papers : First made available on ORBi
Physical, chemical, mathematical & earth Sciences : Mathematics
Sudokus' ranks
[fr] Rangs des Matrices Sudoku
Merciadri, Luca mailto [Université de Liège - ULiège > > > 1re an. bac. sc. ing., or. ing. civil]
Eastham, Chip mailto [> >]
[en] Sudoku ranks ; Latin square ; Euler's totient function
[en] A Latin square of order n^2 is a Sudoku matrix if subdividing its entries into n^2 disjoint n-by-n subblocks causes each symbol to appear once in each subblock. Symbols are taken from {1, ..., n^2}, and n^2 = 9 then corresponds to the familiar recreation.

A construction of cyclic latin squares (see Shiu, W.C. and Fang, K.T. and Ma, S. L., On the Rank of Cyclic Latin Squares, Linear and Multilinear Algebra, Vol. 40, pp. 183-188) determines their minimum rank and shows they can attain full rank. It follows that Sudoku matrices can also be full rank. The present authors initially thought that the minimum ranks of Sudoku matrices would equal the minimum ranks of cyclic latin squares of the same order, i.e. 1 + \sum_{i=1}^{s} \varphi\left((p_i)^{t_i}\right) where n=\prod_{i=1}^{s} (p_i)^{t_i} is the prime factorization (of n), and \varphi is Euler's totient function. However, a block-cyclic latin square construction is found that attains a smaller rank. For the case n^2 = 9, one gets a rank 5 matrix rather than rank 7.

Some generalizations such as taking symbols from {0, ..., n^2 -1} are discussed, and comparisons made to ranks of more general kinds of latin squares. We also discuss the possibility of finding a rank inferior to 5 for a 9*9 Sudoku matrix. (Until here, no test revealed such a possibility, but tests are not finished yet.)
Researchers ; Students
The article is not finished yet.

File(s) associated to this reference

Fulltext file(s):

Restricted access
sudoku_rank.pdfThe article is not finished yet.Author preprint109.12 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.