# Sudoku Rectangle Completion

Mohammad Mahdian1 Ebadollah S. Mahmoodian2 This research is partially
supported by a grant from the INSF.

###### 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 $9\times 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\times 3$ 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$.

1Google Research
Mountain View, CA, USA
2Department of Mathematical Sciences
Sharif University of Technology
Tehran, I.R. IRAN

Key Words: Sudoku squares, Latin squares, Number of Sudoku squares, Critical
sets in Latin squares.

##  1 Introduction and preliminaries

A Latin square is an $n\times n$ matrix with entries in $1,\ldots,n$ such that
each of the numbers $1$ to $n$ appears exactly once in each row and in each
column. Latin squares are heavily studied combinatorial objects that date back
to the time of Euler and probably earlier. A variant of the notion of Latin
squares has recently surfaced in the form of a number-placement puzzle called
Sudoku. In this puzzle, the task is to complete a partially filled $9\times 9$
square with numbers 1 through 9 such that in addition to the Latin square
conditions, each number appears exactly once in each of the nine $3\times 3$
blocks. This puzzle was popularized in 1986 by the Japanese puzzle company
Nikoli and became an international hit in the 2000s, although similar puzzles
have appeared in various publications around the world since late 19th
century. The emergence of this puzzle has generated a surge of interest in the
mathematical properties of Sudoku squares [7].

In this paper, we study a Sudoku rectangle completion problem similar to a
classical result of M. Hall on Latin rectangle completion. We start with the
formal definition of the main notions used in this paper. Definitions and
notations not given here may be found in standard combinatorics and graph
theory textbooks such as [2] and [13].

A Latin square of order $n$ is an $n\times n$ matrix with entries from
$[n]=\\{1,\ldots,n\\}$ that satisfies the following two conditions:

  * •

row condition: every element in $[n]$ appears at most once in each row.

  * •

column condition: every element in $[n]$ appears at most once in each column.

When $n=k^{2}$ for an integer $k$, for every $i,j\in[k]$, the $(i,j)$th block
of an $n\times n$ matrix $M$ is defined as the set of entries with coordinates
in $((i-1)k+x,(j-1)k+y)$ for $x,y\in[k]$. We say that $(i,j)$ are the
coordinates of this block. These blocks partition the set of entries in $M$
into $k^{2}$ submatrices, each of size $k\times k$ and therefore containing
$n$ entries. The $i$th row block of $M$ is the union of the blocks at
coordinates $(i,j)$ for $j\in[k]$. Similarly, the $j$th column block of $M$ is
the union of the blocks at coordinates $(i,j)$ for $i\in[k]$. A Sudoku square
of order $n=k^{2}$ is an $n\times n$ matrix that in addition to the row and
column conditions above, satisfies the following condition:

  * •

block condition: every element in $[n]$ appears at most once in each block.

A partial Latin (Sudoku) square of order $n$ is an $n\times n$ matrix with
entries from $[n]\cup\\{*\\}$ (with $*$ representing an empty entry) that
satisfies the row and column (row, column, and block) conditions. A partial
Latin (Sudoku) square $P_{2}$ is an extension of a partial Latin (Sudoku)
square $P_{1}$ if they have the same order and for every $(i,j)\in[n]^{2}$, if
$P_{1}(i,j)\neq*$, then $P_{1}(i,j)=P_{2}(i,j)$. For $m<n$, an $m\times n$
Latin (Sudoku) rectangle is an $n\times n$ partial Latin (Sudoku) square in
which all cells in the first $m$ rows are filled and all remaining cells are
empty. More generally, for every $p,q\leq n$, a $(p,q,n)$-Latin (Sudoku)
rectangle is an $n\times n$ partial Latin (Sudoku) square in which all cells
in the intersection of the first $p$ rows and the first $q$ columns are filled
and all remaining cells are empty.

For Latin rectangles there is a well-known theorem of Marshal Hall [6] that
states: Every $m\times n$ Latin rectangle can be extended to an $n\times n$
Latin square. This theorem is proved by using the classical matching theorem
of Philip Hall. A natural question is whether the similar statement holds for
Sudoku rectangles. In this paper, we study this question, and will show that,
perhaps surprisingly, the answer depends on the value of $m$.

For $n=9$ (the regular Sudoku), this question was answered by Kanaana and
Ravikumar [8]. They showed that for all values of $m$ except $m=5$, an
$m\times 9$ Sudoku rectangle can always be completed to a Sudoku square. For
$m=5$, this is not always possible. For example, see the $5\times 9$ Sudoku
rectangle in Figure 1. Note that none of the numbers $1,\ldots,9$ can be
placed in the square marked with a star.

1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 8 3 2 5 6 1 9 4 7 9 6 5
8 4 7 2 3 1 $\star$

Figure 1: A $5\times 9$ Sudoku rectangle with no valid completion

For general $n$, the only previous result on completability of Sudoku
rectangle is the following theorem proved by Kanaana and Ravikumar [8].

######  Theorem A.

([8]) Assume $n=k^{2}$ and $n-k\leq m<n$. Then every $m\times n$ Sudoku
rectangle can be completed to a Sudoku square.

In this paper, we prove two more sufficient conditions for $m$, under which
every $m\times n$ Sudoku rectangle is completable to an $n\times n$ Sudoku
square (Section 2). These results are proved using a two-stage procedure for
completing a Sudoku rectangle, where generalized matching and bipartite graph
edge coloring is used within the two stages. We will show in Section 3 that
the union of these three conditions is a full characterization of the values
of $m$ for which every $m\times n$ Sudoku rectangle is completable. An
important ingredient of this proof is a constructive lemma that shows how to
generalize a non-completable $m\times k$ Sudoku rectangle to a non-completable
$m\times n$ Sudoku rectangle. Sections 4 and 5 are devoted to two corollaries
of our characterization. We observe in Section 4, that the procedure used to
prove our sufficient conditions gives an efficient algorithm for deciding
whether a given $m\times n$ rectangle is completable and find a valid
completion. Furthermore, in Section 5 we use this procedure combined with
theorems of Minc and Van der Waerden, to prove asymptotic bounds on the number
of Sudoku squares of order $n$.

### Related work.

Recently quite a few papers have appeared on the mathematical questions raised
for Sudoku squares similar to Latin squares. For example in [4] the number of
Sudoku squares is discussed, while some results about the sets of mutually
orthogonal Sudoku squares are given in [11]. Concepts of “critical (or
defining) sets” i.e. “the minimum Sudoku problem” and “Sudoku trades (or
detection of unavoidable sets in Sudoku)” are studied in [9], [10], [14], and
[3]. In [1] Sudoku is considered as a special case of Gerechte designs and
they introduce some interesting mathematical problems about them. The
complexity and completeness of finding solution for Sudoku is investigated in
[12]. List coloring of Latin and Sudoku graphs is studied in [7] which has an
extensive number of references on Sudoku. In [8] the problem of completing
Sudoku rectangles is studied.

##  2 Sufficient Conditions

In Theorem A it is shown that if the Sudoku rectangle only leaves parts of the
last row block incomplete, then it can be completed to a Sudoku square. In
this section, we prove two theorems, showing that for certain other values of
$m$, an $m\times n$ Sudoku rectangle can always be completed to a Sudoku
square. We start with the next result which shows that if the Sudoku rectangle
consists of a number of full row blocks and a number of empty row blocks
(i.e., no row block is partially filled), then it can always be completed to a
Sudoku square.

######  Theorem 1.

Assume $n=k^{2}$ and $m=lk$ for some $l<k$. Then every $m\times n$ Sudoku
rectangle $R$ can be completed to a Sudoku square.

###### Proof.

We prove that we can complete the rectangle $R$ row-block by row-block. To do
this, we need to show that $R$ can be extended to a $k(l+1)\times n$ Sudoku
rectangle. This is done in two steps: First, we fill the elements in the
$(l+1)$st row block in such a way that column and block conditions are
satisfied. In the second step, we permute the elements in each column of the
$(l+1)$st row block in such a way that the resulting configuration satisfies
the row condition as well. Note that column and block conditions will stay
satisfied after such a permutation, and therefore, the resulting configuration
is a valid Sudoku extension of $R$.

We start with the first step. The $(l+1)$st row block consists of $k$ blocks,
which we denote by $B_{1},B_{2},\ldots,B_{k}$. For each block $B_{d}$, we
formulate an assignment problem as follows: On one side of the assignment
problem, we have the numbers $1,\ldots,n$. On the other side, we have the $k$
columns $c_{1},c_{2},\ldots,c_{k}$ of the block. A number $i$ can be assigned
to a column $j$, if $i$ does not appear in column $j$ in $R$. For each number
$i$, this number appears exactly once in each of the blocks above $B_{d}$, and
these appearances are in different columns. Therefore, each number $i$ can be
assigned to exactly $k-l$ different columns. Also, for each column $j$, there
are precisely $lk$ distinct numbers in that column in $R$. Therefore, there
are precisely $n-lk$ numbers that can be assigned to column $j$. The objective
is to find an assignment that assigns each number to exactly one column, and
assigns precisely $k$ numbers to each column.

We show that this assignment problem always has a feasible solution. We prove
this by using a network flow argument. The assignment problem can be
formulated as a network flow problem: There is a source $s$ that has links of
capacity 1 to $n$ nodes representing the numbers; each number $i$ has a link
of capacity 1 to each of the nodes representing columns that it can be
assigned to; and there is a sink $t$ that has a link of capacity $k$ from each
of the nodes representing the columns. It is easy to see that it is possible
to route a flow of value $n$ from $s$ to $t$ in this network: The flow on each
of the edges from $s$ to number nodes is 1; the flow on each of the edges from
number nodes to column nodes is $1/(k-l)$; and the flow from each of the
column nodes to $t$ is $k$. It is not hard to see that this is a feasible flow
of value $k$ (and is therefore the maximum flow from $s$ to $t$). By the Ford-
Fulkerson theorem, there must be an integer flow of the same value in this
network. This integer flow gives an assignment of numbers $1,\ldots,n$ to the
$k$ columns in $B_{d}$ such that each number is assigned to precisely one
column, each column has precisely $k$ numbers assigned to it, and no number is
assigned to a column $c_{i}$ where it appears in the $i$th column of $R$.
Putting these assignments together for all blocks $B_{d}$ of the $(l+1)$st row
block, we obtain an assignment of the $n$ numbers to the $n$ columns such
that:

  * •

each number is assigned to precisely $k$ columns, one from each block;

  * •

each column has precisely $k$ numbers assigned to it; and

  * •

no number is assigned to a column where it appears in one of the cells of the
column above that.

Let us call this assignment $M$. The second step is to take the assignment $M$
and specify in which of the $k$ rows of the $(l+1)$st row block each number
must go. We construct a bipartite graph as follows: On one side, we have the
numbers $1,\ldots,n$, and on the other side, we have the $n$ columns of the
$(l+1)$st row block. There is an edge between number $i$ and column $j$, if
$i$ is assigned to $j$ under the assignment $M$. By the properties of $M$,
this is a bipartite $k$-regular graph. By König’s theorem, this graph has an
edge-coloring with $k$ colors. Let the colors be denoted by $1,\ldots,k$. We
now complete the $(l+1)$st row block as follows: For each edge $(i,j)$ colored
with color $c$, we place the number $i$ on the $c$th row of the row block and
$j$th column. It is easy to see that with the addition of this row-block all
the Sudoku conditions are still satisfied: There is no repeated element in any
row, since the coloring is a proper edge coloring; there is no repeated
element in each column by the third property of the assignment $M$; and there
is no repeated element in each block by the first property of the assignment
$M$. ∎

Next, we prove the following sufficient condition for completability of a
Sudoku rectangle.

######  Theorem 2.

Assume $n=k^{2}$ and $m=lk+r$ for some $l<k$ and $0\leq r<k$. Then an $m\times
n$ Sudoku rectangle $R$ can always be completed to a Sudoku square, if
$(k-r)(k-l)\geq lk$.

###### Proof.

We proceed the same way as in the proof of Theorem 1. The empty rows of the
$(l+1)$st row block form a $(k-r)\times n$ rectangle $R_{1}$. First, we show
that for each column in $R_{1}$, we can pick $k-r$ distinct elements in such a
way that the elements chosen for the columns in each block are distinct, and
the $k-r$ elements for each column do not appear in that column in $R$. Next,
we show that the elements in each column can be permuted in such a way that
the elements in each row become distinct. Note that for the second step
exactly the same proof as in Theorem 1 works. Therefore, we only need to prove
the first step. Also, note that the first step can be done block-by-block. So,
it is enough to consider one block $B_{d}$, and prove the following: for each
column in $B_{d}$ we can pick $k-r$ elements distinct from elements that
appear in $B_{d}$ and in the cells of the same column above $B_{d}$ in such a
way that the elements picked for the $k$ columns in $B_{d}$ are distinct.

We formulate the problem as a matching problem as follows: On one side, we
have $k$ vertices corresponding to the $k$ columns in the block $B_{d}$. We
call these the column vertices. On the other side, we have $n-rk$ vertices,
corresponding to the elements that do not appear in the $r$ filled rows of the
block. We call these the element vertices. There is an edge between a column
vertex and an element vertex if the corresponding element does not appear in
the corresponding column in $R$. The degree of each element vertex is
precisely $k-l$, since out of the $k$ columns, it appears in $l$ of them (one
for each block above this block). The degree of each column vertex is a number
between $n-lk-rk$ and $n-lk$. We prove that there is a 1-to-$(k-r)$ matching
in this graph, i.e., a matching which matches each column vertex to precisely
$k-r$ element vertices, and each element vertex to precisely one column
vertex.

We prove this by verifying the following easy extension of Hall’s condition
[13] for the existence of a 1 to $(k-r)$ matching. This condition states that
such a matching exists if and only if for every set $S$ of column vertices,
$|N(S)|\geq(k-r)|S|$, where $N(S)$ is the set of all element vertices adjacent
to at least one vertex in $S$. To prove this, we consider two cases: either
$|S|>l$ or $|S|\leq l$. In the first case, consider an element $x$ that does
not appear in the $r$ filled rows of the block. Since $x$ appears in exactly
$l$ columns in the corresponding column block in $R$ and $|S|>l$, there is at
least one column in $S$ that does not contain $x$. Therefore, the
corresponding column vertex is adjacent to the element vertex $x$. This means
that in this case, $N(S)$ is the set of all $n-rk$ element vertices. Hence,
$|N(S)|=k(k-r)\geq|S|(k-r)$, as desired. In the second case ($|S|\leq l$), we
use the fact that the degree of each column vertex in this graph is at least
$n-lk-rk$, and therefore, $|N(S)|\geq n-lk-rk$. Using this inequality, we
have:

$|N(S)|\geq k^{2}-lk-rk=(k-r)(k-l)-rl\geq lk-rl\geq(k-r)|S|.$

This completes the proof of Hall’s condition, which implies that to each
column we can assign $k-r$ elements distinct from elements that appear in the
$r$ filled rows of the block, such that each such element is assigned
precisely to one column. ∎

##  3 A Complete Characterization

In this section, we give some Sudoku rectangle constructions to prove that the
union of the three sufficient conditions given in Section 2 and Theorem A is
also necessary.

######  Theorem 3.

Assume $n=k^{2}$ and $m=lk+r$ for some $l<k$ and $0\leq r<k$. Every $m\times
n$ Sudoku rectangle $R$ can always be completed to a Sudoku square, if and
only if at least one of the following conditions hold:

  * •

$l=k-1$,

  * •

$r=0$, or

  * •

$(k-r)(k-l)\geq lk$.

We proved sufficiency of the above conditions in the previous section. To
prove necessity, we need to construct an $m\times n$ Sudoku rectangle that is
not completable for any value of $m$ that does not satisfy the conditions of
the theorem. The main tool we use in this construction is the following
extension of Theorem 1, which proves that any $(m,k,n)$-Sudoku rectangle can
be extended to an $m\times n$ Sudoku rectangle. This means that to construct
an $m\times n$ Sudoku rectangle that is not completable, it is enough to
construct its first column block, i.e., an $(m,k,n)$-Sudoku rectangle that is
not completable.

######  Lemma 1.

For every $n=k^{2}$, $m\leq n$, every $(m,k,n)$-Sudoku rectangle $R$ can be
extended to an $(m,n,n)$-Sudoku rectangle.

###### Proof.

We follow an algorithm similar to the one used in the proof of Theorem 1 to
extend $R$, column block by column block. Before starting this algorithm,
first we append a few rows to $R$ to make sure the number of rows is a
multiple of $k$: Let $m=lk+r$, where $0\leq r<k$. We append $k-r$ rows to $R$,
containing the $n-rk$ elements that do not appear in rows $lk+1$ through
$lk+r$ in $R$ in an arbitrary order. This converts $R$ into an $(l+1)k\times
k$ rectangle $R^{\prime}$ that satisfies the row and block conditions, but
might violate the column condition (i.e., $R^{\prime}$ is not necessarily a
partial Sudoku square). Now, we append a new column block to this rectangle
using a two-stage process as follows: In the first stage, for each row in
$R^{\prime}$, we are going to pick $k$ elements among elements that do not
already appear in this row in $R^{\prime}$, such that sets picked for rows
within the same row block are disjoint. This is done by constructing a graph
similar to the one constructed in the proof of Theorem 1 for each row block of
$R^{\prime}$, and proving it contains a $k$-to-$1$ matching. The graph
contains $k$ row vertices corresponding to the rows within this row block, and
$n$ element vertices corresponding to the elements $1$ to $n$. There is an
edge between row vertex $i$ and element vertex $j$ if $j$ does not appear in
the $i$th row of $R^{\prime}$. Since $R^{\prime}$ satisfies row and block
constraints, the degree of each row vertex in this graph is precisely $n-k$
and the degree of each element vertex is $k-1$. Therefore, using essentially
the same argument as in the proof of Theorem 1, we can show that this graph
contains a matching that matches each row vertex to precisely $k$ element
vertices and each element vertex to exactly one row vertex. In the second
stage, we assign each of the $k$ elements assigned to each row to one of the
$k$ columns within the new column block, in such a way that the column
condition is satisfied. Again, this is done by building a bipartite graph as
in the proof of Theorem 1. The graph contains $(l+1)k$ row vertices,
corresponding to the rows of $R^{\prime}$, and $n$ element vertices. There is
an edge between an element vertex $i$ and a row vertex $j$ if the element $i$
is assigned to the row $j$ in the first stage. The maximum degree of vertices
in this graph is $k$. Therefore, the graph is $k$-edge colorable. We assign
each color to one column of the new column block, and place an element $i$ in
row $j$ in column $c$ of this column block, if the edge between $i$ and $j$ is
colored with the color corresponding to $c$. This ensures that the vertices
assigned to the same column are distinct. Therefore, we obtain an
$(l+1)k\times 2k$ extension of $R^{\prime}$ that satisfies block and row
conditions, and satisfies the column conditions except possibly for the first
$k$ columns. We can continue this process, column block by column block,
resulting in an $(l+1)k\times n$ extension of $R^{\prime}$ that satisfies row
and block conditions and the column conditions except possibly for the first
$k$ columns (i.e., columns of $R^{\prime}$). Removing the last $k-r$ rows of
this rectangle results in an $m\times n$ rectangle that satisfies row, block,
and column conditions. ∎

The following lemma is another useful tool in our constructions.

######  Lemma 2.

For every $a,b\leq k$ and every set $A$ of $k\cdot\max\\{a,b\\}$ elements,
there is an $(ak,b,n)$-Sudoku rectangle with elements from $A$.

###### Proof.

Let $c=\max\\{a,b\\}$. We partition the elements of $A$ into $c$ sets
$A_{0},A_{1},\ldots,A_{c-1}$, each of size $k$. The Sudoku rectangle is
constructed as follows: We fill the elements in column $j+1$ ($0\leq j<b$) and
rows $ik+1$ through $ik+k$ ($0\leq i<a$) of the rectangle with elements from
$A_{(i+j)\mod c}$, in increasing order111For the purpose of this lemma,
elements of $A_{(i+j)\mod c}$ can be placed in any arbitrary order. However,
placing them in increasing order makes it easier to combine and modify these
rectangles, as needed in the proof of Theorem 3.. Since for any fixed $i$, the
family $\\{A_{(i+j)\mod c}:1\leq j\leq b\\}$ is a family of disjoint sets, the
block conditions (and therefore the row conditions) are satisfied. Also, for
every fixed $j$, the family $\\{A_{(i+j)\mod c}:1\leq i\leq a\\}$ is a family
of disjoint sets, and therefore the column conditions are also satisfied. ∎

Equipped with the above lemmas, we are now ready to prove Theorem 3:

###### Proof of Theorem 3.

The “if” part follows from Theorems A, 1, and 2. To prove the “only if” part,
let $m=lk+r$ be a number that does not satisfy any of the three conditions
(i.e., $l\leq k-2$, $r\geq 1$, and $(k-r)(k-l)<lk$), and construct an $m\times
n$ Sudoku rectangle that cannot be completed to a Sudoku square. We use Lemma
1 in this construction as follows: Instead of constructing an $m\times n$
Sudoku rectangle, we construct an $(m,k,n)$-Sudoku rectangle that cannot be
completed into a Sudoku square, and use Lemma 1 to extend this $m\times k$
rectangle to an $m\times n$ rectangle. As the original $m\times k$ rectangle
was not completable, the $m\times n$ rectangle cannot be completable either.

We consider three cases for this construction: (a) $l<k/2$, (b) $l\geq k/2$
and $k$ is even, and (c) $l\geq k/2$ and $k$ is odd.

  1. (a)

$l<k/2$: Using Lemma 2 with $a=b=l$, we can construct an $(lk,l,n)$-Sudoku
rectangle $R_{1}$ with entries in $\\{1,\ldots,lk\\}$. Also, since $l+1\leq
k-l$, using Lemma 2 with $a=l+1$ and $b=k-l$ we obtain an
$((l+1)k,k-l,n)$-Sudoku rectangle $R_{2}$ with elements in
$\\{lk+1,\ldots,k^{2}\\}$. The idea is to construct an $(m,k,n)$-Sudoku
rectangle by concatenating the columns of $R_{2}$ after the columns of
$R_{1}$. However, $R_{1}$ has $m-r$ rows and $R_{2}$ has $m+k-r$ rows, and
therefore before concatenating $R_{1}$ and $R_{2}$, we need to add $r$ rows to
$R_{1}$ and remove $k-r$ rows from $R_{2}$ to make sure both rectangles have
$m$ rows. To do this, we first simply remove the extra $k-r$ rows from
$R_{2}$. These rows contain a set of $(k-r)(k-l)$ elements $E$. We place these
elements in an arbitrary order in the missing $r$ rows of $R_{1}$. To fill
these rows with elements in $E$, we need $lr\leq|E|=(k-r)(k-l)=lr+k(k-l-r)$.
This holds if and only if $l+r\leq k$, in which case we are done. If $l+r>k$,
$R_{1}$ is still missing $lr-|E|=k(l+r-k)$ elements to become an $m\times l$
rectangle. We pick a set $E^{\prime}$ of this many elements arbitrarily from
rows $lk+1$ through $lk+r$ of $R_{2}$. This is feasible, since $R_{2}$ has
$(k-l)r$ elements in these rows, and

$(k-l)r=(r+l)k-(r+k)l>(r+l)k-(k+k)l>(r+l)k-2k\cdot\frac{k}{2}=k(l+r-k).$

We now perform the following switch: The elements of $E^{\prime}$ in the rows
$lk+1$ through $lk+r$ of $R_{2}$ are replaced with arbitrary elements in
$1,\ldots,lk\\}$ (possible since $k(l+r-k)\leq lk$), and the missing elements
of $R_{1}$ are filled with elements in $E^{\prime}$.

It is easy to see that the rectangle $R$ obtained by concatenating the columns
of $R_{1}$ and $R_{2}$ after the above operations is an $(m,k,n)$-Sudoku
rectangle: The block conditions are satisfied since $R_{1}$ and $R_{2}$
initially satisfied these conditions, they were composed of disjoint sets of
elements, and none of the steps above violated the block condition. The row
conditions follows directly from the block conditions, and the column
conditions are also true since they are true for $R_{1}$ and $R_{2}$
constructed by Lemma 2, and the above operations only moved elements from
$lk+1,\ldots,k^{2}$ to the first $l$ columns (which did not previously contain
any of these elements), and elements from $1,\ldots,lk$ to the last $k-l$
columns (which, again, did not previously contain any of these elements).

Now, we prove that $R$ is not completable to a Sudoku square. We consider two
cases: $l+r\leq k$ and $l+r>k$. In the latter case, it is evident from the
above construction that all elements in $\\{lk+1,\ldots,k^{2}\\}$ appear in
the last partial block (i.e., last $r$ rows) of $R$. Also, all elements in
$\\{1,\ldots,lk\\}$ appear in each of the first $l$ columns. Therefore, there
is no element that can be placed in any of the entries in columns $1$ through
$l$ of the $(m+1)$st row without violating column or block conditions.

We now consider the case $l+r\leq k$. Consider the first $l$ columns of $R$.
To complete $R$, we must fill rows $m+1,\ldots,m+k-r=(l+1)k$ of these columns
with $l(k-r)$ elements. Let us call the set of these elements $S$. By block
conditions, elements in $S$ must all be distinct, and also distinct from the
$rk$ elements in the first $r$ rows of this block. Furthermore, since all
elements in $\\{1,\ldots,lk\\}$ appear in each of the first $l$ columns, by
column conditions $S$ cannot contain any of the elements $1,\ldots,lk$.
Therefore, we must have at least $l(k-r)+rk+lk$ distinct elements. Thus,
$l(k-r)+rk+lk\leq k^{2}$, or $lk\leq k^{2}-lk-rk+lr=(k-l)(k-r)$, contradicting
the third condition.

  2. (b)

$l\geq k/2$ and $k$ is even: Let $F=\\{1,\ldots,\frac{k^{2}}{2}\\}$ and
$G=\\{\frac{k^{2}}{2}+1,\ldots,k^{2}\\}$. We use Lemma 2 to construct the
following four Sudoku rectangles:

     * •

a $(\frac{k^{2}}{2},\frac{k}{2},n)$-Sudoku rectangle $R_{1}$ with entries in
$F$,

     * •

a $(\frac{k^{2}}{2},\frac{k}{2},n)$-Sudoku rectangle $R_{2}$ with entries in
$G$,

     * •

an $((l+1-\frac{k}{2})k,\frac{k}{2},n)$-Sudoku rectangle $R_{3}$ with entries
in $G$, and

     * •

an $((l+1-\frac{k}{2})k,\frac{k}{2},n)$-Sudoku rectangle $R_{4}$ with entries
in $F$.

Recall that the construction in Lemma 2 starts by defining a partition of the
set of elements into subsets of size $k$. Let $F_{0},F_{1},\ldots,F_{k/2-1}$
be the partition of $F$ used to construct $R_{1}$, and
$G_{0},G_{1},\ldots,G_{k/2-1}$ be the partition of $G$ used to construct
$R_{2}$. To construct $R_{3}$, we use this permutation of the latter
partition: $G_{1},G_{3},G_{4},\ldots,G_{k/2-1},G_{2},G_{0}$. In other words,
the first column of the first row block of $R_{3}$ contains elements of
$G_{1}$, the second column of this row block contains elements of $G_{3}$, the
third column contains $G_{4}$, and so on. For $R_{4}$, we use the partition
$F_{k/2-1},F_{k/2-2},\ldots,F_{1},F_{0}$. By placing the four rectangles
$R_{1},R_{2},R_{3}$, and $R_{4}$ in the following configuration, we obtain an
$(l+1)k\times k$ rectangle $R$:

$R=\left[\begin{array}[]{cc}R_{1}&R_{2}\\\ R_{3}&R_{4}\end{array}\right]$

It is easy to see that $R$ is a Sudoku rectangle. Next, we remove the last
$k-r$ rows of $R$ to obtain an $(m,k,n)$-Sudoku rectangle $R^{\prime}$.

Since the partition $G_{1},G_{3},G_{4},\ldots,G_{k/2-1},G_{2},G_{0}$ was used
to construct $R_{3}$, in the first column of this rectangle elements of these
sets appear in this order. Since $R_{3}$ contains
$l+1-\frac{k}{2}<\frac{k}{2}$ row blocks, none of the elements of $G_{0}$ can
appear in the first column of $R_{3}$ (and thereofre in the first column of
$R^{\prime}$). Similarly, none of the elements of $G_{2}$ appear in the last
column of $R_{3}$ (and therefore the $\frac{k}{2}$th column of $R^{\prime}$.
The first column of $R_{4}$ contains elements of $F_{k/2-1},F_{k/2-2},\ldots$,
in this order. Thus, the first column of $R_{4}$ (and therefore the
$(\frac{k}{2}+1)$th column of $R^{\prime}$) does not contain any of the
elements of $F_{0}$. In the second column of $R_{4}$, we have elements of
$F_{k/2-2},F_{k/2-3},\ldots$, in this order. If $l<k-2$, none of the elements
of $F_{0}$ appear in this column (and therefore the $(\frac{k}{2}+2)$th column
of $R^{\prime}$). If $l=k-2$, elements of $F_{0}$ appear in the last row block
in the second column of $R_{4}$. But then since $R^{\prime}$ is obtained from
$R$ by removing its last $k-r>0$ rows, the last element of $F_{0}$ does not
appear in the $(\frac{k}{2}+1)$th column of $R^{\prime}$. Let $x$ denote the
last element of $F_{0}$, $x_{1}$ denote the last element of $G_{0}$, and
$x_{2}$ denote the last element of $G_{2}$. By the above arguments, we know
that $x$ does not appear in $(\frac{k}{2}+1)$th and $(\frac{k}{2}+2)$th
columns of $R^{\prime}$, $x_{1}$ does not appear in its first column, and
$x_{2}$ does not appear in its $\frac{k}{2}$th column. Also, by the
construction of $R_{1}$ and $R_{2}$, $x$ appears in the first column of the
first row block and the $\frac{k}{2}$th column of the second row block of
$R^{\prime}$, $x_{1}$ appears in the $(\frac{k}{2}+1)$th column of the first
row block of $R^{\prime}$, and $x_{2}$ appears in the $(\frac{k}{2}+2)$th
column of the second row block of $R^{\prime}$. Finally, since $x_{1}$, and
$x_{2}$ are the last elements of the sets $G_{0}$ and $G_{2}$, they can only
appear in the last row in any row block in $R$. Therefore, since $R^{\prime}$
is obtained from $R$ by removing the last $k-r\geq 1$ rows, neither $x_{1}$
nor $x_{2}$ appear in the last row block of $R^{\prime}$.

We now perturb the rectangle $R^{\prime}$ to obtain another rectangle that is
not completable. We do this by first swapping $x$ and $x_{1}$ in the first row
block of $R^{\prime}$, and $x$ and $x_{2}$ in the second row block of
$R^{\prime}$. By the above observations, these swaps do not violate the Sudoku
conditions. Furthermore, after these swaps, the $(\frac{k}{2}+1)$th column of
the rectangle does not contain $x_{1}$ and its $(\frac{k}{2}+2)$th column does
not contain $x_{2}$. Therefore, we can change the element in row $lk+1$ and
column $(\frac{k}{2}+1)$ to $x_{1}$, and the element in row $lk+1$ and column
$(\frac{k}{2}+2)$ to $x_{2}$. Again, it is easy to see that Sudoku conditions
are preserved. Let $R^{\prime\prime}$ denote the resulting $(m,k,n)$-Sudoku
rectangle.

We argue that $R^{\prime\prime}$ is not completable. Consider the first $k/2$
columns of $R^{\prime\prime}$. To complete $R^{\prime\prime}$, we must place
$\frac{k}{2}(k-r)$ distinct elements in rows $m+1,\ldots,m+k-r=(l+1)k$ of
these columns. Let $T$ denote the set of these elements. Every element in
$F\setminus\\{x\\}$ appears in each of the first $k/2$ columns of
$R^{\prime\prime}$. Therefore, $T$ cannot contain any elements of $F$, except
possibly $x$. Also, it cannot contain any of the elements of $G$ that appear
in the last row block of $R^{\prime\prime}$. There are precisely
$r\cdot\frac{k}{2}+2$ such elements, namely the $r\cdot\frac{k}{2}$ elements
of $G$ that appear in the first $k/2$ columns of the last row block of
$R^{\prime\prime}$, and $x_{1}$ and $x_{2}$. This means that there are at most
$\frac{k}{2}(k-r)-2$ elements of $G$ that can be in $T$. Therefore, $T$ cannot
contain more than $\frac{k}{2}(k-r)-1$ elements, which is a contradiction.

  3. (c)

$l\geq k/2$ and $k$ is odd: The high-level idea of the construction is similar
to the one in case (b): we construct an $(l+1)k\times k$ rectangle $R$ by
composing four smaller rectangles, truncate it to get an $m\times k$ rectangle
$R^{\prime}$, and then slightly perturb it to get an $m\times k$ rectangle
$R^{\prime\prime}$ that is not completable.

Let $F=\\{1,\ldots,k\lceil\frac{k}{2}\rceil\\}$,
$G=\\{k\lceil\frac{k}{2}\rceil+1,\ldots,k^{2}\\}$, and
$H=\\{k^{2}+1,\ldots,k^{2}+k\\}$. Note that $|F|=k\lceil\frac{k}{2}\rceil$,
$|G|=k\lfloor\frac{k}{2}\rfloor$, and $|G\cup H|=k\lceil\frac{k}{2}\rceil$. We
construct the following Sudoku rectangles using Lemma 2:

     * •

a $(k\lceil\frac{k}{2}\rceil,\lfloor\frac{k}{2}\rfloor,n)$-Sudoku rectangle
$R_{1}$ with entries in $F$,

     * •

a $(k\lceil\frac{k}{2}\rceil,\lceil\frac{k}{2}\rceil,n)$-Sudoku rectangle
$R_{2}$ with entries in $G\cup H$.

     * •

an $((l+1-\lceil\frac{k}{2}\rceil)k,\lfloor\frac{k}{2}\rfloor,n)$-Sudoku
rectangle $R_{3}$ with entries in $G$, and

     * •

an $((l+2-\lceil\frac{k}{2}\rceil)k,\lceil\frac{k}{2}\rceil,n)$-Sudoku
rectangle $R_{4}$ with entries in $F$.

Recall that the construction in Lemma 2 starts by defining a partition of the
set of elements into subsets of size $k$. Let $F_{0},F_{1},\ldots,F_{\lceil
k/2\rceil-1}$ be the partition of $F$ used to construct $R_{1}$, and
$H,G_{0},G_{1},\ldots,G_{\lfloor k/2\rfloor-1}$ be the partition of $G\cup H$
used to construct $R_{2}$. Without loss of generality, we assume that the
partition $G_{\lfloor k/2\rfloor-1},G_{\lfloor k/2\rfloor-2},\ldots,G_{0}$ is
used to construct $R_{3}$, and the partition $F_{\lceil k/2\rceil-1},F_{\lceil
k/2\rceil-2},\ldots,F_{1},F_{0}$ is used to construct $R_{4}$. This means that
the first row block of $R_{1}$ contains elements of $F_{0}$ in its first
column, $F_{1}$ in the second column, and $F_{\lceil k/2\rceil-2}$ in its last
(i.e., $\lfloor k/2\rfloor$th) column. Therefore, the first row block of
$R_{1}$ does not contain any of the elements of $F_{\lceil k/2\rceil-1}$.
Similarly, the second row block of $R_{1}$ does not contain any element in
$F_{0}$, the third row block does not contain any element in $F_{1}$, and so
on. We now modify $R_{2}$ as follows: Replace elements of $H$ in the first row
block of $R_{2}$ by elements of $F_{\lceil k/2\rceil-1}$, the elements of $H$
in the second row block of $R_{2}$ by elements of $F_{0}$, and so on. Let
$R^{\prime}_{2}$ denote the resulting rectangle. All entries of
$R^{\prime}_{2}$ are in $F\cup G$. Note that by the construction in Lemma 2,
elements of $H$ appear in the first column of $R_{2}$ in the first row block,
the last (i.e., $\lceil k/2\rceil$th) column in its second row block, …, and
the second column in its last (i.e., $\lceil k/2\rceil$th) row block. This
means that the set of elements appearing in the first column of
$R^{\prime}_{2}$ is $G\cup F_{\lceil k/2\rceil-1}$, in its second column is
$G\cup F_{\lceil k/2\rceil-2}$, and so on. On the other hand, the set of
elements appearing in the $i$’th column of the first row block of $R_{4}$ is
precisely $F_{\lceil k/2\rceil-i}$. Therefore, if we remove the first row
block of $R_{4}$, we obtain an
$((l+1-\lceil\frac{k}{2}\rceil)k,\lfloor\frac{k}{2}\rfloor,n)$-Sudoku
rectangle $R^{\prime}_{4}$ with elements in $F$ such that the $i$’th column of
$R^{\prime}_{4}$ does not contain any of the elements of $F_{\lceil
k/2\rceil-i}$. We are now ready to define an $(l+1)k\times k$ rectangle $R$ by
placing the four rectangles $R_{1},R^{\prime}_{2},R_{3}$, and $R^{\prime}_{4}$
as follows:

$R=\left[\begin{array}[]{cc}R_{1}&R^{\prime}_{2}\\\
R_{3}&R^{\prime}_{4}\end{array}\right]$

Given the above construction, it is easy to see that $R$ is a Sudoku rectangle
with elements in $F\cup G$. Let $R^{\prime}$ denote the $(m,k,n)$-Sudoku
rectangle obtained by removing the last $k-r$ rows of $R$. The last step is to
perturb $R^{\prime}$ by moving a few elements in such a way that the resulting
rectangle is not completable.

Recall that the partition $G_{\lfloor k/2\rfloor-1},G_{\lfloor
k/2\rfloor-2},\ldots,G_{0}$ was used to construct $R_{3}$. Therefore, in the
first column of $R_{3}$, we have the elements in $G_{\lfloor
k/2\rfloor-1},G_{\lfloor k/2\rfloor-2},\ldots,G_{s}$, where $s=\lfloor
k/2\rfloor-(l+1-\lceil\frac{k}{2}\rceil)=k-1-l>0$. Therefore, none of the
elements in $G_{0}$ appears in the first column of $R_{3}$, and therefore in
the first column of $R^{\prime}$. Similarly, none of the elements of
$G_{\lfloor k/2\rfloor-1}$ appears in the second column of $R^{\prime}$. In
the last column of $R_{4}$, we have the elements of $F_{0},F_{\lceil
k/2\rceil-1},F_{\lceil k/2\rceil-2},\ldots,F_{s+1}$. Therefore, none of the
elements of $F_{1}$ appears in the last column of $R^{\prime}$. In the first
column of $R_{4}$, we have elements of $F_{\lceil k/2\rceil-1},F_{\lceil
k/2\rceil-2},\ldots,F_{s}$. Therefore, since $R^{\prime}$ is obtained by
removing the last $k-r\geq 1$ rows of $R$, the last element of $F_{1}$ does
not appear in the $\lceil k/2\rceil$th column of $R^{\prime}$ (which
corresponds to the first column of $R_{4}$). Now, let $x$ denote the last
element of $F_{1}$, $x_{1}$ denote the last element of $G_{\lfloor
k/2\rfloor-1}$, and $x_{2}$ denote the last element of $G_{0}$. To summarize,
the above arguments, we know that $x$ does not appear in neither the last nor
the $\lceil k/2\rceil$th column of $R^{\prime}$, $x_{1}$ does not appear in
the second column of $R^{\prime}$, and $x_{2}$ does not appear in the first
column of $R^{\prime}$. Furthermore, by the definition of $R_{1}$ and $R_{2}$,
$x$ appears in the second column of the first row block of $R^{\prime}$ and
the first column of the second row block of $R^{\prime}$ (where all elements
of $F_{1}$ are listed), $x_{1}$ appears in the last column of the first row
block of $R^{\prime}$ (where all the elements of $G_{\lfloor k/2\rfloor-1}$
are listed), and $x_{2}$ appears in the $\lceil k/2\rceil$th column of the
second row block of $R^{\prime}$ (where all the elements of $G_{0}$ are
listed). Finally, since $x_{1}$ and $x_{2}$ are the last elements of
$G_{\lfloor k/2\rfloor-1}$ and $G_{0}$, they can only appear in the last row
in any row block in $R$. Therefore, since $R^{\prime}$ is obtained from $R$ by
removing the last $k-r\geq 1$ rows, neither $x_{1}$ nor $x_{2}$ appear in the
last row block of $R^{\prime}$.

We are now ready to perform the swaps that would make $R^{\prime}$ not
completable. In the first row block of $R^{\prime}$, we swap $x$ and $x_{1}$
(which appear in the second and the last columns). In the second row block, we
swap $x$ and $x_{2}$ (occuring in the first and the $\lceil k/2\rceil$th
column). By the above observations, these swaps do not violate the Sudoku
conditions. After these swaps, there is no $x_{1}$ in the last column of the
rectangle. Therefore, we can replace the element in the row $lk+1$ of this
column by $x_{1}$. Similarly, we can replace the element in the row $lk+1$ of
the $\lceil k/2\rceil$th column by $x_{2}$. Let $R^{\prime\prime}$ denote the
resulting $(m,k,n)$-Sudoku rectangle.

We now prove that $R^{\prime\prime}$ is not completable. To see this, consider
the first $\lfloor k/2\rfloor$ columns, and notice that to complete
$R^{\prime\prime}$, we need to place $(k-r)\lfloor k/2\rfloor$ distinct
elements in rows $m+1$ through $m+k-r$ of these columns. Let $T$ denote the
set of these elements. Since all elements in $F\setminus\\{x\\}$ appear in
each of the first $\lfloor k/2\rfloor$ columns of $R^{\prime\prime}$, we must
have $T\subseteq G\cup\\{x\\}$. On the other hand, by the block condition,
none of the elements in $T$ must appear in the last row block of
$R^{\prime\prime}$. This row block contains precisely
$r\lfloor\frac{k}{2}\rfloor$ elements of $G$ in its first $\lfloor k/2\rfloor$
columns and two elements of $G$ (namely, $x_{1}$ and $x_{2}$) in the remaining
columns. Therefore, $T$ cannot contain more than $(k-r)\lfloor k/2\rfloor-1$
distinct elements, which is a contradiction.

∎

##  4 Algorithms for Sudoku Rectangle Completion

The two-stage procedure used in the proof of Theorem 2 is essentially a
polynomial-time algoritm for completing a Sudoku rectangle into a Sudoku
square. Furthermore, we note that the same procedure applies for every value
of $m$, and not just for those for which Theorem 2 guarantees the existence of
a Sudoku square. This is a simple observation, and follows from the fact that
if the given Sudoku rectangle $R$ has a valid extension, then this extension
gives a perfect 1-to-$(k-r)$ matching in the graph constructed in the first
stage. On the other hand, if $R$ is not completable, then the graph
constructed in the first stage does not have any perfect 1-to-$(k-r)$
matching, since if it did, this matching can be turned into an extension to a
Sudoku square using the method outlined in the proof of Theorem 2. Therefore,
we have the following result.

######  Theorem 4.

There is a polynomial time algorithm that given an $m\times n$ Sudoku
rectangle $R$, finds a completion of $R$ to a Sudoku square, or decides that
$R$ is not completable to a Sudoku square.

An interesting follow-up question is whether the above result can be
generalized to the case where $R$ is a general partial Sudoku square or when
$R$ is a $(p,q,n)$-Sudoku rectangle. We conjecture that at least in the former
case, the problem is NP-complete.

##  5 Asymptotics of the Number of Sudoku Squares

Let ${\mathrm{Sud}}(n)$ denote the number of Sudoku squares of order $n$. In
this section, we give a tight asymptotic bound on
$({\mathrm{Sud}}(n))^{1/n^{2}}$. Our proof uses the Sudoku rectangle
completion procedure of the Section 3 as well as classical bounds on the
permanent of matrices. Our result is summarized in the following theorem.

######  Theorem 5.

We have $({\mathrm{Sud}}(n))^{1/n^{2}}\sim e^{-3}n$ as $n\rightarrow\infty$.

This should be contrasted with a similar result for Latin squares (see, for
example, [13, Theorem 17.3]), which shows that $(L(n))^{1/n^{2}}\sim e^{-2}n$
as $n\rightarrow\infty$, where $L(n)$ is the number of Latin squares of order
$n$. In other words,

######  Corollary 1.

The fraction of the Latin squares of order $n$ that are Sudoku squares is
$(\frac{1}{e}+o(1))^{n^{2}}$.

Proof of Theorem 5 uses two classical results about the permanent of matrices.
The first result, known as the Van der Waerden conjecture (proved
independently by Falikman and Egoritsjev, see [13]), states that the permanent
of every doubly stochastic matrix of order $n$ is at least $n!n^{-n}$. This
implies

######  Theorem B.

([13]) The number of perfect matchings in an $r$-regular bipartite graph with
$n$ vertices in each part is at least $n!(r/n)^{n}$.

The other result is an upper bound on the permanent of matrices. This result,
conjectured by Minc in 1967 and proved by Brégman in 1973, shows that the
permanent of a $(0,1)$-matrix with row-sums $r_{1},r_{2},\ldots,r_{n}$ is at
most $\prod_{j}(r_{j}!)^{1/r_{j}}$. This implies

######  Theorem C.

([13]) The number of perfect matchings in an $r$-regular bipartite graph with
$n$ vertices in each part is at most $(r!)^{n/r}$.

Let $\mathfrak{m}(n,r)$ and $\mathfrak{M}(n,r)$ denote the minimum and the
maximum of the number of perfect matchings in an $r$-regular bipartite graph
with $n$ vertices in each part. Theorems B and C can be written as

$n!(r/n)^{n}\leq\mathfrak{m}(n,r)\leq\mathfrak{M}(n,r)\leq(r!)^{n/r}.$

We are now ready to prove Theorem 5.

###### Proof of Theorem 5.

We use the Sudoku rectangle completion procedure of Section 3 to build a
Sudoku square row-block by row-block, and count the number of ways each row-
block can be completed. Assume we are at a stage that $l-1$ row-blocks are
completed, and we want to count the number of ways the $l$th row-block can be
completed.

To complete the $l$th row-block, we first process the blocks in this row-block
one by one, and for each block, solve a matching problem to assign an
unordered set of $k$ elements to each column, in such a way that each element
is assigned to only one column within the block, and an element that is
assigned to a column does not appear in the first $(l-1)$ row-blocks in that
column. In the proof of Theorem 1, we did this by formulating an assignment
problem with $n$ vertices (corresponding to the elements) on one side and $k$
vertices (corresponding to the columns) on the other side, and finding an
assignment that assigns $k$ elements to each column. To count the number of
such assignments, we formulate this as a matching problem by replacing each
column vertices by $k$ copies. The assignments in the original graph
correspond to perfect matchings in this new graph. This graph has $n$ vertices
on each side and is $(n-k(l-1))$-regular. Therefore, the number of perfect
matchings in this graph is bounded from below and above by
$\mathfrak{m}(n,n-k(l-1))$ and $\mathfrak{M}(n,n-k(l-1))$. For each column,
since the ordering of which element is assigned to which copy of that column
graph is not important, the number should be divided by $k!$. This means that
the total number of assignments of $k$ elements to each column, for each block
in this row-block, is between

$\frac{\mathfrak{m}(n,n-k(l-1))}{(k!)^{k}}\qquad\mbox{and}\qquad\frac{\mathfrak{M}(n,n-k(l-1))}{(k!)^{k}}.$

The total number of assignments for all blocks of this row-block is the above
value raised to the power $k$.

Next, we count the number of ways each of the $k$ elements assigned to the
column can be assigned to the $k$ rows of this column in a way that no row
contains repeated elements. We do this row by row, by constructing a matching
problem for each row. For the first row of the row-block, the graph consists
of $n$ nodes corresponding to the $n$ elements on one side and $n$ nodes
corresponding to the $n$ columns on the other side. Each column node is
connected by an edge to each of the $k$ elements assigned to it in the first
stage. It is easy to see that this is a $k$-regular graph. Each perfect
matching in this graph gives a way to assign elements to the first row of the
$l$th row-block. The number of such perfect matchings is between
$\mathfrak{m}(n,k)$ and $\mathfrak{M}(n,k)$. For the next row, we have the
same graph, except the element already assigned to the first row is no longer
connected to the corresponding column. The graph is $(k-1)$-regular, and has
between $\mathfrak{m}(n,k-1)$ and $\mathfrak{M}(n,k-1)$ perfect matchings.
Continuing this process, we show that the number of ways to assign the
elements to rows in this row-block is between

$\mathfrak{m}(n,k)\cdot\mathfrak{m}(n,k-1)\cdots\mathfrak{m}(n,1)\qquad\mbox{and}\qquad\mathfrak{M}(n,k)\cdot\mathfrak{M}(n,k-1)\cdots\mathfrak{M}(n,1).$

To obtain a minimum and maximum for the total number of Sudoku squares, we
multiply the above values for all $l=1,\ldots,k$. This gives the following
bounds on the total number of Sudoku squares of order $n$:

${\mathrm{Sud}}(n)\geq\prod_{l=1}^{k}\left[\frac{\mathfrak{m}(n,n-k(l-1))}{(k!)^{k}}\right]^{k}\cdot\left(\prod_{r=1}^{k}\mathfrak{m}(n,r)\right)^{k}.$
(1)

${\mathrm{Sud}}(n)\leq\prod_{l=1}^{k}\left[\frac{\mathfrak{M}(n,n-k(l-1))}{(k!)^{k}}\right]^{k}\cdot\left(\prod_{r=1}^{k}\mathfrak{M}(n,r)\right)^{k}.$
(2)

Using Theorem B and inequality (1), we have:

$\displaystyle{\mathrm{Sud}}(n)$ $\displaystyle\geq$
$\displaystyle\prod_{l=1}^{k}\left[\frac{n!(n-k(l-1))^{n}}{k!^{k}n^{n}}\right]^{k}\cdot\left(\prod_{r=1}^{k}(n!(r/n)^{n})\right)^{k}$
$\displaystyle=$ $\displaystyle\frac{n!^{n}}{k!^{kn}\cdot
k^{n^{2}}}\prod_{l=1}^{k}(k-(l-1))^{kn}\cdot\frac{n!^{n}}{n^{n^{2}}}\prod_{r=1}^{k}r^{kn}$
$\displaystyle=$ $\displaystyle\frac{n!^{n}k!^{kn}}{k!^{kn}\cdot
k^{n^{2}}}\cdot\frac{n!^{n}k!^{kn}}{n^{n^{2}}}$ $\displaystyle=$
$\displaystyle\frac{n!^{2n}k!^{kn}}{k^{n^{2}}n^{n^{2}}}.$

Using Stirling’s formula, we have $n!>(n/e)^{n}$ and $k!>(k/e)^{k}$.
Therefore,

${\mathrm{Sud}}(n)\geq\frac{n^{2n^{2}}e^{-2n^{2}}k^{n^{2}}e^{-n^{2}}}{k^{n^{2}}n^{n^{2}}}=(n/e^{3})^{n^{2}}.$

Similarly, using Theorem C and inequality (2), we have:

$\displaystyle{\mathrm{Sud}}(n)$ $\displaystyle\leq$
$\displaystyle\prod_{l=1}^{k}\left[\frac{(n-k(l-1))!^{n/(n-k(l-1))}}{(k!)^{k}}\right]^{k}\cdot\left(\prod_{r=1}^{k}r!^{n/r}\right)^{k}.$

We use the following extension of Stirling’s formula [5] that holds for every
$x$:

$x!<(x/e)^{x}\sqrt{2\pi x}\cdot e^{1/(12x)}.$

For $x\geq 1$, $\sqrt{2\pi}\cdot e^{1/(12x)}<3$, and therefore,
$x!<3(x/e)^{x}\sqrt{x}$. Using this inequality, we have:

$\displaystyle{\mathrm{Sud}}(n)$ $\displaystyle\leq$
$\displaystyle\frac{1}{k!^{kn}}\prod_{l=1}^{k}(n-k(l-1))!^{kn/(n-k(l-1))}\cdot\prod_{r=1}^{k}r!^{kn/r}$
$\displaystyle<$
$\displaystyle\frac{1}{k!^{kn}}\prod_{l=1}^{k}\left(3\left(\frac{n-k(l-1)}{e}\right)^{n-k(l-1)}\sqrt{n-k(l-1)}\right)^{kn/(n-k(l-1))}\cdot\prod_{r=1}^{k}\left(3(r/e)^{r}\sqrt{r}\right)^{kn/r}$
$\displaystyle=$
$\displaystyle\frac{1}{k!^{kn}}\prod_{l=1}^{k}\left(\frac{k(k-(l-1))}{e}\right)^{kn}\cdot\prod_{l=1}^{k}\left(3\sqrt{n-k(l-1)}\right)^{n/(k-(l-1))}\cdot\prod_{r=1}^{k}\left(r/e\right)^{kn}\cdot\prod_{r=1}^{k}\left(3\sqrt{r}\right)^{kn/r}$
$\displaystyle=$
$\displaystyle\frac{k^{n^{2}}k!^{kn}}{k!^{kn}e^{n^{2}}}\cdot\prod_{r=1}^{k}\left(3\sqrt{rk}\right)^{n/r}\cdot\frac{k!^{kn}}{e^{n^{2}}}\cdot\prod_{r=1}^{k}\left(3\sqrt{r}\right)^{kn/r}$
$\displaystyle=$
$\displaystyle\frac{k^{n^{2}}k!^{kn}}{e^{2n^{2}}}\cdot\prod_{r=1}^{k}\left((9r)^{1+k}k\right)^{n/(2r)}$
$\displaystyle<$
$\displaystyle\frac{k^{n^{2}}(3(k/e)^{k}\sqrt{k})^{kn}}{e^{2n^{2}}}\cdot\prod_{r=1}^{k}\left((9r)^{1+k}k\right)^{n/(2r)}$
$\displaystyle=$
$\displaystyle\frac{n^{n^{2}}}{e^{3n^{2}}}\cdot(3\sqrt{k})^{kn}\cdot\prod_{r=1}^{k}\left((9r)^{1+k}k\right)^{n/(2r)}.$

Therefore,

$({\mathrm{Sud}}(n))^{1/n^{2}}<\frac{n}{e^{3}}\cdot(3\sqrt{k})^{1/k}\cdot\prod_{r=1}^{k}\left((9r)^{1+k}k\right)^{1/(2rn)}.$
(3)

All that remains is to prove that
$(3\sqrt{k})^{1/k}\cdot\prod_{r=1}^{k}\left((9r)^{1+k}k\right)^{1/(2rn)}=1+o(1)$.
We use the inequality that for $x<1$, $e^{x}<1+2x$. Therefore,

$(3\sqrt{k})^{1/k}=e^{\frac{\ln(3\sqrt{k})}{k}}<1+\frac{2\ln(3\sqrt{k})}{k}=1+o(1).$
(4)

Also, using the bound $\sum_{r=1}^{k}\frac{1}{r}<1+\ln(k)$ on the harmonic
series, we obtain

$\displaystyle\prod_{r=1}^{k}\left((9r)^{1+k}k\right)^{1/(2rn)}$
$\displaystyle<$
$\displaystyle\prod_{r=1}^{k}\left((9k)^{1+k}k\right)^{1/(2rn)}$ (5)
$\displaystyle<$
$\displaystyle\prod_{r=1}^{k}\left((9k)^{2k}\right)^{1/(2rn)}$
$\displaystyle=$ $\displaystyle(9k)^{\frac{1}{k}\sum_{r=1}^{k}\frac{1}{r}}$
$\displaystyle<$ $\displaystyle(9k)^{\frac{1+\ln(k)}{k}}$ $\displaystyle=$
$\displaystyle\exp\left(\frac{1+\ln(k)}{k}\ln(9k)\right)$ $\displaystyle<$
$\displaystyle 1+2\cdot\frac{1+\ln(k)}{k}\ln(9k)=1+o(1).$

Putting together Equations (3), (4), and (5), we obtain:

$({\mathrm{Sud}}(n))^{1/n^{2}}<\frac{n}{e^{3}}(1+o(1)),$

as desired. ∎

## Acknowledgements

Part of the research of the second author was done while he was visiting
professor Delaram Kahrobaee at the Graduate Center of City University of New
York. He thanks for the hospitality during his visit.

## References

  * [1] R. A. Bailey, Peter J. Cameron, and Robert Connelly.  Sudoku, Gerechte designs, resolutions, affine space, spreads, reguli, and Hamming codes.  Amer. Math. Monthly, 115(5):383–404, 2008.
  * [2] J. A. Bondy and U. S. R. Murty.  Graph theory, volume 244 of Graduate Texts in Mathematics.  Springer, New York, 2008.
  * [3] Joshua Cooper and Anna Kirkpatrick.  Critical sets for Sudoku and general graph colorings.  Discrete Math., 315:112–119, 2014.
  * [4] Bertram Felgenhauer and Frazer Jarvis.  Mathematics of Sudoku I.  Mathematical Spectrum, 39:15 , 22, 2006.
  * [5] William Feller.  An introduction to probability theory and its applications. Vol. I.  Third edition. John Wiley & Sons, Inc., New York-London-Sydney, 1968\.
  * [6] Marshall Hall.  An existence theorem for Latin squares.  Bull. Amer. Math. Soc., 51:387–388, 1945.
  * [7] Antal Iványi and Zsolt Németh.  List coloring of Latin and Sudoku graphs.  In 8th Joint Conference on Mathematics and Computer Science—MaCS 2010, pages 23–34. NOVADAT Ltd., Győr, 2011.
  * [8] Izabela Kanaana and Bala Ravikumar.  Row-filled completion problem for Sudoku.  Util. Math., 81:65–84, 2010.
  * [9] Hung-Hsuan Lin and I-Chen Wu.  Solving the minimum Sudoku problem.  Technologies and Applications of Artificial Intelligence (TAAI), 2010 International Conference on, 315:456–461, 2010.
  * [10] Gary McGuire, Bastin Tugemann, and Gilles Civario.  There is no 16-clue Sudoku: Solving the Sudoku minimum number of clues problem.  CoRR, abs/1201.0749, 2012.
  * [11] Ryan M. Pedersen and Timothy L. Vis.  Sets of mutually orthogonal Sudoku Latin squares.  College Math. J., 40(3):174–180, 2009.
  * [12] Yato Takayuki and Seta Takahiro.  Complexity and completeness of finding another solution and its application to puzzles.  IEICE transactions on fundamentals of electronics, communications and computer sciences, 86(5):1052–1060, 2003.
  * [13] J. H. van Lint and R. M. Wilson.  A course in combinatorics.  Cambridge University Press, Cambridge, second edition, 2001.
  * [14] Daniel Willams.  The detection of unavoidable sets in Sudoku grids of different sizes.  Technical report, University of Glomorgan, April 4 2011.