Annons

Hur kan lätta sudoko vara så svåra?

Publicerad:

2011-06-06

Fråga: Jag använder sudoku som hjärngympa varje dag och har två frågor: Hur många olika sudoku finns det, och hur konstruerar man sudoku med olika svårighetsgrad? Antalet givna siffror är förstås en parameter, men jag stöter ofta på svåra sudoku trots att antalet givna siffror är högt.

Gustaf Plym Forshell

Svar: Det finns 6 670 903 752 021 072 936 960 olika sudoku. Men en hel del liknar varandra. Till exempel är det ingen skillnad om man byter plats på symbolerna på vissa sätt, till exempel om alla 1:or byter plats med alla 2:or. Om man i stället räknar antalet unika pussel blir antalet möjliga sudoku betydligt mindre: 5 472 730 538 stycken.

Det är nästan omöjligt att kortfattat beskriva hur man konstruerar sudoku. Det är några få entusiaster som gör det, och alla har sina privata tricks. De sudoku som dagligen förekommer i medierna är datorgenererade – du kan hitta algoritmer som gör det på internet. De är ofta ganska enformiga.

En mycket erfaren konstruktör kan göra en sudoko på ett par timmar. Efter några års konstruktioner kan man faktiskt styra hur svår sudokon blir. Svårigheten beror på flera olika saker, till exempel antalet siffror, mönster och hur ofta samma siffra förekommer.

Paul Vaderlind, matematiker vid Stockholms universitet.

Forskning & Framsteg berättar om fackgranskade forskningsresultat och om pågående forskning. Våra texter ska vara balanserade och trovärdiga, och sätta forskningsresultaten i sitt sammanhang för att göra dem begripliga. Forskning & Framsteg har rapporterat om vetenskap sedan 1966.