© EPA
© EPA © UNKNOWN

Vergeet de sudoku met maar 16 cijfers

Ierse wiskundigen hebben aangetoond wat sudoku-fanaten al langer vermoeden: een cijferpuzzel met minder dan 17 gevulde hokjes heeft geen unieke oplossing. Dat blijkt uit rekenwerk van Gary McGuire en collega's van University College Dublin, deze week online gepubliceerd.

De populaire sudoku-puzzel is een 9x9 matrix waarin de speler in elke rij en kolom alle cijfers van 1 tot en met 9 moet plaatsen, waarbij al een aantal cijfers zijn ingevuld. Een sudoku waarin bijvoorbeeld maar 7 cijfers zijn ingevuld, kan nooit een unieke oplossing hebben omdat de twee resterende cijfers in elk geval onderling nog kunnen zouden worden verwisseld.

17 aanwijzingen
Wiskundig is echter de vraag wat het minimum aantal clous is voor een unieke (en dus geldige) sudoku. In de praktijk leken sudoku's met 16 aanwijzingen geen unieke oplossing meer te hebben en met 17 wel. Maar formeel bewijs ontbrak nog steeds.

Dat is nog steeds zo. Maar met bruut uitproberen, is in elk geval na te gaan óf er sudoku's met 16 aanwijzingen bestaan die maar één oplossing hebben. Eenvoudig is dat niet. Een sudoku kent ongeveer 10 tot de macht 21 verschillende configuraties (6.670.903.752.021.072.936.960 om precies te zijn), te veel om zelfs met snelle computers binnen redelijke tijd te checken.

Niet opgehelderd
McGuire bedacht een aantal wiskundige argumenten en trucs om het rekenwerk binnen de perken te houden, op basis van symmetrieën en groepentheorie. Daardoor hoeven lang niet alle mogelijkheden individueel te worden gecheckt, maar nog 'maar' 5.472.730.538 opties.

Ruim 7 miljoen processoruren op een computerpark van 640 XEON hex-core processoren in Dublin klaarden de klus in een klein jaar doorwerken. In december was het rekenwerk klaar. Er werd geen 16-clou sudoku gevonden die slechts één oplossing heeft. Waarom dat zo is, is daarmee nog steeds niet opgehelderd, erkent McGuire.