Is Sudoku NP-Complete? A Plain-English Answer

Yes, in its general form. Deciding whether an n²×n² sudoku grid (4×4, 9×9, 16×16, 25×25 and so on) can be completed is NP-complete, proven by Takayuki Yato and Takahiro Seta in 2003. The ordinary 9×9 puzzle is a single fixed size, so the theory does not make it hard for a computer: a simple program solves any 9×9 sudoku in a fraction of a second. NP-completeness describes how the difficulty grows as the grid gets bigger.

What NP-complete means, in plain English

A problem is in NP if a proposed answer can be checked quickly. Sudoku clearly qualifies: given a filled grid, you can confirm it in one pass over every row, column and box. A problem is NP-complete if it is in NP and at least as hard as every other problem in NP, which means a fast method for it would give a fast method for all of them. Nobody knows whether such fast methods exist. That open question, P versus NP, is one of the Clay Mathematics Institute's Millennium Prize Problems, with a $1 million prize.

For sudoku, NP-complete means that as the grid grows, every known general method needs, in the worst case, time that grows exponentially with the size of the grid. Hard instances of very large sudokus can defeat any known algorithm, even though typical 9×9 puzzles take a computer no time at all.

The proof: Yato and Seta, 2003

Yato and Seta studied the "another solution problem": given a puzzle and one solution, find a different one. They proved it is complete (in a strong sense they called ASP-completeness) for three Nikoli puzzles, Slither Link, Cross Sum and Number Place, which is sudoku's original name (Yato and Seta, IEICE Transactions on Fundamentals, 2003). As a consequence, simply deciding whether a general sudoku has a solution is NP-complete.

The proof builds on an older result about Latin squares, grids where each symbol appears once per row and column. Charles Colbourn showed in 1984 that completing a partially filled Latin square is NP-complete (Discrete Applied Mathematics, 1984). Sudoku adds a box rule to that problem. Yato and Seta showed that any Latin-square completion problem can be encoded as a sudoku, so sudoku inherits the hardness.

Why your newspaper sudoku is still easy for a computer

Complexity theory is about growth. A 9×9 grid has only 81 cells, and a short backtracking program with good pruning finishes almost any 9×9 puzzle in milliseconds. Peter Norvig's well-known essay "Solving Every Sudoku Puzzle" solves puzzles this way with a short Python program. Donald Knuth's Dancing Links algorithm, written for exact cover problems in general, is another popular approach.

We saw the same thing while researching the hardest sudoku ever. A plain brute-force checker confirmed that Arto Inkala's famous 2012 puzzle has exactly one solution in well under a second, even though our human-style grader could not place a single digit in it.

Hard for computers vs hard for people

These are two different kinds of difficulty. A computer can search: try a digit, follow the consequences, back up on a contradiction, thousands of times per second. A person solves by spotting patterns and keeping track of candidates, so human difficulty depends on which techniques a puzzle forces. Sudoku Royale's grader measures exactly that. Across the 457,048 graded puzzles in our library, 77.8% can be solved with singles alone, and the rest need patterns like pointing pairs, naked pairs or the X-Wing. None of those percentages has anything to do with NP-completeness. More numbers in how long it takes to solve a sudoku.

Related results

• The fewest clues a 9×9 puzzle can have is 17, proven by exhaustive search in 2012 (McGuire, Tugemann and Civario).
• There are 6,670,903,752,021,072,936,960 valid 9×9 grids. See how many sudoku puzzles are there.
• Sudoku can also be written as a graph colouring problem: 81 vertices, each joined to the 20 cells that share its row, column or box, coloured with 9 colours. More in the mathematics behind sudoku.