1
$\begingroup$

What is the least amount of hints a sudoku puzzle needs to be solved related to size $n*n$.

The classic sudoku puzzle is a $9*9$ grid that is divided into rows, columns and $9$ $3*3$ squares called a nonet, where:\

  • Each column must contain the numbers $1-9$ without repetitions
  • Each row must contain the numbers $1-9$ without repetitions
  • Each nonet must contain the numbers $1-9$ without repetitions

Each puzzle is unique and has clues to solve the puzzle. Which are numbers. According to Cornell University there is no way to solve a sudoku with only 16 clues.

So, if there is $x>16$ clues needed for a $9*9$ sudoku, what is the formula for how many are needed for a $n*n$ grid?

$\endgroup$
1
  • $\begingroup$ This might be a question for Puzzling.SE. $\endgroup$
    – Blue
    Commented May 1, 2022 at 3:28

1 Answer 1

1
$\begingroup$

If OEIS is to be taken as an authority, then no such formula exists that we humans know of. They only list the smallest number of clues for a puzzle to possibly have a unique solution for $1\times 1, 4\times 4$ and $9\times 9$ (and $0\times0$), and stop there. There is a bound on $16\times 16$, which lies somewhere between 15 clues and 55. If a formula were known, it would probably be mentioned on OEIS, and the solution would probably be known for more sizes.

In order to figure out that no 16-clue $3\times 3$ sudoku is uniquely solvable, they basically had to try to solve every single one. See, for instance, this numberphile video for more details on that feat. They probably wouldn't have needed that if a formula was known.

(Note that OEIS use $n^2\times n^2$ size sudokus, as the $n\times n$ size smaller boxes are laid out in an $n\times n$ grid. So they don't count, say, $2\times 2$ or $6\times 6$ as sudokus in this case.)

$\endgroup$
1
  • $\begingroup$ Note that it is next to impossible to conclusively claim that a formula doesn't exist, or that no formula has been found. That's why I present evidence instead of proof in this answer. $\endgroup$
    – Arthur
    Commented May 1, 2022 at 4:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .