Sudoku FlowSådan løser computere sudoku
Opdateret 2026-10-05
Backtracking
Løseren prøver et lovligt ciffer i et tomt felt og fortsætter. Hvis intet ciffer fører til en løsning, fortryder den et tidligere valg og prøver et andet. Hvis man først vælger det felt, der har færrest mulige cifre, bliver søgningen ofte meget kortere.
Kilder: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Eksakt dækning og Dancing Links
Sudoku kan omskrives til et eksakt dækningsproblem: Vælg placeringer, så hvert felt og hvert ciffer i hver række, kolonne og boks er dækket præcis én gang. I en artikel fra november 2000 beskrev Donald Knuth Dancing Links, en effektiv måde at køre hans backtracking-algoritme Algorithm X på; anvendt på modellen af sudoku som eksakt dækningsproblem finder den hurtigt alle løsninger til en opgave.
Kilder: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Tilfældig søgning
Nogle programmer udfylder diagrammet tilfældigt og bytter derefter rundt på tallene for at mindske antallet af konflikter, med metoder som simuleret udglødning eller genetiske algoritmer. De er blevet undersøgt som alternative tilgange; hvor godt de klarer sig, afhænger af programmet og opgaven.
Kilder: Wikipedia: Sudoku solving algorithms
Løsere, der tænker som mennesker
En tipmotor har en anden opgave: Den skal ikke bare finde svaret, men vise det næste trin, som et menneske kan følge. Motoren i vores app prøver menneskelige teknikker i en fast rækkefølge, fra de letteste, som en skjult single, til de sværeste, som kæder og næsten låste mængder (almost locked sets), og bruger den første, der fører til et placeret ciffer; de sværere virker ved først at udelukke kandidater. Den sværeste teknik, den bruger på en opgave, bestemmer opgavens niveau i appen.
Kilder: Hvad hvert sudokuniveau kræver af dig
