Font Size: 

Over the last decade, Sudoku, a combinatorial number-placement puzzle,
has become a favorite pastimes of many all around the world. Recently it
is shown that this concept has many mathematical and computational relations
and applications. In this
puzzle, the task is to complete a partially filled 9 by 9 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 3 by 3
blocks. Sudoku squares can be considered a subclass of the
well-studied class of Latin squares.
Actually a Sudoku square
of order $n=k^2$ is a Latin square of order $n$ such that every
element in     $[n]=\{1,\ldots,n\}$ appears exactly once in each block.
A partial Sudoku square $P$ is a {\sf defining set} for a Sudoku square $S$ if
$S$ is the unique Sudoku square that is an extension of $P$.
A central problem is to determine the size of the smallest defining
set for Sudoku squares of order $n$. For $n=9$ (regular Sudoku)
extensive computer search showed that this number is 17 (McGuire et al, 2014), but the
asymptotics of this value is unknown. For Latin squares, this number
is conjectured to be $\lfloor n^2/4\rfloor$ (Mahmoodian 1995, Van Rees and Bates 1999).
A construction based on
back-circulant Latin squares shows that this number is at most
$\lfloor n^2/4\rfloor$, but the best proven lower bound is just
slightly superlinear. Also, the $\lfloor n^2/4\rfloor$ conjecture is
proved if ``defining set'' is replaced by a more strict notion called ``forcing set''.

For Sudoku
squares, we show that the same construction (with a permutation on the
rows of the matrix) works, giving an upper bound of $\lfloor
n^2/4\rfloor$. We also show that the size of the smallest forcing set
for Sudoku squares of order $n$ is at least $\Theta(n^2)$. Our
conjecture is that the size of the smallest defining set for Sudoku
squares of order $n$ is also $\Theta(n^2)$. Finally, we discuss open problems
related to Sudoku squares, their defining sets, and the computational complexity
of Sudoku completion.

computation, algorithm, analysis,