211service.com
Matematiker löser minsta Sudoku-problem
Sudoku är ett nummerpussel som består av ett 9 x 9 rutnät där vissa celler innehåller ledtrådar i form av siffror från 1 till 9. Lösarens jobb är att fylla i de återstående cellerna så att varje rad, kolumn och 3×3 ruta rutnätet innehåller alla nio siffrorna.
Det finns en annan oskriven regel: pusslet måste bara ha en lösning. Så rutnät kan inte bara innehålla några få startledtrådar.
Det är lätt att förstå varför. Ett rutnät med 7 ledtrådar kan inte ha ett unikt svar eftersom de två saknade siffrorna alltid kan bytas ut i valfri lösning. Ett liknande argument förklarar varför rutnät med färre ledtrådar också måste ha flera lösningar.
Men det är inte så lätt att se varför ett rutnät med 8 ledtrådar inte kan ha en unik lösning, eller faktiskt ett med 9 eller fler ledtrådar.
Det väcker en intressant fråga för matematiker: vad är det minsta antalet Sudoku-ledtrådar som ger ett unikt svar?
Det här är en fråga som har hängt tungt över Sudoku-gemenskapen, inte minst för att de tror att de vet svaret. Sudoku-fanatiker har hittat många exempel på rutnät med 17 ledtrådar som har en unik lösning, men de har aldrig hittat ett med 16 ledtrådar.
Det tyder på att minimitalet är 17 men ingen har kunnat bevisa att det inte finns en lösning med 16 ledtrådar som lurar någonstans i pusselrymden.
Gå in på Gary McGuire och kompisar på University College Dublin. De här killarna har löst problemet med den beprövade och pålitliga matematiska tekniken med ren brute force.
I huvudsak har dessa killar undersökt alla potentiella 16-ledtrådslösningar för alla möjliga Sudoku-rutnät. Vår sökning gav inga riktiga 16-ledtrådspussel, men hade det funnits ett så hade vi hittat det, säger de.
Det är en imponerande bedrift. Det finns exakt 6, 670, 903, 752, 021, 072, 936, 960 möjliga lösningar på Sudoku (cirka 10^21) . Det är mycket mer än vad som kan kontrolleras inom en rimlig tidsperiod.
Men som tur är är det inte nödvändigt att kontrollera dem alla. Olika symmetriargument bevisar att många av dessa rutnät är likvärdiga. Detta minskar antalet som behöver kontrolleras till bara 5, 472, 730, 538.
Så McGuire och co skrev ett program som heter Checker för att kontrollera vart och ett av dessa rutnät för en lösning med 16 ledtrådar.
Men processen att kontrollera ett enda rutnät är i sig själv knepigt. Ett sätt att göra det är att undersöka varje möjlig delmängd av 16 ledtrådar för att se om någon av dem leder till en unik lösning. Problemet är att det finns ungefär 10^16 delmängder för varje rutnät.
Återigen kommer lite matematik väl till pass. McGuire och co använde några smarta resonemang för att visa att vissa delmängder är likvärdiga med många andra och detta minskar dramatiskt antalet delmängder som behöver kontrolleras.
Ändå är den resulterande beräkningen fortfarande ett monster. Dublin-teamet säger att det tog 7,1 miljoner core-timmars behandlingstid på en maskin med 640 Intel Xeon hex-core-processorer. De startade i januari 2011 och slutade i december.
Hela övningen kan låta som lite matematisk kul men den här typen av problemlösning har många viktiga tillämpningar. McGuire och co säger att problemet med kontroll av Sudoku-rutnät formellt sett motsvarar problem i analys av genuttryck och i datornätverk och mjukvarutestning.
Så Dublin-teamets metoder för att påskynda beräkningen kommer att ha en direkt inverkan även i dessa områden.
Men även om resultatet är helt klart imponerande, är det minimala Sudoku-problemet inte helt belagt.
Detta problem ropar efter ett elegant bevis som låter oss se varför minimitalet måste vara 17; gillar snarare beviset på att det inte kan finnas några unika lösningar för 7 eller färre ledtrådar.
En stor fråga, jag vet, men säkert en värd att sikta på.
Ref: arxiv.org/abs/1201.0749 : Det finns ingen 16-ledtråd Sudoku: Lösning av Sudoku-problemet med minsta antal ledtrådar
Rättelse: det här inlägget redigerades den 6 januari för att återspegla argumentet att om ett n-ledtrådsrutnät är unikt lösbart måste det också vara unikt lösbart att lägga till en siffra för att skapa ett n+1-ledtrådsrutnät. Så om det inte finns några unikt lösbara 16-ledtrådsrutnät, kan det inte finnas några rutnät med färre ledtrådar som är unikt lösbara. Tack till RealMurph och abooij.