Hva er minimum antall ledetråder en Sudoku kan ha?
Sist oppdatert
En gyldig Sudoku - En med nøyaktig én løsning - Krever minst 17 gitte sifre. Dette er et bevist matematisk resultat. Ethvert puslespill med 16 eller færre ledetråder har enten flere løsninger eller ingen i det hele tatt.
2012-beviset
I 2012 publiserte Gary McGuire, Bastian Tugemann og Gilles Civario ved University College Dublin et bevis på at det ikke finnes noe gyldig 16-ledetråd Sudoku. Arbeidet deres var hovedsakelig beregningsbasert: de søkte gjennom hele rommet av mulige 16-ledetråd rutenett og verifiserte at ingen ga en unik løsning. Søket krevde omtrent 7 millioner kjernetimer med datakraft.
Før dette var det allment antatt at 17 var minimum, og tusenvis av 17-ledetråd oppgaver var funnet eksperimentelt. McGuires team ga det første strenge beviset på at 16 er umulig.
Hvordan puslespill med 17 ledetråder ser ut
17-ledetrådspuslespill er ekstremt sparsomme - 17 gitte sifre i 81 celler, som etterlater 64 tomme. De er blant de vanskeligste puslespillene å løse og krever typisk avanserte teknikker. Å finne gyldige 17-ledetrådspuslespill i seg selv krevde flere tiår med beregningsinnsats. Per nå er over 49 000 vesensforskjellige 17-ledetråds Sudoku-puslespill kjent.
Hva dette betyr for puslespilldesign
Publiserte puslespill rettet mot menneskelige løsere går sjelden under 22 ledetråder. Ekspert og Mester vanskelighetsgrad puslespill bruker typisk 22-27 gitte sifre, mens Enkle puslespill bruker 36-45. 17-ledetråd minimum er en teoretisk grense - I praksis betyr løsbarhet med god teknikk og en hyggelig løsningsvei langt mer enn ledetrådantall alene.