Nóg moeilijkere sudoku’s

De nog immer populaire sudoku is er in verschillende varianten. Veel kranten publiceren dagelijks twee sudoku’s, een makkelijke en een moeilijke. Binnenkort kan daar een derde variant aan worden toegevoegd: extreem moeilijk. Althans, dat verwachten Paul Newton en Stephen DeSalvo, twee wiskundigen van de University of Southern California in Los Angeles. De resultaten van hun onderzoek publiceerden zij onlangs in Proceedings of the Royal Society A.

Sudoku’s in de Volkskrant van 18 februari 2010. De linker heeft het predicaat light en de rechter heavy. Als het aan wiskundigen van de University of Southern California in Los Angeles ligt, kan daar een sudoku met het predicaat extreme aan worden toegevoegd.

‘Ik denk dat ons onderzoek ertoe leidt dat we meerdimensionale sudoku’s kunnen maken en dat we de vraag kunnen beantwoorden hoe beginwaarden van een sudoku gekozen moeten worden, opdat een erg moeilijke, doch oplosbare, sudoku ontstaat.’ Dit zegt Paul Newton in een artikel in het tijdschrift ABC Science.

Een sudoku is een vierkant dat uit 9 × 9 = 81 hokjes bestaat. In elk hokje moet een van de getallen 1 tot en met 9 staan, zodat in elke rij en in elke kolom elk cijfer precies eenmaal voorkomt. Bovendien moet elk subvierkant van 3 × 3 elk van die cijfers precies eenmaal bevatten. In 2006 berekenden Felgenhauer en Jarvis dat er ongeveer 6,67 × 10²¹ (om precies te zijn: 6.670.903.752.021.072.936.960) sudoku’s bestaan. Het totale aantal manieren om 81 hokjes in te vullen, is nog veel groter: als niet aan de voorwaarden van een sudoku hoeft te worden voldaan, en in elk hokje willekeurig een van de getallen 1 tot en met 9 wordt geplaatst (niet noodzakelijk elk getal precies negen keer), zijn er 9⁸¹ (ongeveer 1,97 × 10⁷⁷) invullingen mogelijk. Dat betekent dat de kans dat een willekeurig ingevuld vierkant een sudoku is, zeer klein is: ongeveer 3 × 10^-56. De sudoku-voorwaarden zorgen er kennelijk voor dat de spoeling zeer dun is.

Speel sudoku op je computer! Met ‘Pure Sudoku’ kun je kiezen uit vele fraaie achtergronden. Download Pure Sudoku

Willekeur

Newton en DeSalvo zochten uit hoe ‘willekeurig’ de getallen in de suduko staan. Zij bestudeerden 10.000 ingevulde sudoku’s en vergeleken die met vierkanten die willekeurig met de getallen 1 tot en met 9 gevuld waren. Zij waren verrast toen ze ontdekten dat de sudoku’s in feite meer willekeur vertonen dan de willekeurige invullingen. Dit resultaat is tegenintuïtief, omdat je verwacht dat de mate van willekeur juist afneemt naarmate het aantal voorwaarden groter wordt.

Hoe verklaar je dit opmerkelijke feit? Newton: ‘Een willekeurig ingevuld vierkant kan uit één en hetzelfde getal bestaan, of bevat een alternerende structuur (bijvoorbeeld 1-3-5-1-3-5-1-3-5 enz.), noem maar op.’ Er zijn ongelofelijk veel patronen te bedenken, patronen die niet zijn toegestaan in een sudoku.

Doordat men met dit onderzoek meer grip heeft op de structuur van een sudoku, verwachten de wiskundigen dat dit zal leiden tot een beter algoritme om sudoku’s te genereren, waardoor het ook mogelijk moet zijn om nog moeilijkere sudoku’s te maken. Het kleinste aantal startwaarden dat nodig is om een sudoku op slechts één manier te kunnen oplossen, is 17 – althans, dat is de huidige stand van zaken. Het is niet bekend of er een sudoku gemaakt kan worden met minder startwaarden, zonder dat er een tweede oplossing bestaat. Het is niet ondenkbaar dat het onderzoek van Newton en DeSalvo het in de toekomst mogelijk maakt om zo’n sudoku te maken. Bovendien hebben de wiskundigen goede hoop dat hun onderzoek ertoe zal leiden dat er driedimensionale sudoku-kubussen gemaakt kunnen worden. En zo blijft de populaire puzzel springlevend.

Zie ook:

• Sudoku’s ontcijferd (Kennislinkartikel)
• Sudoku en grafentheorie (Kennislinkartikel)
• Sudoku, de nieuwe hype (Kennislinkartikel)
• Sudoku en zeeslag even moeilijk (Kennislinkartikel)