NP-completeness of SUDOKU

This result was first shown in this master’s thesis by reduction from the NP-complete problem LATIN SQUARE COMPLETION. Sudoku wikipedia page.

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 n2×n2 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
42
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 n2×n2 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 n2. That is left as an exercise; it is not hard to check.
459 13
61014
71115
181216
81216
25 913
61014
71115
71115
81216
45 913
61014
361014
71115
281216
5 913
1315 9
142610
153711
164812
164812
1315 9
142610
153711
153711
164812
1315 9
142610
142610
153711
164812
1315 9
91315
101426
111537
121648
121648
91315
101426
111537
111537
121648
91315
101426
101426
111537
121648
91315
5 9131
610142
711153
812164
812164
5 9131
610142
711153
711153
812164
5 9131
610142
610142
711153
812164
5 9131

Paul W. Goldberg