Jaký je minimální počet podnětů, který Sudoku může mít?
Posledně aktualizováno
Validní Sudoku - jedno s přesně jedním řešením - vyžaduje nejméně 17 daných číslic. To je dokázaný matematický výsledek. Každá puzzle s 16 nebo méně indiciemi má buď více řešení, nebo žádné.
Důkaz z 2012
V roce 2012, Gary McGuire, Bastian Tugemann a Gilles Civario z University College Dublin publikovali důkaz, že žádný validní 16-clue Sudoku neexistuje. Jejich práce byla převážně computační: prohledali celý prostor možných 16-clue grids a zjistili, že žádný neprodukuje unikální řešení. Hledání vyžadovalo přibližně 7 millionů core-hodin computace.
Před tím bylo široko věřeno, že 17 bylo minimum a tisíce 17-clue puzzles byly najdeny experimentálně. McGuireho team poskytl první rigorózní důkaz, že 16 je nemožné.
Jak vypadají 17-Clue puzzle
Puzzly s 17 indíciemi jsou extrémně řídké - 17 daných číslic v 81 buňkách, zanechávajíc 64 prázdné. Jsou mezi nejtěžšími puzzly k řešení a typicky vyžadují pokročilé techniky. Nalezení validních puzzlů s 17 indíciemi samo vyžadovalo dekády komputačního úsilí. V čase pisaní je známo přes 49 000 esenciálně různých puzzlů Sudoku s 17 indíciemi.
Co to znamená pro design puzzle
Publikované puzzles aimed at human solvers rarely go below 22 clues. Expert a Master difficulty puzzles typicky používají 22-27 given digits, zatímco Easy puzzles používají 36-45. 17-clue minimum je theoretical bound - V praxi, solvability s good technique a enjoyable solving path matter far more than clue count alone.