NP-completeness of SUDOKU

Here is how it works (simplified, without reference to ASP-completeness, which I don’t cover in this course).

Suppose we have a n×n instance of LATIN SQUARE COMPLETION. We construct a n²×n² instance of SUDOKU, that encodes the instance of LATIN SQUARE COMPLETION. Moreover, the encoding is very direct.

Let’s do an example with n=4, and it will be clear how to generalize. Suppose the instance of LATIN SQUARE COMPLETION looks like this:

4 3 2 4 2 1

Recall that a n×n Latin square is a n×n grid that contains n occurrences of each number in the range 1–n, such that no row or column contains two occurrences of the same number. LATIN SQUARE COMPLETION is the problem of filling in the blank entries so as to obtain a Latin square.

Here is the corresponding instance of SUDOKU. What we did is, copy each column of the LATIN SQUARE COMPLETION instance into the first columns of the top row of squares in the SUDOKU instance. Then we filled up the rest of the SUDOKU instance with the other numbers (in the range 5–16) so that the problem of completing the SUDOKU is the same as the problem of completing the original Latin square.

In giving a general rule for constructing a n²×n² instance of SUDOKU from an n×n instance of LATIN SQUARE COMPLETION, the main thing to be checked is that there is a polynomial-time computable way of filling in the “idle” squares with the numbers n+1 through n². That is left as an exercise; it is not hard to check.

4 5 9 13 6 10 14 7 11 15 1 8 12 16	8 12 16 2 5 9 13 6 10 14 7 11 15	7 11 15 8 12 16 4 5 9 13 6 10 14	3 6 10 14 7 11 15 2 8 12 16 5 9 13
13 1 5 9 14 2 6 10 15 3 7 11 16 4 8 12	16 4 8 12 13 1 5 9 14 2 6 10 15 3 7 11	15 3 7 11 16 4 8 12 13 1 5 9 14 2 6 10	14 2 6 10 15 3 7 11 16 4 8 12 13 1 5 9
9 13 1 5 10 14 2 6 11 15 3 7 12 16 4 8	12 16 4 8 9 13 1 5 10 14 2 6 11 15 3 7	11 15 3 7 12 16 4 8 9 13 1 5 10 14 2 6	10 14 2 6 11 15 3 7 12 16 4 8 9 13 1 5
5 9 13 1 6 10 14 2 7 11 15 3 8 12 16 4	8 12 16 4 5 9 13 1 6 10 14 2 7 11 15 3	7 11 15 3 8 12 16 4 5 9 13 1 6 10 14 2	6 10 14 2 7 11 15 3 8 12 16 4 5 9 13 1

Paul W. Goldberg