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 Eppstein Dec 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.

  • 6
    $\begingroup$ No (unless $P=NP$). You can always fill a blank sudoku in polynomial time. You can read about the algorithm here $\endgroup$ – Shaull Nov 27 '15 at 15:34
  • 3
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Nov 27 '15 at 18:13
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Nov 27 '15 at 19:07
  • 4
    $\begingroup$ 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). $\endgroup$ – Peter Shor Nov 28 '15 at 13:26