MSc course: Foundations of Computer Science (original) (raw)

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 _n_2×_n_2instance 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:

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 polynomial-time 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.

Paul W. Goldberg