The Journal of Online Mathematics and Its Applications, Volume 8 (2008)

Integer Programming Model for the Sudoku Problem, Bartlett, Chartier, Langville, Rankin

You could first experiment with different objective function vectors in the `bintprog`

line of the m-file sudoku.m. Change the objective function vector from `zeros(n^3,1)`

to `ones(n^3,1)`

, and other uniform vectors. You would find that these other objective functions all give the same solution. After these experiments, you're ready to state a theorem and attempt the proof.

If \mathbf{x}^* is the optimal solution for the BILP in Section 2.1 with objective function given by \text{min } \mathbf{0}^T \mathbf{x}, then \mathbf{x}^* is also the optimal solution for the related problem that has the same constraints but different objective function given by \text{min } \alpha \, \mathbf{e}^T \mathbf{x}, where \mathbf{e} is the vector of all ones and \alpha is a scalar.

(By Contradiction.) Assume \mathbf{x}^* is an optimal, and therefore feasible, solution for the original BILP of Section 2.1 (called Problem A), but \mathbf{x}^* is not an optimal solution for the modified BILP with the new objective (called Problem B). Then there exists a feasible solution \mathbf{y} such that \alpha \, \mathbf{e}^T \mathbf{y} < \alpha\,\mathbf{e}^T \mathbf{x}^*, which implies \mathbf{e}^T (\mathbf{y}- \mathbf{x}^*) < 0. Because \mathbf{x}^* and \mathbf{y} are binary vectors made up of only 0s and 1s, this means that \mathbf{x}^* must have more nonzero elements than \mathbf{y}. Careful examination of the constraint set, which is the same for both BILPs, shows that a feasible solution must contain exactly n^2 elements that are 1. Since \mathbf{y} is a feasible solution with exactly n^2 elements equal to 1, then \mathbf{x}^* must have n^2+1 elements equal to 1, which implies \mathbf{x}^* is not feasible. This contradicts our initial assumption that \mathbf{x}^* is a feasible optimal solution to Problem A.

We can't say 29 exactly, due to potential double counting as subsequent givens are considered.

The solutions are:

\begin{eqnarray}
\pmatrix{1&2&3 & 4\cr
3&4&2 & 1\cr
2&1&4 & 3\cr
4&3&1 & 2\cr},
\quad
\pmatrix{1&2&3 & 4\cr
3&4&1 & 2\cr
2&1&4 & 3\cr
4&3&2 & 1\cr}, \text{ and}
\quad
\pmatrix{1&2&3 & 4\cr
3&4&1 & 2\cr
2&3&4 & 1\cr
4&1&2 & 3\cr}.
\end{eqnarray}

One can create 4 \times 4 Sudoku puzzles with 5 and 4 givens that have unique solutions. However, it is not possible to formulate a puzzle of this size with a unique solution that has only 3 givens. When placing givens, position is generally more important than the value of the given. A possible theorem related to this topic is:

The minimum number of givens in a 4 \times 4 Sudoku puzzle is 4.

A proof of this theorem is contained in (Taalman, 2007). This article also counts the number of 4 \times 4 puzzles. The process of enumerating such puzzles is designed to supply the reader with an overview of how Felgenhauer and Jarvis counted the number of 9 \times 9 Sudoku boards (see Section 4.1). Further, the article poses a variety of open questions in this field of recreational mathematics.

Position Sudoku comes with the extra requirement that all corresponding locations within the 3 \times 3 subgrids contain each digit exactly once. Since there are 9 possible locations and 9 possible digits, this leads to 9^2=81 constraints in addition to the standard ones. The constraints are as follows:

\sum_{a=0}^{2} \sum_{b=0}^{2} x_{(3a+i)(3b+j)k}=1, \ i=1,2,3; \
j=1,2,3; \ {\rm ~and~} \ k=1:9.

Here the choices of i and j determine the particular position in question of all the subgrids; for example, i=j=1 corresponds to the top left corner of each subgrid.

The constraints for Three Magic Sudoku are the most complicated of the ones covered in this paper since the value of each digit matters in addition to simply how many of each there are. In each shaded square, each row and each column must sum to the same amount. (For this particular puzzle, diagonals are not required to sum to the same number as well, though requiring this is an option.) It is not hard to see that the "magic number" to which each row and column must sum is 15. If we sum all the rows and all the columns of the 3 \times 3 square together, each number in the square is added twice, once for its row and once for its column. The sum of the natural numbers from 1 to 9 is 45, so the combined sum of all the rows and all the columns must be 2*45=90. Since there are three rows and three columns, dividing 90 by 6 will yield the sum of each row and each column, 15.

With the system of decision variables in use, x_{rck}=1 if and only if k is the digit that appears in the box in row r and column c. It follows that \sum_{k=1}^{9} kx_{rck} will produce the value of the digit in square (r,c): each summand will equal zero except for the one with the correct k, and then its value will be k*1 = k, the digit appearing in the square. Knowing this fact and that each row and column in the shaded squares must add to 15, we can formulate the constraints as follows (for the top right magic square).

Row sums:

\sum_{c=7}^{9} \sum_{k=1}^{9} kx_{rck} = 15, \ r = 1:3.

Column sums:

\sum_{r=1}^{3} \sum_{k=1}^{9} kx_{rck} = 15, \ c = 7:9.

The constraints for the other two magic squares are done similarly, with r and c both ranging from 4 to 6 for the middle square, and r ranging from 7 to 9 and c ranging from 1 to 3 for the lower left square. There are six constraints for each magic square, and there are three magic squares, leading to 18 constraints in addition to the standard ones. (It is possible to reduce these constraints down to 5 for each square instead of 6, by setting the second column sum equal to the first column sum, the third column sum equal to the first column sum, the first row sum equal to the first column sum, etc. However, doing this would most likely complicate the constraints enough to more than cancel out any gain in efficiency from having fewer constraints.)

There are m! possibilities to permute an m \times m identity matrix and m blocks that can be permuted. Counting both row and column permutations, this gives [(m!)^m]^2 different Sudoku matrices. Thus, Theorem 4.2 leaves [(m!)^m]^2-1 new Sudoku matrices that can be created from the original matrix. For m=3, that is 46,655 different puzzles!

Theorem 4.3 creates n!-1 new Sudoku matrices. For n=9, that is 362,879 new puzzles! Combining the three theorems in Section 4.2 with strategies for varying the number and location of givens creates an even larger number of puzzles.