A372224 The size of the smallest critical set of hints needed to uniquely solve a generalized n X n Sudoku board.

0, 1, 2, 4, 6, 8, 12, 14, 17

Offset: 1

Author

Agustin Gomez de la Vega and Mithra Karamchedu, Apr 22 2024

Keywords

• nonn
• hard
• more

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).

Examples

			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 |
  +-------+-------+-------+
		

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.

Crossrefs

Cf. A002620, A002860, A198297.

Formula

When n is prime, a(n) is conjectured to equal A002620(n).

When n is square, a(n) = A198297(n).