# Empty sudoku and NP-completeness [closed]

My question is straightforward: Is an empty sudoku grid (not partially completed) still NP-complete?

## closed as off-topic by R B, Kaveh, Ryan Williams, Mohammad Al-Turkistany, David EppsteinDec 1 '15 at 7:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – R B, Ryan Williams, Mohammad Al-Turkistany, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.

• No (unless $P=NP$). You can always fill a blank sudoku in polynomial time. You can read about the algorithm here – Shaull Nov 27 '15 at 15:34
• There is a minor technicality here. To specify an empty sudoku grid all we need to specify is the size of the puzzle. A sudoku puzzle is parameterized by $$n$$ and the size itself is a $$n^2 \times n^2$$ grid. However, specifying $$n$$ takes only $$\log n$$ bits while the solutions requires writing down $$n^2 \times n^2$$ numbers. – Chandra Chekuri Nov 27 '15 at 18:13
• NP is a class of decision problems. Since the empty grid is always solvable, the algorithm is "ignore the input and answer YES", which is constant-time irrespective of whether the input is given in unary, binary, or any other way. – Emil Jeřábek Nov 27 '15 at 19:07
• An empty grid is a unary language – there's only one for each $n$ – so it cannot be NP-complete by Mahaney's theorem (unless P=NP). – Peter Shor Nov 28 '15 at 13:26