When Natural Variables Are Not Enough: Teaching Integer Programming with Sudoku
Aled Williams Department of Computer Science Royal Holloway, University of London London, UK [email protected] · 2026
Read When Natural Variables Are Not Enough: Teaching Integer Programming with Sudoku by Aled Williams Department of Computer Science Royal Holloway, University of London London, UK [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30227.txt.
Introduction
Aled Williams uses Sudoku to teach a modelling lesson about integer programming choices. Students naturally assign one integer variable to each Sudoku cell. That natural model then needs an all-different rule for every row, column, and block. Expressing all-different with linear constraints proves surprisingly awkward. The paper contrasts it with the less intuitive assignment formulation.
The alternative uses binary variables for digit-cell assignments. Puzzle rules then become simple assignment constraints in that model. It also extends easily to variants like Killer Sudoku. The natural cell-value model needs many pairwise disjunctions instead. Big-M inequalities linearize those disjunctions at considerable size cost. AMPL code is provided for both formulations. A second integer program certifies that a puzzle's solution is unique. Generalized Sudoku also opens a careful door into computational complexity.
Catalog record
| CREATOR | Aled Williams Department of Computer Science Royal Holloway, University of London London, UK [email protected] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30227
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When Natural Variables Are Not Enough: Teaching Integer Programming with Sudoku Aled Williams Department of Computer Science Royal Holloway, University of London London, UK [email protected] Abstract Sudoku is a compact and familiar setting for teaching a surprisingly deep lesson in integer linear programming, namely that the most natural decision variables are not always enough to produce an effective or convenient linear model. This paper compares two formulations of Sudoku. The first uses binary assignment variables indicating whether a particular digit is assigned to a particular cell. This formulation is less natural from the perspective of the puzzle board itself, but it encodes the puzzle rules through simple assignment constraints and extends easily to variants such as Killer Sudoku. The second formulation uses the more natural approach of assigning one integer variable to represent the value in each cell, but then the central requirement is that the values in each row, column, and block must be all different. When this all-different requirement must be expressed using linear constraints while retaining the cell-value variables, the formulation becomes a large collection of pairwise disjunctions linearised by big- M M inequalities. The paper includes AMPL code for both the assignment model and the natural all-different model, and derives a second integer program for certifying uniqueness. The paper also uses generalised Sudoku as a careful entry point to computational complexity, while emphasising that the standard nine-by-nine puzzle is not itself an asymptotic problem class. Keywords : integer programming, optimisation education, mathematical modelling, Sudoku, operations research, formulation choice, AMPL. 1 Introduction Sudoku has been used as a classroom example in operations research and integer programming because its rules are simple to state, readily illustrated on a familiar puzzle grid, and naturally lead to combinatorial decision models. Chlond [ 2 ] presents Sudoku as one of two classroom drill exercises in integer programming modelling, using a five-index binary formulation and an Xpress-Mosel implementation. Weiss and Rasmussen [ 10 ] revisit the puzzle from a spreadsheet-modelling perspective, using a three-index binary assignment formulation and showing how it can be implemented and solved in Microsoft Excel. These contributions show that a familiar recreational puzzle can provide an accessible setting in which students encounter binary variables, assignment constraints, and modelling software. This paper builds on previous work by making the contrast between natural and effective formulations its main pedagogical focus. In particular, when students first encounter the puzzle, the most literal modelling choice is often to assign one integer variable to each cell, thereby mirroring the puzzle board directly. The difficulty is not in defining these variables, but in expressing the Sudoku rules as linear constraints. The modelling challenge is to ensure that every row, every column, and every block contains distinct values. In other words, the central requirement is an all-different condition, not simply a condition on the sum of the entries. This tension between variables that mirror the puzzle directly and variables that simplify the constraints creates a useful basis for classroom discussion about formulation choice. This tension highlights an important principle in integer programming, namely that variables that provide the most natural description of a problem are not always those that yield the simplest or most effective linear formulation. The aim of this paper is not merely to show that Sudoku can be solved by integer programming, but to show why variables that describe the solution directly need not lead to the most effective linear formulation. We first develop the standard binary assignment formulation. We then consider the natural cell-value formulation and examine the linearisation required to model the all-different relation. We also show how the assignment variables support uniqueness certification and Killer Sudoku constraints, and how AMPL can express the natural model through its alldiff operator. Finally, we outline how generalised Sudoku can be used as a careful classroom entry point into \mathcal{NP} -completeness. 2 The Binary Assignment Formulation The most widely used integer programming formulation for Sudoku does not model the value written in each cell directly. Instead, it records which digits are assigned to which cells. This formulation is not the most literal representation of the board, but it provides a clean linear representation of the digit-placement decisions underlying the puzzle. Let N=\{1,2,\ldots,9\} , and use this notation throughout the paper. For each cell (i,j)\in N\times N and digit k\in N , we define the binary variable x_{ijk}=\begin{cases}1,&\text{if digit }k\text{ is placed in cell }(i,j),\\ 0,&\text{otherwise.}\end{cases} The model therefore contains 9^{3}=729 binary variables, each representing a possible assignment of a digit to a cell. The Sudoku rules can now be expressed as linear constraints. The requirement that every digit must appear exactly once in each column can be modelled by \sum_{i\in N}x_{ijk}=1\qquad\text{for every }j,k\in N. Similarly, every digit must appear exactly once in each row, which is enforced by \sum_{j\in N}x_{ijk}=1\qquad\text{for every }i,k\in N. Each digit must also appear exactly once in every 3\times 3 block. Let a,b\in\{1,4,7\} index the upper-left corners of the blocks, then this condition can be modelled via \sum_{q=0}^{2}\sum_{r=0}^{2}x_{a+q,\,b+r,\,k}=1\qquad\text{for every }a,b\in\{1,4,7\}\text{ and }k\in N. Finally, each cell of the Sudoku grid must contain exactly one digit, which yields the constraints \sum_{k\in N}x_{ijk}=1\qquad\text{for every }i,j\in N. Recall that, before incorporating the given clues, the assignment formulation outlined above contains 9^{3}=729 binary variables and 4\cdot 81=324 equality constraints, corresponding to the column, row, block, and cell constraints. Although the number of variables is considerably larger than the 81 cells of the puzzle, the benefit is that every Sudoku rule is represented by a simple linear equality. Given clues are incorporated naturally. In particular, if the puzzle specifies that cell (i,j) contains the digit g_{ij}\in N , then this can be imposed simply by fixing x_{ijg_{ij}}=1 . Observe that Sudoku is fundamentally a feasibility problem, and no objective function is required. In AMPL or other modelling software, one may use a dummy objective such as minimising 0 if needed. If desired, the corresponding cell values can be recovered from the binary solution via z_{ij}=\sum_{k\in N}k\,x_{ijk}, where z_{ij}\in N denotes the value in the cell (i,j) . This observation is important pedagogically. The binary variables do not discard the natural cell values, but instead represent each possible assignment of a digit to a cell separately. Importantly, although this formulation introduces substantially more variables than there are cells in the puzzle, the resulting model consists entirely of simple linear equalities. This makes the formulation particularly attractive for implementation in standard integer programming software. 2.1 Implementing the Assignment Model in AMPL The three-index assignment formulation is compact enough to be presented directly to students as an AMPL model. The following implementation uses sets of cell coordinates for each 3\times 3 block, allowing the block constraints to mirror the row and column constraints. Before giving the AMPL code, it is useful to note how the mathematical notation given above maps onto the implementation. The set VALUES corresponds to the digit set N , while ROWS and COLUMNS index the cell positions. The binary variable assign[i,j,v] is the AMPL counterpart of x_{ijv} . The four families of constraints in the algebraic model appear directly as row_sum , col_sum , block_sum , and one_value . The constraint family initial_value fixes the variables corresponding to the given clues. set ROWS