zaterdag 7 januari 2012

17, het heilig Sudokugetal

Mia is een echte Sodukofan. Op het randje van de verslaving zelfs.
Sudoku’s oplossen is het eerste wat ze doet als ze ‘s morgens wakker wordt en het laatste vóór ze in bed naar dromenland vertrekt. En als we op vakantie gaan zit er steevast een dikke pil vol 9-cijfer-puzzelkes in de koffer.
Voor de eenvoudige opgaven, de starters en de doorbijters, draait ze haar hand niet om.
Die zijn voor mij. De moeilijke, de kamikaze en de vijandige, “dat is spek naar haren bek”.


image

Uren kan ze er in opgaan, tot ze de oplossing gevonden heeft.
Het gebeurt zelden, maar af en toe zegt ze wel eens met een beetje ontmoediging in haar stem: “Die is niet op te lossen!”

En sommige Sudoku’s zijn ook niet op te lossen.
Een groep wiskundigen van de University College in Dublin, onder leiding van Gary McGuire hebben aangetoond dat een Sudokurooster minstens 17 ingevulde hokjes moet bevatten om oplosbaar te zijn. Alle roosters met minder bekende hokjes kunnen meerdere oplossingen hebben en zijn bijgevolg geen geldige Sudoku’s.
Zo heeft de Australische wiskundige Gordon Royle aangetoond dat de volgende Sodoku met 16 ingevulde hokjes twee oplossingen bezit. Je mag ze altijd eens proberen te vinden.


image

Dat er een minimaal aantal cijfers moet aanwezig zijn is natuurlijk voor de hand liggend. Veronderstel even een 9x9 rooster met alleen het cijfer 1 er in: dan kan je uiteraard een groot aantal oplossingen bedenken.
Maar om er achter te komen dat er minimum 17 bekende hokjes nodig zijn, zijn straffe wiskundigen, een uitgekiend algoritme en een supersnelle computer nodig.
En die supercomputer heeft toch nog van januari 2011 tot december 2011 moest draaien om een besluit mogelijk te maken.
Hoe de groep van McGuire daar bij te werk gingen kan je in dit pdf-bestand lezen.

Enfin, Mia en alle andere Soduko-freaks gaan best eerst even tellen vóór ze zo’n vijandig rooster aanpakken: 17 is van nu af aan voor hen een heilig Sudokugetal.

Geen opmerkingen:

Een reactie plaatsen