Wat is het minimum aantal aanwijzingen dat een Sudoku kan hebben?
Laatst bijgewerkt
Een geldige Sudoku - Een met precies één oplossing - Vereist ten minste 17 gegeven cijfers. Dit is een bewezen wiskundig resultaat. Elke puzzel met 16 of minder aanwijzingen heeft ofwel meerdere oplossingen of helemaal geen.
Het 2012-bewijs
In 2012 publiceerden Gary McGuire, Bastian Tugemann en Gilles Civario van University College Dublin een bewijs dat er geen geldige 16-clue Sudoku bestaat. Hun werk was voornamelijk computationeel: ze doorzochten de volledige ruimte van mogelijke 16-clue roosters en controleerden dat geen daarvan een unieke oplossing opleverde. De zoektocht vereiste ongeveer 7 miljoen core-uren aan berekening.
Hiervoor werd algemeen aangenomen dat 17 het minimum was en waren er duizenden 17-clue puzzels experimenteel gevonden. McGuire's team leverde het eerste rigoureuze bewijs dat 16 onmogelijk is.
Hoe 17-Clue-puzzels eruitzien
17-clue puzzels zijn extreem schaars - 17 gegeven cijfers in 81 cellen, waardoor 64 leeg blijven. Ze behoren tot de moeilijkste puzzels om op te lossen en vereisen typisch geavanceerde technieken. Het vinden van geldige 17-clue puzzels zelf vereiste decennia van rekeninspanning. Op het moment van schrijven zijn er meer dan 49.000 wezenlijk verschillende 17-clue Sudoku puzzels bekend.
Wat dit betekent voor puzzelontwerp
Gepubliceerde puzzels gericht op menselijke oplossers gaan zelden onder de 22 clues. Expert en Master difficulty puzzels gebruiken typisch 22-27 gegeven cijfers, terwijl Easy puzzels 36-45 gebruiken. Het 17-clue minimum is een theoretische grens - In de praktijk wegen oplosbaarheid met goede techniek en een prettig oplossingspad veel zwaarder dan het aantal clues alleen.