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

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

Given the popularity of Sudoku puzzles, variations on the traditional puzzle have emerged. One colorful, extensive source of puzzles is authored by Riley and Taalman in (Riley, 2007). In this section, we formulate a BILP for each of several puzzles that are contained in this book. Each puzzle contains the same set of constraints on a solution as a traditional Sudoku but also imposes one or more additional constraints. The authors thank Riley and Taalman for creating the puzzles in this paper.

All constraints needed for a traditional Sudoku puzzle would also be required for any puzzle which has the same set (plus additional) constraints as a traditional puzzle. Therefore, we are faced with creating the additional constraints that capture the additional requirements for the puzzle under consideration. This will be the goal for each puzzle below.

The "Sudoku X" puzzle is like the standard puzzle, with an extra requirement: the two long diagonals of the board must also contain each digit from 1 to 9 exactly once. Thus, any solution to the Sudoku X puzzle is also a solution to the standard Sudoku puzzle, but the converse is not the case. An example of a Sudoku X puzzle is given in Figure 3, where the elements along each long diagonal are colored in green. You may enter a Sudoku X puzzle into this figure or click the "default puzzle" button to see the default puzzle. As you enter elements into the tableau, clicking the "violate constraints?" button results in a message indicating whether or not your entries have violated any of Sudoku X rules.

The only additional requirements of a Sudoku X puzzle are that the two long diagonals have exactly one of each digit. This results in 18 additional constraints (two diagonals with nine digits each).

To capture the requirement for the positive diagonal, we add the nine constraints

\sum_{r=1}^{9} x_{rrk} = 1, \ k=1:9.

That is, each number on the positive diagonal appears exactly once. Similarly, for the anti-diagonal, the following set of nine constraints are added

\sum_{r=1}^{9} x_{r(10-r)k}=1, \ k=1:9.

As a result of these two additional constraints, every digit must appear exactly once on each diagonal.

The "Four Square" Sudoku is again a standard puzzle but with an extra requirement. There are four shaded 3 \times 3 regions on the Sudoku board, and in addition to the requirements of the standard Sudoku, each shaded region must also contain each digit from 1 to 9 exactly once. A sample Four Squares puzzle is given in Figure 4.

In addition to the standard Sudoku constraints, the Four Square Sudoku puzzle requires that each shaded 3 \times 3 square contains each digit exactly once. This requirement results in 36 constraints on top of the standard constraints (4 squares, 9 digits). The constraints themselves look similar to the other constraints on the 3 \times 3 subgrids:

\sum_{r=i}^{i+2} \sum_{c=j}^{j+2} x_{rck}=1, \ i=2,6; \ j=2,6; \
{\rm ~and~} \ k=1:9.

Again, the choices of `i` and `j` determine the shaded square in question.

Like the Four Square variant, the "Four Pyramids" Sudoku is a standard Sudoku puzzle with four shaded regions, where one must ensure that each shaded region contains exactly one of each digit from 1 to 9 (in addition to satisfying the requirements of the standard Sudoku). As one can see in the example below, the shaded regions are shaped somewhat like pyramids, giving this variant its name.

Like the previous variant, the Four Pyramids variant adds 36 additional constraints to the standard ones. Each of the four pyramid-shaped shaded regions must contain each digit exactly once:

\sum_{r=1}^{3} \sum_{c=3+r}^{9-r} x_{rck}=1, \ k=1:9,

\sum_{c=1}^{3} \sum_{r=1+c}^{7-c} x_{rck}=1, \ k=1:9,

\sum_{r=7}^{9} \sum_{c=11-r}^{r-3} x_{rck}=1, \ k=1:9,

\sum_{c=7}^{9} \sum_{r=13-c}^{c-1} x_{rck}=1, \ k=1:9.

The four sums correspond to the four shaded regions in counterclockwise order, starting with the top pyramid. For example, in the first sum, when r=1, c varies from 4 to 8, when r=2, c goes from 5 to 7, and when r=3, c only takes the value of 6.

Other variants on a traditional Sudoku puzzle exist. We present two here as they will be used in the exercises below.

For each element in a "Position Sudoku" tableau, not only does one need to take into account the 3 \times 3 subgrid within which the element lies but also the element's position within the 3 \times 3 subgrid. In addition to satisfying the standard Sudoku requirements, a solution to the Position Sudoku must be such that exactly one of each digit from 1 to 9 is contained in the top left squares of all nine 3 \times 3 subgrids, exactly one of each digit is contained in the top middle squares of all subgrids, and so forth. In the sample puzzle found in Figure 6 (a), the set of squares on the board sharing any given color must contain each digit exactly once.

Unlike the previous variants, in a "Three Magic Sudoku," the actual value of the digits is important, not just the fact that they are distinct. In a solution to a Three Magic Sudoku puzzle, along with satisfying the requirements of the standard Sudoku, each shaded 3 \times 3 subgrid must also be a "magic square," where the three numbers in each column and in each row add up to the same number. The puzzle depicted in Figure 6 (b) is an example of a Three Magic Sudoku, but it is possible to create puzzles involving any number of magic squares, including the possibility of all nine subgrids being magic squares!

Formulate a BILP to solve the Position Sudoku puzzle in Figure 6 (a). Further, adapt the Matlab code sudoku.m to solve a Position Sudoku. (Solution)

Formulate a BILP to solve the Three Magic Sudoku puzzle in Figure 6 (b). Further, adapt the Matlab code sudoku.m to solve a Three Magic Sudoku. (Solution)

Formulate a BILP for another variation of the traditional Sudoku puzzle. You can find such variations in (Riley, 2007) or online sources such as Brainfreeze Puzzles and (Pegg, 2005).

**Warning**: Solving some of the puzzles as BILPs in Matlab may result in long solution times. You may wish to add a preprocessing step that identifies entries which can be determined with very simple logic from the givens in the initial matrix.