Sudoku’s zijn al heel wat jaren populair in dagbladen. Tot nu toe werd gedacht dat Sudoku’s alleen met minimaal 17 ingevulde cijfers opgelost konden worden. De wiskundige vraag die daarop volgde: zijn er ook puzzels met minimaal 16 ingevulde cijfers en één mogelijke oplossing? Een jaar onderzoek met een ingewikkeld computermodel leidde tot het antwoord: er zijn minimaal 17 ingevulde cijfers nodig.

Bij een Sudoku gaat het om een puzzel van 9 x 9 vakjes, waarbij elk vierkant van 3 x 3 vakjes alle cijfers van 9 moet bevatten. Ook moet elke rij en kolom alle 9 cijfers bevatten. Er is ook een andere, ongeschreven regel: de puzzel mag maar één oplossing bevatten. Een 9 x 9 vierkant met maar 7 of minder al ingevulde cijfers heeft meerdere oplossingen. Hoeveel aanwijzingen zijn er dan minimaal nodig voor een puzzel met maar één oplossing?

Sudoku-fanatici vonden eerder voorbeelden van puzzels met 17 aanwijzingen die maar één oplossing hadden. Ze hebben er geen gevonden met 16 aanwijzingen en één oplossing, wel met 16 aanwijzingen en twee oplossingen. Dat suggereert een minimum van 17 aanwijzingen, maar niemand heeft dat nog kunnen bewijzen. Tot nu toe.

Gary McGuire en zijn collega’s aan de University College in Dublin hebben zich over de vraag gebogen. Met een computermodel bekeken ze miljoenen mogelijkheden van Sudoku’s met 16 ingevulde cijfers en de oplossing daarvoor. Conclusie van het werk: het minimum is inderdaad 17.

Met 17 aanwijzingen is een Sudoku zeer moeilijk. Sudoku’s in kranten geven meestal 25 ingevulde cijfers weg – hoe meer cijfers, hoe makkelijker de puzzel.

Bron: Nature, beeld Twentyfour Students