Is SUDOKU np-complete? [closed]

Question

I did go through this.

I don't understand this.

Sudoku is NP-complete when generalized to a n × n grid however a standard 9 × 9 Sudoku is not NP- complete.

Politburo

I’m voting to close this question because this is a computational complexity question that is better suited to cs.stackexchange.com and is off-topic on SO. – Loma

Answer 1

Correct; any 9x9 Sudoku can be solved in O(1) time (as can a 1x1 Sudoko, or a 4x4 Sudoko, or even a 1000x1000 Sudoku) because the input size is fixed. NP-completeness is a concept that applies to decision problems with variable input size, so that you can analyze the running time of an algorithm as that input size grows asymptotically.

The difference is whether the algorithm can assume the size of the input, or has to wait until it receives the input to see how big it is.

The input doesn't have to be encoded in binary; it just has to use some finite-sized alphabet. For fixed-sized Sudoku, you can choose an alphabet that has one unique symbol for each possible puzzle. (In practical terms, you can encode the theoretical alphabet in binary, with a fixed-sized binary string for each alphabet symbol. This is how ASCII works. The input size is still constant; it's just a constant that is bigger than one.) The algorithm then uses a hard-coded table that pairs each symbol in the input alphabet with its solution. The constant-time algorithm that solves the puzzle is just a table lookup.

Now consider the problem where the puzzles do not have a fixed size. There are an infinite number of possible puzzles, so the algorithm has to specify some encoding scheme that can describe an infinite number of puzzles using a finite-sized alphabet. These has two immediate consequences.

1. You cannot store the solutions to all possible inputs in a finite amount of space, so your algorithm needs to do actual work to solve a puzzle once it sees the input.

2. Not all the inputs will have the same size, since a fixed string of symbols from a finite alphabet can only encode a finite number of puzzles. Once the inputs have different sizes, you can consider how much work you algorithm has to do as a function of the input size. (Just reading the input is now an O(n) operation; the work needed to solve the problem maybe, and usually is, greater.)

Flasher

With this logic, any particular instance of an NP-complet problem is O(1) and thus, they are all polynomial? – Beholden

No, because an algorithm that can solve specifially a 9x9 Sudoku cannot solve an arbitrary n x n Sudoku. – Flasher

That does not matter: Do you have a better solution than checking all the possible combinations to ensure a solution for a 9x9 sudoku? Can you convert this sudoku to another NP-complet problem (e.g. minesweeper) -> it is NP-complet – Beholden

You have to be precise about the problem you are claiming to solve. The problem of solving 9x9 Sudoku is very different from the problem of solving n x n Sudoku. – Flasher

No, the general problem of n x n Sudoku is NP-complete. Just because an algorithm runs in constant time doesn't mean it's fast; it just means it does not vary with input size, and an algorithm whose input size cannot vary is trivially a constant-time algorithm. – Flasher

Sudoku can be transformed into an NP-complete problem. Sudoku itself can be solved by a simple set of techniques, which can easily be coded into a small Python program, and its solved nearly instantly. It really depends on the rules as a 9x9 has constraints for each 3x3 square and uses a digit 1 through 9. Therefore outside of 9x9 you need to define what a sudoku is. But the 9x9 is for sure not NP complete and almost all can be solved with some basic first order logic with a few requiring a single recursive exclusion search. Generalizations need clear definitions before such a transform – Hallagan

@BrettHale I want to emphasize that 9x9 sudoku indeed cannot possibly be NP-complete, since: (1) There are less than 10^(9*9) different initial boards for a 9x9 sudoku. (2) Solutions can be precomputed; doesn’t have to be fast, can even be brute force’d. (3) Precomputed solutions can be hard-coded into a lookup table in a new program. Given any 9x9 sudoku, this new program will run in O(n) time. (Not in O(1) time, it still needs to read the input!) – Leverage

@UtkanGezer Reading the input for a problem known to have a fixed size is still O(1). – Flasher

@Flasher Hmm, I see, makes sense: The computation takes at most 83-ish steps, no matter what the input is. If the input is 81 decimal digits (which the program will then interpret as a 9x9 sudoku board), one last step will grab the corresponding answer. If the input is 3498578 decimal digits, the program will scream and reject when it realizes there is a 82nd digit, ending in 83 steps. Of course, if the input alphabet is "9x9 sudoku boards" instead of decimal digits, then the reading can also be done in a single step. Thanks! – Leverage

Answer 2

You are analyzing a problem in O(N) when N goes towards infinity. But you input problem does not vary with N to infinity, you have a finite upper bound. This upper bound is constant.

The reason for this is that there are a finite set of solutions. You can list and enumerate each and every 9x9 sudoku. Index all solutions into a dictionary with the known input values as index. Finding a solution is then just a constant-time lookup in your pre-generated dictionary. It does not matter that the list is huge, only that it is finite.

In fact, another solution is to generate all possible sudoku grids until you find one that solves your input. This might seem like a linear solution at first sight but since there is a finite upper limit it is actually a constant-time algorithm.

Separates