algorithmtime-complexitysudokuknuth

What is a time complexity for Algorithm X for sudoku?


I've found here a statement that Algorithm X for sudoku has O(N^3) time complexity where N is a board size.

That's maybe logical, since for sudoku the binary matrix to compute has N^3 rows. But that makes sudoku problem solvable in a polynomial time, and sudoku is known to be NP problem, that means (as I understand it)

So what is the time complexity of Algorithm X for sudoku, and is it possible to solve a sudoku in a polynomial time or not ?

Thank you!


Solution

  • Mathematics of Sudoku explains this pretty well:

    The general problem of solving Sudoku puzzles on n^2×n^2 grids of n×n blocks is known to be NP-complete.

    The runtime complexity of any algorithm solving Sudoku is thus at least exponential in n. For a normal Sudoku (n = 3) this means O(N^3) is perfectly reasonable.