What is a time complexity for Algorithm X for sudoku?

Question

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)

• not possible to always solve in a polynomial time

• possible to verify a solution in a polynomial time

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!

Drysalt

Answer 1

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.

Trader

If n is 3, what does N represent? And why isn't it a constant as well? – Nisse

@rici, there are 2 constants here: n = 3 is a size of block, and N = n^2 = 9 is a size of row/column. Even if it is a constant, people are still used to speak about time complexity in terms like "O(N^3) where N = 9". For example, in this article – Drysalt

@tkrishtop: sometimes people use terms incorrectly. Sometimes these errors are innocuous, other times (as in the cited article) they make the text meaningless. In no case should they be emulated. The claim in that paper, to the extent that it is meaningful, is wrong or misleading. Dancing links has many virtues but it does not make polynomial-time algorithms out of exponential-time algorithms. – Nisse

@Nisse sorry, I didn’t get your point. Do you want just to mention that “O(N^3) where N = 9” is not elegant and better to say “9^3 operations” ? Or you’re not agree that it’s 9^3 ? – Drysalt

@tkrishtop: it is certainly not 9^3 operations, for any meaningful definition of "operation". So there is that. The statement that DLX takes cubic time is just plain wrong, and attempting to say that it applies to some fixed n shows a complete lack of understanding of what Big-O notation means. Forget that paper and read a good textbook. – Nisse

@rici, so what is DLX time complexity equal to? – Drysalt

@tkrishtop: as this answer says, it is worst-case exponential. I don't believe a tight-limit (θ()) is known; in theory DLX could be O(2^N) where N is the number of sets, but I think Sudoku can be solved with a smaller (though still exponential) time-sensitive complexity – Nisse

A standard, 9x9 sudoku, is not NP-complete. Only a NxN one. So O(N^3) seems reasonable. We could try to generalise this to NxN, (here lowercase n means the size of a block), this would result in O((n*n)^n) or more elegantly O(n^(2n)). This is still exponential/nonpolynomial – Metallist

Answer 2

For a complete analysis of running time see: https://11011110.github.io/blog/2008/01/10/analyzing-algorithm-x.html

There it is stated that

even the stupidest version of Algorithm X, one that avoids any chance to backtrack and always chooses its pivots in such a way as to maximize its running time, takes at most O(3^n/3)

which places the algorithm in exponential running time (EXPTIME).

Virginium