Sudokuuppslagsverk · Matematik och datorer

Matematiken bakom sudoku

Uppdaterad 2026-10-05

En latinsk kvadrat med block

I en latinsk kvadrat förekommer varje symbol en gång i varje rad och varje kolumn. Ett färdigifyllt sudoku är en latinsk kvadrat av storlek 9 med ytterligare ett villkor: vart och ett av de nio 3×3-blocken innehåller också varje siffra en gång.

Källor: Wikipedia: Latin square

Hur många rutnät det finns

Bertram Felgenhauer och Frazer Jarvis räknade de färdigifyllda 9×9-rutnäten 2005: det finns 6 670 903 752 021 072 936 960, ungefär 6,67 × 10²¹. Många av dem är samma rutnät i förklädnad. Om två rutnät räknas som ett när det ena kan omvandlas till det andra genom att byta beteckning på siffrorna, rotera eller spegla, eller ändra ordningen på rader och kolumner på sätt som bevarar rutnätets giltighet, återstår 5 472 730 538 väsentligen olika rutnät, ett antal som beräknades av Ed Russell och Frazer Jarvis.

Källor: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Minst 17 ledtrådar

Inget vanligt 9×9-sudoku med 16 eller färre givna siffror har exakt en lösning. Gary McGuire, Bastian Tugemann och Gilles Civario visade detta med en uttömmande datorsökning och tillkännagav resultatet i januari 2012. Sjutton är ett minimum, ingen garanti: många rutnät med 17 givna siffror har fortfarande fler än en lösning.

Källor: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku som graffärgning

Rita en punkt för var och en av de 81 cellerna och förbind två punkter när deras celler delar rad, kolumn eller block. Den här sudokugrafen har 810 förbindelser, och varje punkt har exakt 20 grannar. Att lösa pusslet innebär att utöka den färgning som de givna siffrorna bestämmer så att förbundna punkter aldrig har samma färg. Minst nio färger behövs, eftersom varje rad, kolumn och block är en grupp med nio punkter som alla är förbundna med varandra, och varje färdigifyllt rutnät visar att nio räcker.

Källor: Wikipedia: Sudoku graph

Svårt i allmänhet, snabbt för 9×9

För sudokurutnät som kan växa utan gräns (n²×n² med n×n-block) är problemet att avgöra om ett delvis ifyllt rutnät kan fyllas färdigt NP-fullständigt, ett resultat som Takayuki Yato och Takahiro Seta publicerade 2003. Effektiva datorprogram löser i regel vanliga 9×9-pussel på en bråkdel av en sekund, men tiden beror på programmet, datorn och pusslet.

Källor: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Se även

Källor

Alla artiklar →