# Empty sudoku and NP-completeness [closed]

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

• 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 supports Monica 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