An analogue of Ryser's theorem for partial Sudoku squares

zbMATH Open1242.05041arXiv1107.2634MaRDI QIDQ2895331FDOQ2895331

Emil R. Vaughan, Peter J. Cameron, 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)

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).

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• Spectrum of free-form Sudoku graphs
• DIVISION SUDOKUS: INVARIANTS, ENUMERATION, AND MULTIPLE PARTITIONS
• Title not available (Why is that?)
• Hall's theorem and extending partial Latinized rectangles
• Reducing the generalised Sudoku problem to the Hamiltonian cycle problem
• Title not available (Why is that?)

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)