An analogue of Ryser's theorem for partial Sudoku squares

MaRDI QIDQ2895331zbMATHFDO

Authors Peter J. Cameron, Emil R. Vaughan, A. J. W. Hilton

Publication date 2 July 2012

Published in JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.2634

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: In 1956 Ryser gave a necessary and sufficient condition for a partial latin rectangle to be completable to a latin square. In 1990 Hilton and Johnson showed that Ryser's condition could be reformulated in terms of Hall's Condition for partial latin squares. Thus Ryser's Theorem can be interpreted as saying that any partial latin rectangle $R$ can be completed if and only if $R$ satisfies Hall's Condition for partial latin squares. We define Hall's Condition for partial Sudoku squares and show that Hall's Condition for partial Sudoku squares gives a criterion for the completion of partial Sudoku rectangles that is both necessary and sufficient. In the particular case where $n=pq$, $p|r$, $q|s$, the result is especially simple, as we show that any $rimess$ partial $(p,q)$-Sudoku rectangle can be completed (no further condition being necessary).

Recommendations

• Hall's condition for partial Latin squares
• Completing partial Latin squares: Cropper's problem
• A note on completing Latin squares
• Hall's theorem and extending partial Latinized rectangles
• Cropper's question and Cruse's theorem about partial Latin squares

Cited in

(7)

• Ryser's theorem for \(\rho\)-Latin rectangles
• scientific article; zbMATH DE number 5251073 (Why is no real title available?)
• scientific article; zbMATH DE number 5356325 (Why is no real title available?)
• Reducing the generalised Sudoku problem to the Hamiltonian cycle problem
• Spectrum of free-form Sudoku graphs
• Division sudokus: invariants, enumeration, and multiple partitions
• Hall's theorem and extending partial Latinized rectangles

This page was built for publication: An analogue of Ryser's theorem for partial Sudoku squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2895331)