  It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17
clues to have a unique solution. This paper investigates the more specific
question: given a particular completed Sudoku grid, what is the minimum number
of clues in any puzzle whose unique solution is the given grid? We call this
problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary
bilevel linear program, present a class of globally valid inequalities, and
provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids.
Using a general bilevel solver, we solve 95% of instances to optimality, and
show that the solution process benefits from the addition of a moderate amount
of inequalities. Finally, we extend the proposed model to other combinatorial
problems in which uniqueness of the solution is of interest.
