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

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