Hvordan bestemmes sudokuers sværhedsgrad?

Som daglig sudoku-gætter har jeg tit undret mig over, hvordan opgavestillerne bærer sig ad med at klassificere de tre opgaver i forskellige sværhedskategorier. Det har tilsyneladende intet at gøre med, hvor mange tal der på forhånd er givet som hjælp til opgaveløseren. Somme tider føles det lettere at løse den sværeste af de tre, daglige opgaver end den middelsvære. Er der en formel for sudokuers sværhedsgrad? Og i så fald: Hvordan ser den ud?

Hilsen Bjørn Pedersen, Ballerup

Newton har talt med Thomas Bolander, lektor ved Institut for Matematik og Computer Science, DTU:

»Det er rigtigt, at man ikke kan vurdere sværhedsgraden af en sudoku ud fra, hvor mange tal der er givet på forhånd. Der findes mange eksempler på sudokuer med mange givne tal, som er lettere end andre sudokuer med meget færre givne tal.

Der er stor forskel på, om sværhedsgraden af en sudoku måles i, hvor lang tid et bestemt computerprogram vil være om at løse den, eller hvor lang tid et menneske vil være om det, men når sudokuer er lavet til mennesker, er det naturligvis relevant at måle sværhedsgraden i, hvor svær den er for mennesker.

For at vurdere, hvad der er svært for mennesker, ser man på hvilke standardstrategier, der er nødvendige for at løse sudokuen. De nemmeste sudokuer kan løses ved brug af de simpleste standardstrategier, som eksempelvis ”singler” og ”skjulte singler”. En single er et felt, som kun kan have én værdi, når man tager højde for, at ingen række, søjle eller kasse må indeholde samme tal to gange. Lidt mere komplicerede strategier er eksempelvis ”nøgne” og ”skjulte par”. Nøgne par er, når to felter i samme domæne (række, søjle eller kasse) kun har to mulige kandidater, og disse kandidater derfor kan slettes fra alle andre felter i domænet, så et eksempel på en sværere sudoku kunne være en, der kun kan løses ved brug af både ”singler” og ”nøgne par”. Der findes langt mere kompliceret strategier, men der findes også sudokuer, som er så komplekse, at ingen kombination af kendte generelle strategier kan løse dem.

Når man skal vurdere sværhedsgraden af en hel sudoku, ser man på, hvilke af de kendte strategier der er nødvendige for at kunne løse den, og hvor komplekse disse strategier er. Så der er ikke tale om en decideret formel, men mere en metode til at afgøre sværhedsgraden.

Forskellige mennesker løser sudokuer forskelligt og vil også have lettere ved nogle strategier end andre, så derfor sker det, at man løser en svær sudoku hurtigere end en let. Det kan også ske, hvis man er heldig og får en pludselig "åbenbaring", som ligger uden for de sædvanlige strategier.«