Varför 17 ledtrådar? Sudoku-pusslet som du inte kan göra mindre
Ta bort en siffra från en sudoku så kan du göra den svårare. Ta bort fel siffra så kan du förstöra pusslets enda svar. Någonstans mellan ett fullt rutnät och en tom sida finns en hård gräns: 17 givna rutor. Varför slutar sudoku där?
Svaret börjar med en fråga som är lätt att missa: har ditt pussel bara en lösning?
Ett färdigt rutnät, ett svar
I klassisk 9×9-sudoku måste varje rad, kolumn och 3×3-ruta innehålla siffrorna 1 till 9 exakt en gång. Det är de standardregler som Nikoli har publicerat. Siffrorna som redan står i rutnätet kallas givna, eller ledtrådar.
Ett ifyllt rutnät kan följa alla de reglerna utan att vara det enda möjliga svaret på de givna från början. Om två olika färdiga lösningar passar har spelaren ingen möjlighet att räkna ut vilken av dem som konstruktören tänkte sig.
Därför är entydighet viktigt. En välformulerad klassisk sudoku ger dig tillräcklig information för att identifiera exakt ett färdigt rutnät. Är du ny på reglerna är vår guide till att spela sudoku en bra start.
Se en ledtråd göra allt
Här är ett medvetet nästan-färdigt pussel. En punkt markerar en tom cell.
5 3 4 | 6 . 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | . . 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
Det har 78 ledtrådar och en lösning. Toppraden behöver en 7. Den fjärde raden behöver sedan en 7 i kolumn fyra och en 6 i kolumn fem.
Ta nu bort 6:an i rad ett, kolumn fyra. Fyra celler är tomma, och två arrangemang fungerar:
| Cell | Lösning A | Lösning B |
|---|---|---|
| Rad 1, kolumn 4 | 6 | 7 |
| Rad 1, kolumn 5 | 7 | 6 |
| Rad 4, kolumn 4 | 7 | 6 |
| Rad 4, kolumn 5 | 6 | 7 |
Allt annat är oförändrat. Båda arrangemangen uppfyller varje rad, kolumn, ruta och de övriga givna. De fyra cellerna bildar en rektangel där 6:or och 7:or kan bytas plats utan att bryta en regel. Vi räknade lösningarna: första pusslet har exakt en fullständig lösning; efter borttagningen har det exakt två.
Att ta bort en ledtråd kan inte ogiltigförklara en lösning som redan fungerade: den lösningen uppfyller fortfarande alla återstående ledtrådar. Det borttagningen kan göra är att släppa in ett annat svar. Även det här pusslet med 77 givna är alltså tvetydigt, så ett stort antal ledtrådar ensamt kan inte garantera unikhet.
Varför 17 är minimum
Gary McGuire, Bastian Tugemann och Gilles Civario bevisade att ingen klassisk 9×9-sudoku med 16 givna har exakt en lösning. Deras ursprungliga forskningsartikel beskriver en uttömmande dator sökning. Unikt lösbara pussel med 17 ledtrådar finns, så 17 är det lägsta möjliga.
Det betyder inte att vilket arrangemang av 17 siffror som helst skapar ett giltigt pussel. Deras placeringar och värden spelar roll. Resultatet handlar också om klassisk sudoku; extra regler i varianter ändrar problemet.
Varför innebär det att utesluta 16 också att utesluta mindre antal? Om ett mindre pussel hade en enda lösning hade du kunnat lägga till korrekta ledtrådar från den lösningen tills det hade 16. Att lägga till de ledtrådarna hade bevarat dess unika svar, vilket motsäger resultatet.
Hur bevisar man att inget mindre pussel finns?
Att hitta ett pussel med 17 ledtrådar visar vad som är möjligt. Att bevisa att 16 inte kan fungera kräver att man utesluter varje möjlighet.
Forskarna sökte igenom ifyllda rutnät systematiskt, och tog hänsyn till ekvivalenta rutnät. Deras metod använde oundvikliga mängder: grupper av celler som måste innehålla en ledtråd för att förhindra en alternativ lösning. De tog fram en effektiv algoritm för att räkna upp träffmängder, urval som skär dessa grupper, och kontrollerade kandidat-mängder av ledtrådar för unikhet. Artikeln förklarar metoden.
Rektangeln ovan ger en liten illustration av idén. Lämna alla fyra celler utan ledtråd, så klarar sig båda arrangemangen. Lås minst en av de cellerna så blockerar du just det där bytet. I ett glest pussel måste många möjliga alternativ blockeras samtidigt.
Färre ledtrådar betyder inte maximal svårighet
Antalet ledtrådar svarar på “hur mycket information står skrivet?”. Det säger inte vilken slutsats du kommer att se härnäst. Att räkna givna berättar inte om nästa drag är en självklar ensam siffra eller ett mönster du aldrig har lärt dig.
Det finns en annan användbar skillnad: minimum och minimal. Minimum är det minsta antal ledtrådar som går att ha i klassisk sudoku. Ett minimalt pussel är ett där om du tar bort vilken given som helst förlorar du unikheten. Att kalla ett pussel minimalt säger alltså inte att det har 17 ledtrådar.
Till ditt nästa spel: försök att förklara varje placering innan du gör den: “Det här är den enda cellen i rutan som kan ha en 4.” Om du inte kan förklara ett drag än, kolla kandidaterna eller prova en teknik från vår guide för att lösa sudoku.
Nästa gång du ser en gles sudoku: räkna ledtrådarna—och leta sedan efter anledningen till att varje enskild betyder något.
Kommentarer
Dela en tanke, ställ en fråga eller hjälp en annan sudokulösare.
Kontrollerar inloggning…
Laddar kommentarer…