OFFSET
1,3
COMMENTS
A "critical set" is a collection of Sudoku hints that uniquely determines a solution to the puzzle, but such that removing any hint no longer does so.
Our generalized n X n Sudoku board consists of n rows, n columns, and n lengthwise rectangular subgrids with dimensions A033676(n) X A033677(n). Every row, every column, and every subgrid must contain the digits 1..n.
When n is prime, a(n) is the size of smallest critical set of an n X n Latin square, which is conjectured to equal A002620(n).
REFERENCES
J. N. Cooper and A. Kirkpatrick, Critical Sets for Sudoku and General Graphs, Discrete Mathematics, 315-316 (2014), 112-119.
C. Lass, Minimal number of clues for Sudokus, Central European Journal of Computer Science, 2 (2012).
G. McGuire et al., There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration, Experimental Mathematics, 23 (2012), 190-217.
LINKS
H. Chel, D. Mylavarapu, and D. Sharma, A novel multistage genetic algorithm approach for solving Sudoku puzzle, IEEE International Conference on Electrical, Electronics, and Optimization Techniques (2016), 1.
FORMULA
EXAMPLE
Below is a critical set of size 17 on the 9 X 9 Sudoku grid:
.
+-------+-------+-------+
| | 8 1 | |
| | | 4 3 |
| 5 | | |
+-------+-------+-------+
| | 7 | 8 |
| | | 1 |
| 2 | 3 | |
+-------+-------+-------+
| 6 | | 7 5 |
| 3 | 4 | |
| | 2 | 6 |
+-------+-------+-------+
.
which uniquely determines the solution:
.
+-------+-------+-------+
| 2 3 7 | 8 4 1 | 5 6 9 |
| 1 8 6 | 7 9 5 | 2 4 3 |
| 5 9 4 | 3 2 6 | 7 1 8 |
+-------+-------+-------+
| 3 1 5 | 6 7 4 | 8 9 2 |
| 4 6 9 | 5 8 2 | 1 3 7 |
| 7 2 8 | 1 3 9 | 4 5 6 |
+-------+-------+-------+
| 6 4 2 | 9 1 8 | 3 7 5 |
| 8 5 3 | 4 6 7 | 9 2 1 |
| 9 7 1 | 2 5 3 | 6 8 4 |
+-------+-------+-------+
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Agustin Gomez de la Vega and Mithra Karamchedu, Apr 22 2024
STATUS
approved