211service.com
Wiskundigen lossen minimum Sudoku-probleem op
Sudoku is een cijferpuzzel bestaande uit een raster van 9 x 9 waarin sommige cellen aanwijzingen bevatten in de vorm van cijfers van 1 tot 9. Het is de taak van de oplosser om de resterende cellen in te vullen zodat elke rij, kolom en 3×3 vak in het raster bevat alle negen cijfers.
Er is nog een ongeschreven regel: de puzzel mag maar één oplossing hebben. Dus rasters kunnen niet slechts een paar startaanwijzingen bevatten.
Het is gemakkelijk te zien waarom. Een raster met 7 aanwijzingen kan geen uniek antwoord hebben, omdat de twee ontbrekende cijfers altijd in elke oplossing kunnen worden verwisseld. Een soortgelijk argument verklaart waarom rasters met minder aanwijzingen ook meerdere oplossingen moeten hebben.
Maar het is niet zo eenvoudig in 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 minimum aantal Sudoku-aanwijzingen dat een uniek antwoord oplevert?
Dit is een vraag die zwaar boven de Sudoku-gemeenschap hangt, niet in de laatste plaats omdat ze denken het antwoord te weten. Sudoku-fanaten hebben talloze voorbeelden gevonden van rasters 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 ergens in de puzzelruimte geen oplossing met 16 aanwijzingen op de loer ligt.
Voer Gary McGuire en vrienden op University College Dublin in. Deze jongens hebben het probleem opgelost met behulp van de beproefde en vertrouwde 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 van 16 aanwijzingen op, maar als er een had bestaan, dan hadden we hem 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 binnen een redelijke termijn kan worden gecontroleerd.
Maar zoals het geluk zou hebben, is het niet nodig om ze allemaal te controleren. Verschillende symmetrie-argumenten bewijzen dat veel van deze rasters equivalent zijn. Dit reduceert het aantal dat moet worden gecontroleerd tot slechts 5, 472, 730, 538.
Dus McGuire en co schreven een programma genaamd Checker om elk van deze rasters te controleren op een oplossing met 16 aanwijzingen.
Maar het proces van het controleren van een enkel raster is zelf lastig. Een manier om dit te doen is om elke mogelijke subset van 16 aanwijzingen te onderzoeken om te zien of een van hen tot een unieke oplossing leidt. Het probleem is dat er voor elk raster zo'n 10^16 subsets zijn.
Nogmaals, een beetje wiskunde komt van pas. McGuire en co gebruikten een slimme redenering om aan te tonen dat bepaalde subsets equivalent 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 de analyse van genexpressie 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 minimumaantal 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 een die het waard is om naar te streven.
Referentie: arxiv.org/abs/1201.0749 : Er is geen Sudoku met 16 aanwijzingen: het probleem met het minimumaantal aanwijzingen voor Sudoku oplossen
Correctie: dit bericht is op 6 januari aangepast 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 oplosbare rasters met 16 aanwijzingen zijn, kunnen er ook geen rasters zijn met minder aanwijzingen die uniek oplosbaar zijn. Met dank aan RealMurph en abooij.