Browse issues
no. 5
The linear system for Sudoku and a fractional completion threshold
Dukes, Peter J.1; Nimegeers, Kate I.1
1 University of Victoria Dept. of Mathematics and Statistics Victoria, BC V8N 5L5 (Canada)
Algebraic Combinatorics, Volume 7 (2024) no. 5, pp. 1283-1305.

We study a system of linear equations associated with Sudoku latin squares. The coefficient matrix M of the normal system has various symmetries arising from Sudoku. From this, we find the eigenvalues and eigenvectors of M, and compute a generalized inverse. Then, using linear perturbation methods, we obtain a fractional completion guarantee for sufficiently large and sparse rectangular-box Sudoku puzzles.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.375
Classification: 05B15, 05C70, 05E18
Keywords: Sudoku, latin square, coherent configuration, perturbation

Dukes, Peter J. 1; Nimegeers, Kate I. 1

1 University of Victoria Dept. of Mathematics and Statistics Victoria, BC V8N 5L5 (Canada)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2024__7_5_1283_0,
     author = {Dukes, Peter J. and Nimegeers, Kate I.},
     title = {The linear system for {Sudoku} and a fractional completion threshold},
     journal = {Algebraic Combinatorics},
     pages = {1283--1305},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {5},
     year = {2024},
     doi = {10.5802/alco.375},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.375/}
}
TY  - JOUR
AU  - Dukes, Peter J.
AU  - Nimegeers, Kate I.
TI  - The linear system for Sudoku and a fractional completion threshold
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 1283
EP  - 1305
VL  - 7
IS  - 5
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.375/
DO  - 10.5802/alco.375
LA  - en
ID  - ALCO_2024__7_5_1283_0
ER  - 
%0 Journal Article
%A Dukes, Peter J.
%A Nimegeers, Kate I.
%T The linear system for Sudoku and a fractional completion threshold
%J Algebraic Combinatorics
%D 2024
%P 1283-1305
%V 7
%N 5
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.375/
%R 10.5802/alco.375
%G en
%F ALCO_2024__7_5_1283_0
Dukes, Peter J.; Nimegeers, Kate I. The linear system for Sudoku and a fractional completion threshold. Algebraic Combinatorics, Volume 7 (2024) no. 5, pp. 1283-1305. doi : 10.5802/alco.375. https://alco.centre-mersenne.org/articles/10.5802/alco.375/

[1] Abudayah, Mohammad; Alomari, Omar; Sander, Torsten Spectrum of free-form Sudoku graphs, Open Math., Volume 16 (2018) no. 1, pp. 1445-1454 | DOI | MR | Zbl

[2] Barber, Ben; Kühn, Daniela; Lo, Allan; Osthus, Deryk; Taylor, Amelia Clique decompositions of multipartite graphs and completion of Latin squares, J. Combin. Theory Ser. A, Volume 151 (2017), pp. 146-201 | DOI | MR | Zbl

[3] Bartlett, Padraic Completions of ϵ-dense partial Latin squares, J. Combin. Des., Volume 21 (2013) no. 10, pp. 447-463 | DOI | MR | Zbl

[4] Bowditch, Flora C.; Dukes, Peter J. Fractional triangle decompositions of dense 3-partite graphs, J. Comb., Volume 10 (2019) no. 2, pp. 255-282 | DOI | MR | Zbl

[5] Chen, Hang; Cooper, Curtis Solving Sudoku: structures and strategies, Missouri J. Math. Sci., Volume 29 (2017) no. 1, pp. 12-18 | DOI | MR | Zbl

[6] Chetwynd, Amanda; Häggkvist, Roland Completing partial n×n latin squares where each row, column and symbol is used at most cn times, 1985 (Reports, Dept. of Mathematics, University of Stockholm)

[7] Daykin, David E.; Häggkvist, Roland Completion of sparse partial Latin squares, Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, pp. 127-132 | MR | Zbl

[8] Gustavsson, T. Decompositions of large graphs and digraphs with high minimum degree, Ph. D. Thesis, Stockholm University (1991)

[9] Higman, D. G. Coherent configurations. I, Rend. Sem. Mat. Univ. Padova, Volume 44 (1970), pp. 1-25 | Numdam | MR | Zbl

[10] Horn, Roger A.; Johnson, Charles R. Matrix analysis, Cambridge University Press, Cambridge, 1985, xiii+561 pages | DOI | MR

[11] Kubota, Sho; Suda, Sho; Urano, Akane Mutually orthogonal Sudoku Latin squares and their graphs, Graphs Combin., Volume 39 (2023) no. 6, Paper no. 122, 26 pages | DOI | MR | Zbl

[12] Montgomery, Richard Fractional clique decompositions of dense partite graphs, Combin. Probab. Comput., Volume 26 (2017) no. 6, pp. 911-943 | DOI | MR | Zbl

[13] Nimegeers, K.I. Pseudoku: A Sudoku Adjacency Algebra and a Fractional Completion Threshold, Masters thesis, University of Victoria (2024)

[14] Provan, J. Scott Sudoku: strategy versus structure, Amer. Math. Monthly, Volume 116 (2009) no. 8, pp. 702-707 | DOI | MR | Zbl

[15] Sander, Torsten Sudoku graphs are integral, Electron. J. Combin., Volume 16 (2009) no. 1, Paper no. 25, 7 pages | DOI | MR | Zbl

[16] The Sage Developers SageMath, the Sage Mathematics Software System (Version 9.3) (2021) https://www.sagemath.org

Cited by Sources: