Sudoku is a puzzle played on a 9x9 grid. The grid is also ruled into nine 3x3 blocks. The goal is to place the digits 1, 2, , 9 into squares so that each row contains one occurrence of each digit, each column contains one occurrence of each digit, and each 3x3 block contains one occurrence of each digit. The challenge comes from the fact that each puzzle includes some digits filled in in advance, and the solution must respect those prior placements.

a) Formulate an integer program to solve Sudoku puzzles. You might be tempted to define a variable xj = k to express the idea that digit k appears in position j in a list. A conceptual description of the constraint that each position in a list contains exactly one occurrence of each digit is known as all different. It turns out to be difficult to express the alldifferent constraint applied to variables that take on general integer values in a mathematical programming context. One alternative approach is to define a binary variable for each possible digit, so that xjk = 1 if digit k appears in position j. Then the alldifferent constraint can be expressed as for all k (each digit appears once) and for all j (each position gets one digit). Applying this idea to the Sudoku model leads to defining xijk = 1 if digit k appears in row I and column j, and 0 otherwise. Note that Sudoku puzzles should have unique solutions, so the objective can be a dummy.

b) Create an AMPL model to solve Sudoku problems using your constraints from part (a). One way to efficiently fix the variables that correspond to initial filled-in squares is to create a set of ordered triples PRESET in INDEX cross INDEX cross INDEX containing elements (I, j, k) where row I and column j contain digit k. Then include a constraint defined for (I, j, k) in PRESET that x[i, j, k] = 1.