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!
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.