NPcompleteness of SUDOKU
This result was first shown in this
master’s thesis by reduction from the NPcomplete
problem LATIN SQUARE COMPLETION.
Sudoku wikipedia page.
Here is how it works (simplified, without reference to ASPcompleteness,
which I don’t cover in this course).
Suppose we have a n×n instance of LATIN SQUARE COMPLETION.
We construct a n^{2}×n^{2}
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:

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^{2}×n^{2} instance of SUDOKU from an
n×n instance of LATIN SQUARE COMPLETION, the main thing
to be checked is that there is a polynomialtime computable way of
filling in the “idle” squares with the numbers n+1 through
n^{2}. 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 



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