Vad är det minsta antalet ledtrådar ett Sudoku kan ha?
Senast uppdaterad
En giltig Sudoku - en med exakt en lösning - kräver minst 17 givna siffror. Detta är ett bevisat matematiskt resultat. Alla pussel med 16 eller färre ledtrådar har antingen flera lösningar eller ingen alls.
2012-beviset
År 2012 publicerade Gary McGuire, Bastian Tugemann och Gilles Civario vid University College Dublin ett bevis för att inget giltigt 16-ledtrådars Sudoku existerar. Deras arbete var huvudsakligen beräkningsmässigt: de sökte igenom hela utrymmet av möjliga 16-ledtrådars rutnät och verifierade att inget gav en unik lösning. Sökningen krävde ungefär 7 miljoner kärntimmar av beräkning.
Innan detta trodde man allmänt att 17 var minimum och tusentals 17-ledtrådars pussel hade hittats experimentellt. McGuires team gav det första rigorösa beviset för att 16 är omöjligt.
Hur 17-ledtrådspussel ser ut
17-ledtrådspussel är extremt glesa - 17 givna siffror i 81 celler, vilket lämnar 64 tomma. De är bland de svåraste pusslen att lösa och kräver vanligtvis avancerade tekniker. Att hitta giltiga 17-ledtrådspussel i sig krävde decennier av beräkningsinsats. Vid tidpunkten för skrivandet är över 49 000 väsentligen olika 17-ledtråds Sudoku-pussel kända.
Vad detta innebär för pusseldesign
Publicerade pussel riktade till mänskliga lösare går sällan under 22 ledtrådar. Expert och Mästare svårighetsgrad pussel använder vanligtvis 22-27 givna siffror, medan Lätt pussel använder 36-45. 17-ledtrådsminimumet är en teoretisk gräns – I praktiken spelar lösbarhet med god teknik och en njutbar lösningsväg mycket större roll än enbart ledtrådsantal.