The Sudoku completion problem with rectangular hole pattern is NP-complete

DOI10.1016/J.DISC.2012.07.022MaRDI QIDQ713152zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ramon Bejar, Cesar Fernandez, Carles Mateu, Magda Valls

Publication date 26 October 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2012.07.022

zbMATH Keywords

NP-completequasigroupLatin square completionSudoku completion

Mathematics Subject Classification ID

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

Recommendations

• On completing latin squares
• The complexity of completing partial Latin squares
• Sudoku rectangle completion (extended abstract)
• scientific article; zbMATH DE number 3873343
• scientific article; zbMATH DE number 5823702

Cites work

• Balance and filtering in structured satisfiable problems. (Preliminary report)
• Chessboard squares
• Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete
• Generating uniformly distributed random latin squares
• On completing latin squares
• Sudoku, Gerechte Designs, Resolutions, Affine Space, Spreads, Reguli, and Hamming Codes

Cited in

(5)

• A sublinear Sudoku solution in cP systems and its formal verification
• On completing latin squares
• Packing Latin squares by BCL algebras
• scientific article; zbMATH DE number 5823702 (Why is no real title available?)
• Sudoku rectangle completion (extended abstract)

This page was built for publication: The Sudoku completion problem with rectangular hole pattern is NP-complete

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