Sudoku rectangle completion (extended abstract)

DOI10.1016/J.ENDM.2015.06.101zbMATH Open1346.05025arXiv1704.08136OpenAlexW2214234028MaRDI QIDQ322367FDOQ322367

Authors: Mohammad Mahdian, E. S. Mahmoodian 

Publication date: 14 October 2016

Abstract: Over the last decade, Sudoku, a combinatorial number-placement puzzle, has become a favorite pastimes of many all around the world. In this puzzle, the task is to complete a partially filled $9imes9$ square with numbers 1 through 9, subject to the constraint that each number must appear once in each row, each column, and each of the nine $3imes3$ blocks. Sudoku squares can be considered a subclass of the well-studied class of Latin squares. In this paper, we study natural extensions of a classical result on Latin square completion to Sudoku squares. Furthermore, we use the procedure developed in the proof to obtain asymptotic bounds on the number of Sudoku squares of order $n$.

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

Recommendations

• scientific article; zbMATH DE number 5823702
• On the number of Sudoku squares
• The Sudoku completion problem with rectangular hole pattern is NP-complete
• scientific article; zbMATH DE number 5251073
• scientific article; zbMATH DE number 5178940

zbMATH Keywords

Latin squarescritical sets in Latin squaresnumber of Sudoku squaresSudoku squares

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• A course in combinatorics.
• Sudoku, Gerechte Designs, Resolutions, Affine Space, Spreads, Reguli, and Hamming Codes
• An existence theorem for latin squares
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• Title not available (Why is that?)
• List coloring of Latin and Sudoku graphs
• Critical sets for Sudoku and general graph colorings

Cited In (7)

• Analysis of a Sudoku variation using partially ordered sets and equivalence relations
• On the number of Sudoku squares
• The Sudoku completion problem with rectangular hole pattern is NP-complete
• Title not available (Why is that?)
• The linear system for Sudoku and a fractional completion threshold
• A new algorithm for enumerating all possible Sudoku squares
• On the number of \(6 \times 6\) Sudoku grids

This page was built for publication: Sudoku rectangle completion (extended abstract)

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