Het is gemakkelijk te zien waarom. Een raster met 7 aanwijzingen kan geen uniek antwoord hebben, omdat de twee ontbrekende cijfers altijd kunnen worden verwisseld in elke oplossing. Een soortgelijk argument verklaart waarom rasters met minder aanwijzingen ook meerdere oplossingen moeten hebben.
Maar het is niet zo eenvoudig om te zien waarom een raster met 8 aanwijzingen geen unieke oplossing kan hebben, of zelfs een met 9 of meer aanwijzingen.
Dat roept een interessante vraag op voor wiskundigen: wat is het minimale aantal Sudoku-aanwijzingen dat een uniek antwoord oplevert?
Dit is een vraag die de Sudoku-gemeenschap zwaar heeft gehangen, niet in de laatste plaats omdat ze denken het antwoord te weten. Sudoku-fanaten hebben talloze voorbeelden gevonden van roosters met 17 aanwijzingen die een unieke oplossing hebben, maar ze hebben er nooit een gevonden met 16 aanwijzingen.
Dat suggereert dat het minimum aantal 17 is, maar niemand heeft kunnen bewijzen dat er geen oplossing met 16 aanwijzingen ergens in de puzzelruimte op de loer ligt.
Betreed Gary McGuire en vrienden van University College Dublin. Deze jongens hebben het probleem opgelost met behulp van de beproefde wiskundige techniek van pure brute kracht.
In wezen hebben deze jongens elke mogelijke oplossing met 16 aanwijzingen voor elk mogelijk Sudoku-raster onderzocht. "Onze zoektocht leverde geen echte puzzels met 16 aanwijzingen op, maar als er een bestond, dan hadden we die gevonden", zeggen ze.
Dat is een indrukwekkende prestatie. Er zijn precies 6, 670, 903, 752, 021, 072, 936, 960 mogelijke oplossingen voor Sudoku (ongeveer 10^21). Dat is veel meer dan in een redelijke tijd kan worden gecontroleerd.
Maar gelukkig is het niet nodig om ze allemaal te controleren. Verschillende symmetrie-argumenten bewijzen dat veel van deze roosters equivalent zijn. Dit vermindert het aantal dat moet worden gecontroleerd tot slechts 5.472, 730, 538.
Dus schreven McGuire en co een programma genaamd Checker om elk van deze roosters te controleren op een oplossing met 16 aanwijzingen.
Maar het proces van het controleren van een enkel raster is op zich al lastig. Een manier om dit te doen is door elke mogelijke subset van 16 aanwijzingen te onderzoeken om te zien of een ervan tot een unieke oplossing leidt. Het probleem is dat er zo'n 10^16 subsets zijn voor elk raster.
Nogmaals, een beetje wiskunde komt goed van pas. McGuire en co gebruikten een slimme redenering om aan te tonen dat bepaalde subsets gelijkwaardig zijn aan vele andere en dit vermindert het aantal subsets dat moet worden gecontroleerd drastisch.
Desalniettemin is de resulterende berekening nog steeds een monster. Het Dublin-team zegt dat het 7,1 miljoen core-uren aan verwerkingstijd kostte op een machine met 640 Intel Xeon hex-core processors. Ze begonnen in januari 2011 en eindigden in december.
De hele oefening klinkt misschien als een beetje wiskundig plezier, maar dit soort probleemoplossing heeft veel belangrijke toepassingen. McGuire en co zeggen dat het probleem van Sudoku-rastercontrole formeel gelijk staat aan problemen bij genexpressieanalyse en bij het testen van computernetwerken en software.
Dus de methoden van het Dublin-team om de berekening te versnellen, zullen ook op deze gebieden een directe impact hebben.
Maar hoewel het resultaat duidelijk indrukwekkend is, is het Minimum Sudoku-probleem niet helemaal tot rust gekomen.
Dit probleem schreeuwt om een elegant bewijs waarmee we kunnen "zien" waarom het minimum aantal 17 moet zijn; eerder als het bewijs dat er geen unieke oplossingen kunnen zijn voor 7 of minder aanwijzingen.
Een grote vraag, ik weet het, maar zeker de moeite waard om naar te streven.
Ref:arxiv.org/abs/1201.0749: Er is geen sudoku met 16 aanwijzingen: het oplossen van het Sudoku-probleem met het minimum aantal aanwijzingen
Correctie: dit bericht is op 6 januari bewerkt om het argument weer te geven dat als een n-aanwijzingsraster uniek oplosbaar is, het toevoegen van een cijfer om een n+1-aanwijzingsraster te maken ook uniek oplosbaar moet zijn. Dus als er geen uniek oplosbaar rooster met 16 aanwijzingen is, kunnen er geen roosters zijn met minder aanwijzingen die uniek oplosbaar zijn. Met dank aan RealMurph en abooij.