Hvad er det mindste antal ledetråde en Sudoku kan have?
Sidst opdateret
En gyldig Sudoku - en med præcis én løsning - kræver mindst 17 givne cifre. Dette er et bevist matematisk resultat. Enhver opgave med 16 eller færre ledetråde har enten flere løsninger eller slet ingen.
2012-beviset
I 2012 offentliggjorde Gary McGuire, Bastian Tugemann og Gilles Civario fra University College Dublin et bevis for, at der ikke findes nogen gyldig 16-clue Sudoku. Deres arbejde var primært beregningsmæssigt: de søgte gennem hele rummet af mulige 16-clue gitre og verificerede, at ingen producerede en unik løsning. Søgningen krævede cirka 7 millioner core-hours beregning.
Før dette var det almindeligt antaget, at 17 var minimum, og tusindvis af 17-clue puslespil var blevet fundet eksperimentelt. McGuires team leverede det første stringente bevis for, at 16 er umuligt.
Hvordan 17-Clue-puslespil ser ud
17-ledetråds-puslespil er ekstremt sparsomme - 17 givne cifre i 81 celler, hvilket efterlader 64 tomme. De er blandt de sværeste puslespil at løse og kræver typisk avancerede teknikker. At finde gyldige 17-ledetråds-puslespil krævede i sig selv årtiers beregningsindsats. På nuværende tidspunkt kendes over 49.000 væsentligt forskellige 17-ledetråds-Sudoku-puslespil.
Hvad dette betyder for puslespildesign
Udgivne puslespil rettet mod menneskelige løsere går sjældent under 22 clues. Expert og Master sværhedsgrad puslespil bruger typisk 22-27 givne cifre, mens Easy puslespil bruger 36-45. 17-clue minimum er en teoretisk grænse - I praksis betyder løsbarhed med god teknik og en behagelig løsningssti meget mere end clue-antal alene.