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

CC BY-SA 3.0
2015-11-27T15:34:58.800Z
No (unless $P=NP$). You can always fill a blank sudoku in polynomial time. You can read about the algorithm [here](https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Blank_Sudoku_grids)
Shaull
CC BY-SA 3.0
2015-11-27T18:13:34.797Z
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
CC BY-SA 3.0
2015-11-27T19:07:59.860Z
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
CC BY-SA 3.0
2015-11-28T13:26:29.493Z
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 
<np-hardness><optimization>
Empty sudoku and NP-completeness
yafrani
# Empty sudoku and NP-completeness

(Asked by: username_0 on 2015-11-27)

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

**Tags:** np-hardness, optimization
> **Comments:**
> **username_1**: No (unless $P=NP$). You can always fill a blank sudoku in polynomial time. You can read about the algorithm [here](https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Blank_Sudoku_grids)  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: 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).  

---

## 0 answers

