Sudoku vraagt om minimaal 17 aanwijzingen

Hoeveel aanwijzingen zijn minimaal nodig om een sudoku op te kunnen lossen? Wetenschappers zijn eruit!

Wanneer u de sudoku in de krant maakt, dan helpt de maker ervan u op weg. Een aantal vakjes is al ingevuld. Dat is logisch: zonder die aanwijzingen kunt u de puzzel immers niet maken. Maar hoeveel aanwijzingen zijn er nu minstens nodig om de puzzel op te kunnen lossen? Dat wil eigenlijk zeggen: hoeveel aanwijzingen zijn er minimaal nodig om ervoor te zorgen dat de puzzel maar één oplossing heeft?

Hypothese
Sudoku’s met één oplossing en zeventien aanwijzingen bestaan. Maar een sudoku met zestien aanwijzingen en één oplossing is nog nooit gevonden. Vandaar dat velen ervan uitgaan dat er minimaal zeventien aanwijzingen nodig zijn om een puzzel met maar één oplossing te produceren. De onderzoekers hebben die hypothese nu grondig getest.

Meer puzzels

Hoe?
De methode is eigenlijk heel eenvoudig. De onderzoekers liepen alle oplossingen die een puzzel met zestien aanwijzingen kan hebben, door. U begrijpt: voor zo’n enorme klus was een rekenmachine niet genoeg. De onderzoekers maakten daarom gebruik van een computerprogramma: checker. Dit programma werd al in 2006 ontwikkeld, maar is de afgelopen jaren aanzienlijk verbeterd. Om een idee te geven: volgens de onderzoekers zou de oude versie op één pc er 300.000 jaar over gedaan hebben om het Sudoku-vraagstuk op te lossen.

Gelukkig had de nieuwe versie van checker niet zoveel tijd nodig en kunnen de onderzoekers ons nu al in hun paper vertellen hoeveel aanwijzingen een sudoku werkelijk nodig heeft. De wetenschappers moeten concluderen dat ze geen enkele sudoku met zestien aanwijzingen en één oplossing hebben kunnen vinden. En met het oog op hun grondige aanpak mogen we er dan ook van uitgaan dat deze er niet is. In andere woorden: een sudoku heeft minstens zeventien aanwijzingen nodig.

Bronmateriaal

"There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem" - Arxiv.org
De foto bovenaan dit artikel is gemaakt door chotda (cc via Flickr.com).

Fout gevonden?

Voor jou geselecteerd