Matematikere løser minimalt Sudoku-problem

Sudoku er et talpuslespil bestående af et 9 x 9 gitter, hvor nogle celler indeholder ledetråde i form af cifre fra 1 til 9. Løserens opgave er at udfylde de resterende celler, så hver række, kolonne og 3×3 boks i gitteret indeholder alle ni cifre.

Der er en anden uskreven regel: puslespillet skal kun have én løsning. Så gitter kan ikke kun indeholde nogle få startspor.

Det er nemt at se hvorfor. Et gitter med 7 ledetråde kan ikke have et entydigt svar, fordi de to manglende cifre altid kan ombyttes i enhver løsning. Et lignende argument forklarer, hvorfor gitter med færre ledetråde også skal have flere løsninger.

Men det er ikke så let at se, hvorfor et gitter med 8 ledetråde ikke kan have en unik løsning, eller faktisk et med 9 eller flere ledetråde.

Det rejser et interessant spørgsmål for matematikere: hvad er minimumsantallet af Sudoku-spor, der giver et unikt svar?

Det er et spørgsmål, der har hængt tungt over Sudoku-miljøet, ikke mindst fordi de tror, ​​de kender svaret. Sudoku-fanatikere har fundet adskillige eksempler på gitter med 17 ledetråde, der har en unik løsning, men de har aldrig fundet et med 16 ledetråde.

Det tyder på, at minimumsantallet er 17, men ingen har været i stand til at bevise, at der ikke er en løsning med 16 ledetråde, der lurer et sted i puslespillet.

Indtast Gary McGuire og venner på University College Dublin. Disse fyre har løst problemet ved at bruge den afprøvede og pålidelige matematiske teknik med ren og skær brute force.

I det væsentlige har disse fyre undersøgt alle potentielle 16-ledetrådsløsninger for alle mulige Sudoku-gitter. Vores søgning viste ingen ordentlige 16-ledetråds-puslespil, men havde en eksisteret, så havde vi fundet den, siger de.

Det er en imponerende bedrift. Der er præcis 6, 670, 903, 752, 021, 072, 936, 960 mulige løsninger til Sudoku (ca. 10^21) . Det er langt mere, end der kan kontrolleres inden for en rimelig periode.

Men som heldet ville have det, er det ikke nødvendigt at tjekke dem alle. Forskellige symmetriargumenter beviser, at mange af disse gitre er ækvivalente. Dette reducerer antallet, der skal kontrolleres, til blot 5, 472, 730, 538.

Så McGuire og co skrev et program kaldet Checker for at tjekke hver enkelt af disse tavler for en 16-ledetråds løsning.

Men processen med at kontrollere et enkelt gitter er i sig selv vanskelig. En måde at gøre det på er at undersøge alle mulige undergrupper af 16 spor for at se, om nogen af ​​dem fører til en unik løsning. Problemet er, at der er nogle 10^16 undersæt for hvert gitter.

Endnu en gang kommer lidt matematik godt med. McGuire og co brugte nogle smarte ræsonnementer til at vise, at visse delmængder svarer til mange andre, og dette reducerer dramatisk antallet af delmængder, der skal kontrolleres.

Ikke desto mindre er den resulterende beregning stadig et monster. Dublin-teamet siger, at det tog 7,1 millioner core-timers behandlingstid på en maskine med 640 Intel Xeon hex-core-processorer. De startede i januar 2011 og sluttede i december.

Hele øvelsen lyder måske som en smule matematisk sjov, men denne form for problemløsning har mange vigtige anvendelser. McGuire og co siger, at problemet med kontrol af Sudoku-netværk formelt svarer til problemer i genekspressionsanalyse og i computernetværk og softwaretest.

Så Dublin-teamets metoder til at fremskynde beregningen vil også have en direkte indvirkning på disse områder.

Men selvom resultatet klart er imponerende, er Minimum Sudoku-problemet ikke helt lagt til hvile.

Dette problem råber på et elegant bevis, der giver os mulighed for at se, hvorfor minimumsantallet skal være 17; snarere som beviset på, at der ikke kan være entydige løsninger for 7 eller færre spor.

Et stort spørgsmål, jeg ved det, men det er helt sikkert værd at sigte efter.

Ref: arxiv.org/abs/1201.0749 : Der er ingen 16-ledetråd Sudoku: Løsning af Sudoku-minimumsantallet af ledetråde-problem

Rettelse: dette indlæg blev redigeret den 6. januar for at afspejle argumentet om, at hvis et n-ledtrådsgitter er unikt løseligt, så skal tilføjelse af et ciffer for at lave et n+1-ledtrådsgitter også være unikt løseligt. Så hvis der ikke er nogen unikt løselige 16-ledetråds-gitre, kan der ikke være nogen gitre med færre ledetråde, der er entydigt løselige. Tak til RealMurph og abooij.

skjule