5

Consider a $n^2 \times n^2$ grid sudoku. Define a clue to be composed of a coordinate $x$ and $y$ of the grid and a value $z$. The goal is given $n$ and a set of clues, to find one solution to the sudoku problem.

Let $R$ be the number of clues of the problem.

  • if $R = 0$, the problem is polynomial since it can be resolved in $O(1)$: fill the first line with $1, 2, 3, \dots, n^2$, the second line with $n, n+1, \dots, n^2, 1, 2, \dots, n-1$ until the last line with $n^2-n, \dots, n^2, 1, 2, \dots, n^2-n$.
  • if $R \geq n^4-a$ for a constant $a$, the problem is polynomial too: use brute force and try $n$ different values for the $a$ empty coordinate: $O(n^a)$.

What about other $R$? For which $R$ the problem is polynomial? And for which it is NP-Hard?

Samuel Bismuth
  • 173
  • 7
  • 1
    $R=1$ is equivalent to $R=0$ since we can shift the Latin square according to $(x,y)\mapsto z$. – ə̷̶̸͇̘̜́̍͗̂̄︣͟ Mar 23 '22 at 07:24
  • There is a result that when there are at least 17 clues in a Sudoku it will have a unique solution. It feels like that in such a case the whole problem will simply reduce to solving a system of linear equations. Maybe this might be a starting point for further thoughts. – YukiJ Mar 23 '22 at 07:30
  • @TheSimpliFire Oops, you are totally right! The number 17 is for the $3\times 3$ case. Maybe there are results for the general case on that. – YukiJ Mar 23 '22 at 07:36
  • @YukiJ Ah, I think I've found the reference you're talking about: https://community.middlebury.edu/~jschmitt/papers/minclues4.pdf ($3^2\times3^2$) – ə̷̶̸͇̘̜́̍͗̂̄︣͟ Mar 23 '22 at 07:38
  • @TheSimpliFire Yep, that is what I was thinking about. I am no expert on Sudokus but I thought it might be a direction to take in order to solve the problem – YukiJ Mar 23 '22 at 07:40
  • @TheSimpliFire: You are right. For $R=2$, the problem is easy by using shifting too. I have no formal proof, but I think that for small $R$, the problem is easy. – Samuel Bismuth Mar 23 '22 at 16:03
  • If $R \geq n^4 - n$, the solution is easy: There are $n$ free cordinates, such that for each coordinate there must be $n-1$ clues in the same row, column, or square. Thus, it is easy to find their values. – Samuel Bismuth Mar 23 '22 at 16:09

0 Answers0