# Varför 17 ledtrådar? Sudoku-pusslet som du inte kan göra mindre

Varför behöver en klassisk sudoku minst 17 givna rutor för att ha en lösning? Utforska gränsen, beviset och vad det betyder för spelare.

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](https://www.nikoli.co.jp/en/puzzles/sudoku/). 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/blog/how-to-play-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.

```text
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](https://arxiv.org/abs/1201.0749) 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](https://arxiv.org/html/1201.0749v2).

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](/en/blog/common-techniques-for-solving-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.
