cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A372224 #35 May 25 2024 09:04:41
%S A372224 0,1,2,4,6,8,12,14,17
%N A372224 The size of the smallest critical set of hints needed to uniquely solve a generalized n X n Sudoku board.
%C A372224 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 A372224 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 A372224 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 A372224 J. N. Cooper and A. Kirkpatrick, Critical Sets for Sudoku and General Graphs, Discrete Mathematics, 315-316 (2014), 112-119.
%D A372224 C. Lass, Minimal number of clues for Sudokus, Central European Journal of Computer Science, 2 (2012).
%D A372224 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 A372224 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 A372224 When n is prime, a(n) is conjectured to equal A002620(n).
%F A372224 When n is square, a(n) = A198297(n).
%e A372224 Below is a critical set of size 17 on the 9 X 9 Sudoku grid:
%e A372224 .
%e A372224   +-------+-------+-------+
%e A372224   |       | 8   1 |       |
%e A372224   |       |       |   4 3 |
%e A372224   | 5     |       |       |
%e A372224   +-------+-------+-------+
%e A372224   |       |   7   | 8     |
%e A372224   |       |       | 1     |
%e A372224   |   2   |   3   |       |
%e A372224   +-------+-------+-------+
%e A372224   | 6     |       |   7 5 |
%e A372224   |     3 | 4     |       |
%e A372224   |       | 2     | 6     |
%e A372224   +-------+-------+-------+
%e A372224 .
%e A372224 which uniquely determines the solution:
%e A372224 .
%e A372224   +-------+-------+-------+
%e A372224   | 2 3 7 | 8 4 1 | 5 6 9 |
%e A372224   | 1 8 6 | 7 9 5 | 2 4 3 |
%e A372224   | 5 9 4 | 3 2 6 | 7 1 8 |
%e A372224   +-------+-------+-------+
%e A372224   | 3 1 5 | 6 7 4 | 8 9 2 |
%e A372224   | 4 6 9 | 5 8 2 | 1 3 7 |
%e A372224   | 7 2 8 | 1 3 9 | 4 5 6 |
%e A372224   +-------+-------+-------+
%e A372224   | 6 4 2 | 9 1 8 | 3 7 5 |
%e A372224   | 8 5 3 | 4 6 7 | 9 2 1 |
%e A372224   | 9 7 1 | 2 5 3 | 6 8 4 |
%e A372224   +-------+-------+-------+
%Y A372224 Cf. A002620, A002860, A198297.
%K A372224 nonn,hard,more
%O A372224 1,3
%A A372224 _Agustin Gomez de la Vega_ and _Mithra Karamchedu_, Apr 22 2024