5
$\begingroup$

Here, it is well known that the minimal number of givens for a size $9 \times 9$ board of Sudoku requires 17 "givens" in order to be solved (i.e., no puzzle can be solved with $\le 16$ givens).

What is the minimal number of givens for a size $n^2 \times n^2$ board? Is there a table of "best-known" minimal values?

I'm speculating that there is only an asymptotic/approximate bound as the $n=3$ case was not known, let alone higher values of $n$. For $n=4$, the best-known is 55, and $n=5$ is 151.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ That link says the proof that 17 "givens" are required was only obtained through exhaustive computer search. Therefore, there's not likely to be a known formula that works for general $n$; and when $n$ is large, exhaustive search to find the exact answer is not likely to be feasible. Asking for a table of best known bounds is reasonable, though. $\endgroup$ – D.W.♦ Mar 13 '15 at 16:44
  • $\begingroup$ @D.W. I was just wondering if there is a known proof that at least $f(n)$ givens is required or something. A table would be more helpful though. $\endgroup$ – Ryan Mar 13 '15 at 16:45
  • 1
    $\begingroup$ Possible duplicate of Minimum number of clues to fully specify any sudoku? $\endgroup$ – David Richerby Sep 30 '17 at 18:29
  • $\begingroup$ @DavidRicherby, that question asks about 9x9 sudoku, while this asks about generalization. $\endgroup$ – rus9384 Oct 6 '17 at 1:03
  • $\begingroup$ oeis.org/A198297 $\endgroup$ – Pseudonym Oct 8 '17 at 3:09
2
$\begingroup$

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is known for $n = 2$ (4 x 4 Sudoku), of which the minimum clues is 4 (25% of cells filled). There are 13 such non-equivalent puzzles. (based on info at "enjoysudoku.com").

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is also known for $n = 3$ (9 x 9 Sudoku), of which the minimum clues is 17 (about 21.0% of cells filled). About 49,000 such non-equivalent Sudokus have been discovered.

For $n = 4$ (16 x 16), the fewest clues known in any puzzle is 55 (about 21.5% of cells filled), but it is not known if this is the fewest possible. (based on info at "enjoysudoku.com").

For $n = 5$ (25 x 25), little work has also been done to find the fewest clues possible, and comparatively few Sudokus of this size have been constructed. One 25 x 25 Sudoku is known to have 328 clues. So from a cursory study, the fewest clues for (n=5) is 328 or fewer (about 52% or fewer cells filled). Note: this Sudoku was not an attempt to be an example with few clues. I listed it only to provide an initial upper bound.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ For n in {0,1}, the minimum is zero. ​ ​ $\endgroup$ – user12859 Oct 6 '17 at 2:14
  • $\begingroup$ Well, is it proven at least that number of givens tends to become closer to number of cells as $n$ grows? Maybe some upper bound on limit ($\le 1$) is known? Or $1$ is tight bound? $\endgroup$ – rus9384 Oct 7 '17 at 17:06
  • $\begingroup$ Seems like an open problem well into to the delve of research. $\endgroup$ – User Not Found Dec 31 '17 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.