The Journal of Online Mathematics and Its Applications, Volume 8 (2008)
Integer Programming Model for the Sudoku Problem, Bartlett, Chartier, Langville, Rankin

4. Question 2: Creating the Puzzles

We now turn to the question: how might Sudoku puzzles be created? Should our Sudoku puzzle have a unique solution? According to (Gordon et al., 2006), the answer is yes. A simple search on your favorite search engine will also show that many web sites related to puzzle design agree. However, armed with the BILP from this paper, one can occasionally verify, for instance with the Matlab program sudoku.m, that not all Sudoku puzzles that are posted have unique solutions. One can stumble across such examples when the BILP's computed solution is distinct from the solution provided by the puzzle creators.

4.1. Creating Puzzles by Brute Force

A first approach to creating Sudoku puzzles is to use brute force. One simple idea fills each element of the 9 \times 9 matrix with a randomly chosen integer from 1 to 9, then checks to see if the resulting matrix satisfies the three Sudoku properties concerning rows, columns, and submatrices. This approach creates 9^{81} \approx 1.97 \times 10^{77} different matrices that require checking. Just how many of these would satisfy the Sudoku properties? In other words, how many feasible 9\times 9 Sudoku matrices are there (i.e., matrices satisfying constraints (1)-(4) of the BILP of Section 2.1)?

First, note that a 9 \times 9 Latin square consists of sets of the numbers 1 to 9 arranged in such a way that no row or column contains the same number twice. Therefore, every Sudoku puzzle is a special case of a 9 \times 9 Latin square of which there are 5,524,751,496,156,892,842,531,225,600 \approx 5.525 \times 10^{27} (Bammel et al., 1975). How many of these Latin squares are Sudoku matrices?

The answer to this question was provided by Felgenhauer and Jarvis in 2005. The number of Sudoku matrices for the standard 9\times 9 game was calculated to be 6,670,903,752,021,072,936,960 \approx 6.67 \times 10^{21} (Felgenhauer et al.). This number is equal to 9! \times 72^2 \times 2^7 \times 27,704,267,971, the last factor being prime. The result was derived through logic and brute force computation. (Note that only about .00012\% of 9\times 9 Latin squares are valid Sudoku puzzles.) Later Russell and Jarvis (Russell et al.) showed that when symmetries were taken into account, there were, of course, many fewer solutions; 5,472,730,538 to be exact.

Given that Sudoku matrices can be created by a brute force technique, assume we stop as soon as we find one. With a full Sudoku matrix in hand, we could then simply omit entries to create a puzzle. At this point, the question becomes how to do the omitting so that a proper Sudoku puzzle results. Specifically, we pose the following mathematical questions.

  1. What is the minimum number of givens required to create a puzzle with a unique solution?
  2. How does this relate to the positions of the givens?
  3. Given a puzzle with a unique solution, is there a way to create other related puzzles with unique solutions?

A literature review leads to some answers.

  1. In general, the problem of the minimum number of givens required to create a puzzle with a unique solution is unsolved---at least, theoretically. Experimentally, however, much progress has been made. Algebraic graph theorist Gordon Royle has created a solvable 9 \times 9 puzzle with as few as 17 givens. (In fact, he has found 35,396 distinct such puzzles (Royle).) To date, no puzzle with 16 or less givens, which in turn produces a unique solution, has been discovered. Note that Nikoli, the Japanese publisher mentioned in Section 1, added two conditions to the puzzles. First, no more than 30 numbers could be given at the start with more numbers generally leading to an easier puzzle. The second rule will be addressed below in the comment on the second question.

    Figure 7. Sudoku Symmetry Test

    The publisher Nikoli set the rule that Sudoku puzzles should have symmetry as demonstrated in the Figure 7 above. Enter a tableau or select the "default puzzle" button. By clicking the "rotate tableau" button, the entries in the puzzle are rotated 180^\circ. While the entries may change their numeric values, the rotated puzzle will have entries in only those elements that had entries in the puzzle before rotation.

  2. This question is very difficult to answer. Clearly, it is not solely the number of givens that determines a puzzle's difficulty. The position and values of the givens must also be considered. This question also leads to Nikoli's second rule for puzzles, where the first was addressed above. According to this rule, the pattern of digits must be symmetric. To explore this rule, enter a tableau or select the "default puzzle" button in the application in Figure 7. By clicking the "rotate tableau" button the entries in the puzzle are rotated 180^\circ. While the entries may change their numeric values, the rotated puzzle will have entries in only those elements that had entries in the puzzle before rotation. While not all Sudoku puzzles adhere to this constraint, many do. The reader may wish to verify that all the puzzles contained in this paper adhere to such symmetry. For these reasons, question two extends beyond the scope of this paper.
  3. We provide several answers to this question in the next section.

4.2. Creating New Puzzles from Old Puzzles

Our goal in this section is to create as many new Sudoku puzzles \bar{\mathbf{S}} from one original puzzle \mathbf{S}. A new Sudoku matrix is simply one such that \bar{\mathbf{S}}- \mathbf{S} \neq \mathbf{0}.

Definition 1

A square matrix \mathbf{S} is a Sudoku matrix, if the following four conditions hold.

  1. The order of the matrix n is such that n=m^2, where m is any positive integer.
  2. Every row in \mathbf{S} uses the integers 1 through n exactly once.
  3. Every column in \mathbf{S} uses the integers 1 through n exactly once.
  4. Every submatrix in \mathbf{S} uses the integers 1 through n exactly once.

Theorem 4.1

If \mathbf{S} is a Sudoku matrix, then \mathbf{S}^T is also a Sudoku matrix.

Proof

Transposition interchanges the rows and columns of a matrix, so that [\mathbf{S}^T]_{ij} = [ \mathbf{S}]_{ji}. Since, \mathbf{S} is n \times n, \mathbf{S}^T is n \times n, and clearly Property 1 of the Sudoku matrix definition is satisfied. Property 2 (Property 3) is satisfied for \mathbf{S}^T by virtue of the fact that Property 3 (Property 2) is satisfied by \mathbf{S}. It remains to show that \mathbf{S}^T satisfies Property 4. Without loss of generality (w.l.o.g.) , let m=2. Then in block form, where each block is 2 \times 2,

\mathbf{S} = \left( \begin{array}{cc} \mathbf{S}_{11} & \mathbf{S}_{12} \\ \mathbf{S}_{21} & \mathbf{S}_{22} \\ \end{array} \right), \quad \text{and} \quad \mathbf{S}^T = \left( \begin{array}{cc} \mathbf{S}^T_{11} & \mathbf{S}^T_{21} \\ \mathbf{S}^T_{12} & \mathbf{S}_{22} \\ \end{array} \right).

Each submatrix of \mathbf{S}^T satisfies Property 4 because each submatrix of \mathbf{S}^T is created from a submatrix of \mathbf{S}, which by assumption satisfies Property 4.

Theorem 4.1 allows just one way to create a new Sudoku matrix from an old one. Our next theorem does much better, creating many new puzzles. Exactly how many is left as an exercise.

Theorem 4.2

If \mathbf{S} is a Sudoku matrix, then a new Sudoku matrix \bar {\mathbf{S}} can be created by block reordering the rows and columns of \mathbf{S} (i.e., only rows and columns within the same submatrix block can be permuted).

Proof

Without loss of generality, let m=2. Then the permissible block row and column reordering can be described by the matrix operation

\bar{\mathbf{S}} = \left( \begin{array}{cc} \mathbf{E}_1 & \\ & \mathbf{E}_{2} \\ \end{array} \right)\left( \begin{array}{cc} \mathbf{S}_{11} & \mathbf{S}_{12} \\ \mathbf{S}_{21} & \mathbf{S}_{22} \\ \end{array} \right)\left( \begin{array}{cc} \mathbf{F}_{1} & \\ & \mathbf{F}_{2} \\ \end{array} \right) = \left( \begin{array}{cc} \mathbf{E}_1\mathbf{S}_{11}\mathbf{F}_1 & \mathbf{E}_1\mathbf{S}_{12}\mathbf{F}_2 \\ \mathbf{E}_2\mathbf{S}_{21}\mathbf{F}_1 & \mathbf{E}_2\mathbf{S}_{22}\mathbf{F}_2 \\ \end{array} \right),\qquad (7)

where \mathbf{E}_i and \mathbf{F}_i are permutation matrices that result in elementary row (or column) interchanges applied to the 2 \times 2 identity matrix. \bar{\mathbf{S}} satisfies Property 1 because block reordering does not affect the size of the matrix. To show \bar{\mathbf{S}} satisfies Property 2, w.l.o.g. consider the ith row of the first block row of \bar{\mathbf{S}}.

\mathbf{e}_i^T \left( \begin{array}{cc} \mathbf{E}_1 \mathbf{S}_{11}\mathbf{F}_1 & \mathbf{E}_1 \mathbf{S}_{12}\mathbf{F}_2 \end{array}\right) = \mathbf{e}_i^T \mathbf{E}_1 \left( \begin{array}{cc} \mathbf{S}_{11}\mathbf{F}_1 & \mathbf{S}_{12}\mathbf{F}_2 \end{array} \right).

Consider the last expression in the above equation. The matrix \left(\begin{array}{cc} \mathbf{S}_{11} \mathbf{F}_1 & \mathbf{S}_{12}\mathbf{F}_2\end{array}\right) is the first block row of \mathbf{S} with its columns permuted, and \mathbf{e}_i^T \mathbf{E}_1 corresponds to one particular row in that matrix. Because the rows of \mathbf{S} satisfy Property 2, then the particular row in question in \bar {\mathbf{S}} satisfies Property 2. (Permutation of a vector does not affect Property 2 or Property 3.) By considering the transpose, the same argument holds for Property 3.

It remains to show that \bar {\mathbf{S}} satisfies Property 4. The block reordering restriction is required to insure that \bar {\mathbf{S}} satisfies Property 4; cross-block reorderings destroy Property 4. From Equation (7), it is easy to see that each submatrix of \bar{\mathbf{S}} satisfies Property 4 since it is a simple row and column permutation of the corresponding submatrix of \mathbf{S}, which satisfies Property 4 by assumption.

Exercise 7

How many new Sudoku matrices can be created from an original matrix when block reordering is used? (Hint: Try some 4 \times 4 examples with the allowable reordering described above and look for counting patterns.) (Solution)

Theorem 4.3

If \mathbf{S} is a Sudoku matrix, then a new Sudoku matrix \bar {\mathbf{S}} can be created by relabeling the integers in \mathbf{S}. That is, there is a one-to-one mapping between the integers \alpha =(1, \ldots, n) used to create \mathbf{S} and the permutation \beta of these same integers used to create \bar {\mathbf{S}}.

Proof

(By Contradiction.) Assume \alpha \neq \beta, but \bar{\mathbf{S}} is not a new Sudoku matrix. Clearly Property 1 still holds. Suppose Property 2 fails. Therefore, there exists a row in \bar{\mathbf{S}} that repeats an integer. Thus, the mapping of integers from \alpha to \beta is not one-to-one, which contradicts the one-to-one mapping requirement. Therefore, \bar{\mathbf{S}} must be a new Sudoku matrix. A similar argument shows that neither Property 3 nor Property 4 can fail to hold.

Example

The n=4 Sudoku matrix \mathbf{S} is used by create a new matrix \bar{\mathbf{S}} under the permutation \beta = \pmatrix{4 & 1 & 3 & 2} of \alpha = \pmatrix{1 & 2 & 3 & 4}.

\begin{eqnarray} \mathbf{S} = \pmatrix{1&2& 3 & 4\cr 4& 3& 2 & 1\cr 3& 1& 4 & 2\cr 2& 4& 1 & 3\cr} \quad \mbox{and} \quad \bar{\mathbf{S}} = \pmatrix{4&1&3 & 2\cr 2&3&1 & 4\cr 3&4&2 & 1\cr 1&2&4 & 3\cr}. \end{eqnarray}

Exercise 8

How many new Sudoku matrices can be created from an original matrix when relabeling is used? (Solution)

Challenge

Can you think of other ways to create new puzzles from one original Sudoku matrix?