A372224 - OEIS

%I #35 May 25 2024 09:04:41

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

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

%C 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.

%C 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.

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

%D J. N. Cooper and A. Kirkpatrick, Critical Sets for Sudoku and General Graphs, Discrete Mathematics, 315-316 (2014), 112-119.

%D C. Lass, Minimal number of clues for Sudokus, Central European Journal of Computer Science, 2 (2012).

%D 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.

%H H. Chel, D. Mylavarapu, and D. Sharma, <a href="http://doi.org/10.1109/ICEEOT.2016.7754798">A novel multistage genetic algorithm approach for solving Sudoku puzzle</a>, IEEE International Conference on Electrical, Electronics, and Optimization Techniques (2016), 1.

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

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

%e Below is a critical set of size 17 on the 9 X 9 Sudoku grid:

%e .

%e   +-------+-------+-------+

%e   |       | 8   1 |       |

%e   |       |       |   4 3 |

%e   | 5     |       |       |

%e   +-------+-------+-------+

%e   |       |   7   | 8     |

%e   |       |       | 1     |

%e   |   2   |   3   |       |

%e   +-------+-------+-------+

%e   | 6     |       |   7 5 |

%e   |     3 | 4     |       |

%e   |       | 2     | 6     |

%e   +-------+-------+-------+

%e .

%e which uniquely determines the solution:

%e .

%e   +-------+-------+-------+

%e   | 2 3 7 | 8 4 1 | 5 6 9 |

%e   | 1 8 6 | 7 9 5 | 2 4 3 |

%e   | 5 9 4 | 3 2 6 | 7 1 8 |

%e   +-------+-------+-------+

%e   | 3 1 5 | 6 7 4 | 8 9 2 |

%e   | 4 6 9 | 5 8 2 | 1 3 7 |

%e   | 7 2 8 | 1 3 9 | 4 5 6 |

%e   +-------+-------+-------+

%e   | 6 4 2 | 9 1 8 | 3 7 5 |

%e   | 8 5 3 | 4 6 7 | 9 2 1 |

%e   | 9 7 1 | 2 5 3 | 6 8 4 |

%e   +-------+-------+-------+

%Y Cf. A002620, A002860, A198297.

%K nonn,hard,more

%O 1,3

%A _Agustin Gomez de la Vega_ and _Mithra Karamchedu_, Apr 22 2024