Al jaren is de sudoku, de uit Japan overgewaaide cijferpuzzel, een hit in kranten en tijdschriften. Een sudoku bestaat uit 9 × 9 vakjes, die gevuld moeten worden met de cijfers 1 tot en met 9. In elke rij, in elke kolom en in elk 3×3-vak moet elk cijfer precies eenmaal voorkomen. Wil een sudoku uniek oplosbaar zijn, dan moeten ten minste acht verschillende cijfers in de beginsituatie voorkomen. Want als er maar zeven verschillende cijfers gegeven zijn, kunnen de resterende twee cijfers onderling verwisseld worden.
Deze maand berichtte de Ierse wiskundige Gary McGuire van University College Dublin dat een andere voorwaarde is, dat het totale aantal cijfers in de beginsituatie niet kleiner kan zijn dan 17. Voor alle duidelijkheid: deze voorwaarde is noodzakelijk, maar uiteraard niet voldoende: niet álle sudoku’s hebben genoeg aan 17 begincijfers. De meeste sudoku’s in kranten bevatten ongeveer 25 begincijfers. De sudoku hieronder is er één met 17 begincijfers.
Naar een geldige sudoku met 16 begincijfers is jarenlang vergeefs gezocht en dat leidde tot het vermoeden dat zo’n sudoku niet kan bestaan. McGuire heeft dit vermoeden nu dus hard gemaakt: een sudoku met 16 begincijfers kan nooit één unieke oplossing hebben en is dus daarmee geen geldige sudoku.
Onvermijdelijke sets
Er bestaan niet minder dan 6.670.903.752.021.072.936.960 (ongeveer 6,67 × 1021) ingevulde sudoku’s. Veel daarvan kunnen echter als identiek worden beschouwd. Als je rotaties, spiegelingen, rij- en kolomverwisselingen en rolverwisseling van de cijfers eruit filtert, hou je nog 5.472.730.538 ingevulde sudoku’s over (zie Sudoku’s ontcijferd).
Neem zo’n ingevulde sudoku, en kies daaruit 16 begincijfers. Het aantal manieren om 16 cijfers uit 81 te kiezen, is 33.594.090.947.249.085 (ongeveer 33,6 × 1015; het aantal combinaties van 16 uit 81). Een potentiële manier om het vermoeden te bewijzen, is door al die sudoku’s met 16 begincijfers na te lopen. Dat zou echter veel te veel tijd kosten: ook voor snelle computers is het een ondoenlijke taak om alle mogelijkheden na te gaan.
McGuire bedacht daarom een paar slimmigheden om dit aantal te reduceren. Hij gebruikte daarvoor resultaten uit de grafentheorie en de groepentheorie. Het idee is gebaseerd op wat wiskundigen onvermijdelijke sets noemen. Dit laat zich het beste uitleggen aan de hand van een eenvoudig voorbeeld. Bekijk de linker ingevulde sudoku hieronder. Als je de cijfers 1 en 5 in de gele vakjes verwisselt, ontstaat er opnieuw een geldige sudoku. Dat betekent dat ten minste één van de cijfers in de gele vakjes bij de begincijfers moet horen. We noemen de verzameling gele vakjes een onvermijdelijke set. Formeel: een deelverzameling U van een ingevulde sudoku S heet een onvermijdelijke set, indien élke verzameling begincijfers waarmee S uniek kan worden opgelost, ten minste één element uit U bevat. Een andere, grotere, onvermijdelijke set zie je in het rechterplaatje.
Onvermijdelijke sets kunnen helpen om het probleem te vereenvoudigen: als een verzameling begincijfers niet elke onvermijdelijke set doorsnijdt, is het geen geldige sudoku; er zijn dan immers meerdere oplossingen. Dat betekent dat een verzameling begincijfers van élke onvermijdelijke set ten minste één element moet bevatten.
Hoe je alle onvermijdelijke sets vindt, is een allerminst eenvoudige vraag, maar het werk loont zich. McGuire en zijn collega’s ontwierpen een zogeheten ‘hitting-set algoritme’ – dat het om ingewikkelde materie gaat, blijkt wel uit het feit dat het hitting-set problem NP-volledig is. Nadat het algoritme uitvoerig was getest (dit duurde twee jaar), konden ze alle onvermijdelijke sets in elk van de 6,671 × 1021 ingevulde sudoku’s vaststellen. De winst: de hoeveelheid rekenwerk die nodig is om vast te kunnen stellen dat een sudoku met 16 begincijfers niet kan bestaan, wordt beheersbaar. Ongeveer 7 miljoen processoruren op het Irish Centre for High-End Computing in Dublin klaarden de klus in een klein jaar.
Zie ook:
- Vergeet de sudoku met maar 16 cijfers (de Volkskrant)
- Mathematician claims breakthrough in Sudoku puzzle (Nature)
- There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem (het artikel van Gary McGuire, Bastian Tugemann, Gilles Civario)
- Exhaustive search solves fiendish Sudoku mystery (New Scientist)
- No 16-Clue Sudoku! (I Programmer)
- Is there a Sudoku puzzle with 16 clues? (pdf)
Meer over sudoku’s op Kennislink:
Oeps: Onbekende tag `feed’ met attributen {"url"=>"https://www.nemokennislink.nl/kernwoorden/sudoku.atom", “max”=>"10", “detail”=>"minder"}