patternMinor
Minimum number of givens for General Sudoku of size $n^2 \times n^2$
Viewed 0 times
numbersizeminimumgeneralfortimessudokugivens
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#40394, answer score: 2
Revisions (0)
No revisions yet.