Technology Review March/April 2011 Problem 1

Consider the solution of any ordinary sudoku puzzle. What is the largest number of times that any fixed integer can appear on either of the two major diagonals? Show that this number can actually occur.

Solution:

Five. The major diagonal passes through five 3x3 squares, and each of those squares can only contain any fixed integer once. Thus the theoretical maximum is 5. The figure below shows that the number 9 can appear five times along the major diagonals.