Spillet med sudoku består i at udfylde et firkantet gitter opdelt i N- regioner i N- bokse, delvist fyldt med tal, så i hver række, hver kolonne og hver region vises tallene fra 1 til N én og kun én gang.
En matematisk analyse af Sudoku giver dig mulighed for at opdage de forskellige egenskaber og problemer bag dette spil og dets varianter.
Den matematiske analyse af Sudoku er opdelt i to hoveddele: analysen af egenskaberne for komplette net og analysen af opløsningen af et gitter.
Meget af fokus ved analyse af net har været på at liste mulige løsninger til forskellige variationer af spillet. Undersøgelsen af løsning fokuserer på de oprindelige værdier af nettet og på trinene, der fører op til hele nettet. Disse teknikker påkalder flere discipliner: kombinatorisk analyse, algoritmisk, gruppeteori samt programmering, da computeren giver mulighed for hurtigt at løse netene.
Der er et stort antal Sudoku-variationer, som regel er kendetegnet ved størrelsen på gitteret ( N- parameteren ) og regionernes form. Klassiske sudokus har en N lig med 9 med regioner med 3 × 3 celler. En rektangulær sudoku har rektangulære regioner af størrelse L × C, hvor L er antallet af rækker og C antallet af kolonner. En sådan sudoku med en størrelse på L × 1 (eller 1 × C ) bliver en latinsk firkant, da regionen er en enkelt række eller kolonne.
Mere komplekse varianter findes som dem med uregelmæssigt skårne områder ( Nanpure ) med yderligere begrænsninger ( Samunamupure eller Killer Sudoku , respekt for unikhed på diagonalerne med Kokonotsu , begrænsninger i rækkefølgen af elementerne med Greater -Than ) eller samlinger af flere gitre ( Samurai , Sudoku i 3D). I nogle variationer erstattes tallene med bogstaver. Denne udskiftning af de anvendte tegn ændrer dog ikke puslespillets iboende egenskaber, hvis reglerne forbliver de samme.
Matematisk analyse af sudoku har fulgt populariteten af spillet Analyser vedrørende algoritmisk kompleksitet og NP-kompletitet af spillet blev dokumenteret i slutningen af 2002, optællingsresultater dukkede op omkring midten af året 2005. Bidrag fra mange forskere og amatører har gjort det muligt at opdatere spillets egenskaber. Udseendet af Sudoku-varianter udvider yderligere de matematiske elementer, der skal overvejes og udforskes.
I modsætning til de to vigtigste matematiske tilgange, der blev nævnt i begyndelsen, blev en tilgang baseret på matematisk logik og tackling af problemet med løsning af gåder for nylig foreslået i Denis Berthiers bog, "The Hidden Logic of Sudoku" skjult sudoku). Dette gjorde det muligt at opdage og formalisere alle de generelle symmetrier i spillet og opdage nye løsningsregler baseret på dem, som skjulte xy-kæder.
Problemet med at placere cifre på et n 2 × n 2 gitter med n × n regioner er NP-komplet .
Løsning af en sudoku kan formaliseres ved hjælp af problemet med graffarvning . Målet i den klassiske version af spillet er at anvende 9 farver på en given graf, fra en delvis farvning (den oprindelige konfiguration af gitteret). Denne graf har 81 hjørner, en pr. Celle. Hver af Sudoku-bokse kan mærkes med et ordnet par (x, y) , hvor x og y er heltal mellem 1 og 9. To forskellige hjørner mærket med (x, y) og (x ', y') er forbundet med hinanden en kant, hvis og kun hvis:
Gitteret afsluttes ved at tildele et helt tal mellem 1 og 9 for hvert toppunkt, så alle hjørner forbundet med en kant ikke deler det samme heltal.
Et løsningsgitter er også en latinsk firkant . Forholdet mellem de to teorier er nu fuldt kendt, da D. Berthier demonstrerede i "Den skjulte logik i Sudoku", at en logisk formel af første orden, som ikke nævner blokke (eller regioner), er gyldig for sudoku, hvis og kun hvis det er gyldigt for latinske firkanter.
Der er markant færre løsningsnet end latinske firkanter, fordi Sudoku pålægger yderligere begrænsninger (se punkt 4 nedenfor: antal mulige komplette net).
I modsætning til antallet af løsningsnet, kendes det nøjagtige antal minimumspuslespil ikke. (Et puslespil er minimalt, hvis intet afsløret ikke kan fjernes uden at gå på kompromis med løsningens unikhed.) Statistiske teknikker kombineret med definitionen af en ny type generator (kontrolleret biasgenerator (in) ) bruges imidlertid til at vise, at der er ca. (med en relativ fejl på 0,065%):
(se bogen Mønsterbaseret begrænsningstilfredshed og logiske gåder eller artiklen Unbias Statistics of a CSP - A Controlled-Bias Generator ).
Det maksimale antal afsløret uden en enkelt løsning, der straks vises, uanset variant, er størrelsen på gitteret minus 4: hvis to par kandidater ikke er registreret, og de tomme celler optager hjørnerne af et rektangel, og at nøjagtigt to celler er i en region, så er der to måder at registrere kandidater på. Det modsatte af dette problem, det mindste antal afsløringer, der garanterer en enkelt løsning, er et uløst problem, selvom japanske entusiaster har opdaget et 9 × 9-gitter uden symmetri, der kun indeholder 17 afsløringer (læs mere, se (en) ). Et resultat offentliggjort i 2007 afslører, at for at en sudoku skal have en unik løsning, skal 8 af de 9 cifre afsløres, mens 18 er det mindste antal afsløret for symmetriske 9 × 9-gitre.
Et puslespil er et ufuldstændigt gitter med indledende værdier. Regioner kaldes også blokke eller områder. Udtrykket firkant undgås for at fjerne enhver forvirring.
En strimmel er en række tilstødende blokke på den vandrette akse. En stak er en række tilstødende blokke på den lodrette akse. I en 9 × 9 firkantet sudoku er der således 3 strimler og 3 stakke.
En korrekt designet sudoku har en og kun en løsning: det endelige gitter er unikt, men løsning fra det delvise gitter kan dog tage forskellige stier.
Antallet af mulige komplette gitre er 9! × 72 2 × 2 7 × 27704267971 (dvs. 6 670 903 75202172936960 gitre ≈ 6,67 × 10 21 ).
Den sidste faktor er et primtal . Dette resultat blev bevist i 2005 af Bertram Felgenhauer og Frazer Jarvis gennem udtømmende forskning . Frazer Jarvis forenklede derefter beviset i høj grad gennem detaljeret analyse. Demonstrationen er valideret uafhængigt af Ed Russell.
Flere net er dog ækvivalente, hvis vi tager et bestemt antal symmetrier i betragtning, nemlig
(Bemærk analogien med matrixoperationer i lineær algebra ). Under hensyntagen til disse symmetrier viste Jarvis og Russell, at der var 5.472.730.538 ikke-ækvivalente net.
Omvendt findes der på denne dato ikke noget resultat på antallet af komplette gåder i en super sudoku (16 × 16 gitter).
Hvis vi nu er interesserede i antallet af mulige problemer, er dette tal klart vigtigere, fordi der er flere måder at afsløre tallene for det samme gitter.
Det mindste antal forudfyldte celler for at gøre opløsningen unik er 17; det er bevist ved beregning ijanuar 2012af et irsk hold. En liste over alle sudokus med én løsning med 17 fyldte kasser blev udarbejdet af japanere.
Svaret på spørgsmålet "Hvor mange sudoku-gåder er der?" »Afhænger af definitionen af en løsning og ækvivalensen mellem flere løsninger. Til optælling af alle mulige løsninger ( dvs. komplette net) bevarer vi følgende definition:
Et gitter A er forskelligt fra et gitter B, hvis værdien af feltet i A (i, j) er forskellig fra B (i, j), for mindst et par i, j (værdier begrænset af dimensionen af risten).
Hvis et gitter A opnås ved symmetri af gitteret B, anses de for at være forskellige. Rotationer tælles også som nye løsninger.
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
Er:
Antallet af løsninger afhænger af størrelsen på nettet, de anvendte regler og den nøjagtige definition af en separat løsning. For en sudoku med 3 × 3 regioner er konventionerne til visning af gitterindhold som følger: strimler er nummereret fra top til bund, stakke fra venstre til højre. Regionerne er derfor nummereret fra venstre mod højre og fra top til bund. Denne konvention gælder også for rektangulære net.
Andre udtryk er nyttige i tilfælde af sudoku med 3 × 3 regioner:
For eksempel svarer notationen h56 til tripletten i region 5, række 6. På engelsk bruger vi notationen r til række og c til kolonne .
Vi taler også om mini-række eller mini-kolonne for at betegne den del, der er til stede i en region af en række eller en kolonne i gitteret.
To gitre siges at være symmetrisk adskilte, hvis det ene ikke kan afledes fra det andet (ved en eller flere symmetribevaringsoperationer).
Bevaring af symmetriFølgende operationer omdanner altid et gyldigt gitter til et andet gyldigt gitter:
Disse operationer definerer et symmetriforhold mellem to ækvivalente net. Ved at udelukke skift af etiketter og ved at overveje de 81 værdier, der er til stede i gitteret, udgør disse operationer en undergruppe af den symmetriske gruppe S 81 med en rækkefølge på 3! 8 × 2 = 3.359.232.
Identificer løsninger ved hjælp af Burnsides lemmaFor en opløsning danner sættet af ækvivalente løsninger, der kan opnås ved hjælp af disse operationer (undtagen omdøbning af værdierne), en kredsløb om den symmetriske gruppe. Antallet af symmetrisk adskilte løsninger er således antallet af baner, en værdi, der kan beregnes ved hjælp af Burnsides lemma . De faste punkter i Burnsides metode er løsninger, der kun adskiller sig i omdøbning. Ved hjælp af denne teknik beregnede Jarvis Russell antallet af symmetrisk adskilte løsninger: 5.472.730.538.
For store værdier af L og C anvendes Kevin Kilfoils metode (generaliseret senere) til at estimere antallet af måder at færdiggøre et gitter på. Denne metode antager, at begrænsningerne på rækkerne og kolonnerne til en første tilnærmelse er betinget uafhængige tilfældige variabler med hensyn til begrænsningen af regionen. Algebraiske beregninger fører til formlen Kilfoil-Silver-Pettersen:
hvor b L, C er antallet af måder at færdiggøre en sudoku med L- regioner (af størrelse L × C ) vandret op til hinanden. Den Pettersen algoritme, implementeret af sølv, er i øjeblikket den hurtigste kendte teknik til præcist at vurdere b L, C -værdier .
Striptællingen for problemer, hvor "det samlede antal sudoku-gåder er ukendt" er angivet nedenfor. Som i resten af denne artikel svarer dimensionerne til regionernes.
Dimensioner | Antal bånd | Forfatter (e) | Formel verifikation |
---|---|---|---|
2 × C | (2 C )! ( C !) 2 | (indlysende) | Ja |
3 × C | Pettersen | Ja | |
4 × C | (Se nedenfor for matematiske resultater.) | Pettersen | Ja |
4 × 4 | 16! × 4! 12 × 1.273.431.960 = c. 9.7304 × 10 38 | Sølv | Ja |
4 × 5 | 20! × 5! 12 × 879.491.145.024 = c. 1,9078 × 10 55 | Russell | Ja |
4 × 6 | 24! × 6! 12 × 677 542845 061056 = c. 8.1589 × 10 72 | Russell | Ja |
4 × 7 | 28! × 7! 12 × 563690747238465024 = c. 4.6169 × 10 91 | Russell | Ja |
(Beregninger op til 4 × 100 blev udført af Silver , men vises ikke her.) | |||
5 × 3 | 15! × 3! 20 × 324408987992064 = c. 1,5510 × 10 42 | Sølv | Ja # |
5 × 4 | 20! × 4! 20 × 518 910 423730 214 314 176 = c. 5,0751 × 10 66 | Sølv | Ja # |
5 × 5 | 25! × 5! 20 × 1 165 037 550 432 885 119 709 241 344 = c. 6,9280 × 10 93 | Pettersen / sølv | Ingen |
5 × 6 | 30! × 6! 20 × 32611734691836217181002772823310336 = c. 1,2127 x 10 123 | Pettersen / sølv | Ingen |
5 × 7 | 35! × 7! 20 × 10664509989209 199 533 282 539525535 793 414 144 = c. 1,2325 x 10 154 | Pettersen / sølv | Ingen |
5 × 8 | 40! × 8! 20 × 39119289737902332276642894251428 026 550 280 700 096 = c. 4,1157 x 10 186 | Pettersen / sølv | Ingen |
Udtrykket for 4 × C-sagen er:
med:
den eksterne sum gælder for alle a , b , c således at 0 ⩽ a , b , c og a + b + c = 2 C den indre sum gælder for alle k 12 , k 13 , k 14 , k 23 , k 24 , k 34 = 0 sådan, at k 12 , k 34 = a og k 13 , k 24 = b og k 14 , k 23 = c og k 12 + k 13 + k 14 = a - k 12 + k 23 + k 24 = b - k 13 + c - k 23 + k 34 = c - k 14 + b - k 24 + a - k 34 = CDer findes flere typer begrænsninger på sudoku med 3 × 3. Regioner. Navnene er ikke standardiseret, de eksterne links peger på definitionerne:
Type | Antal gitre | Forfatter (e) | Formel verifikation |
---|---|---|---|
3doku | 104 015 259 648 | Stertenbrink | Ja |
Adskilte grupper | 201 105135151764480 | Russell | Ja |
Hypercube | 37 739 520 | Stertenbrink | Ja |
Magisk Sudoku | 5.971.968 | Stertenbrink | Ja |
Sudoku X | 55 613 393 399 531520 | Russell | Ja |
NRC Sudoku | 6 337 174 388 428 800 | Brouwer | Ja |
Alle sudokus er gyldige (entydighed af tal i rækker, kolonner og regioner) efter anvendelse af operationer, der bevarer sudoku-gruppens egenskaber. Nogle sudokus er specielle i den forstand, at nogle operationer har samme effekt som at omdøbe numre:
Transformation | Antal gitre | Forfatter (e) | Formel verifikation |
---|---|---|---|
Omrokering | 10980 179 804 160 | Russell | Indirekte |
Kvart sving | 4 737 761 280 | Indirekte | |
Halv tur | 56 425 064 693 760 | Indirekte | |
Byt bånd | 5 384 326 348 800 | Indirekte | |
Permutationer af linjer i bånd | 39 007 939 461 120 | Indirekte |
Korrekt fremstillede gitre skal have en og én løsning. Et gitter siges at være irreducerbart eller minimalt, hvis det er gyldigt, og hvis fjernelsen af et ekstra ciffer resulterer i dets ugyldighed ( dvs. det ikke længere tillader en enkelt løsning). Det er muligt at oprette minimale gitre med et andet antal indledende værdier. Dette afsnit beskriver egenskaberne, der er relateret til dette problem.
Klassisk sudoku med et 9 × 9 gitter, dvs. 81 firkanter, er i øjeblikket begrænset af en nedre grænse på 17 indledende værdier eller 18, når positionerne for de første cifre kan drejes 90 °. Der er en formodning, der siger, at denne grænse af 17 er den bedst mulige, men der er ingen formelle beviser, kun en udtømmende søgning med tilfældige net:
Yderligere begrænsninger (med sudokus, hvis regioner er 3 × 3) ændrer antallet af minimumsværdier, der er nødvendige for at komme med en enkelt løsning:
En region kan beskrives ved dens dimensioner: L × C hvor L er antallet af rækker og C antallet af kolonner i regionen. I den klassiske version af sudoku er L = C = 3. Dette betyder, at der er L- regioner pr. Strip og C- regioner pr. Stak. Det er mere praktisk at nævne størrelsen på regionen i stedet for antallet af elementer, fordi en 2 × 6-region har det samme antal kasser som en 3 × 4.
Følgende udskæring kan vedtages for groft at klassificere varianterne:
Yderligere begrænsninger gør det muligt bedre at målrette mod typen af spil.
En firkantet sudoku af N × N- regioner har flere respekterede egenskaber for alle dens underelementer, ud over den klassiske regel om ingen duplikater. Faktisk har hver række og hver kolonne et kryds med N- regioner og deler N- felter med hver af dem. Antallet af strimler og stakke er også lig med N . Rektangulær Sudoku har ikke disse egenskaber.
Sudoku med 3 × 3 regioner skjuler en anden egenskab: N er antallet af underenheder, der betragtes i spillet, nemlig tre: række, kolonne og region.
Den Du-sum-oh erstatte områder af 3 × 3 (eller mere generelt L × C) ved uregelmæssige regioner med en fast størrelse. Bob Harris beviste, at det altid er muligt at oprette du-sum-ohs med N -1 initialværdier på et N ved N- gitter . Han gav flere eksempler.
I Samunamupure eller Killer Sudoku har regionerne ikke kun uregelmæssige former, men også forskellige størrelser. Reglerne for talernes entydighed i rækker, regioner og kolonner gælder stadig. De indledende indikationer gives i form af værdisummer i regionerne (for eksempel vil en region med 4 celler med en sum af 10 indeholde cifrene 1, 2, 3, 4 i en bestemt rækkefølge). Det mindste antal nødvendige værdier for at starte nettet er hverken kendt eller formodet.
En variant foreslået af Miyuki Misawa erstatter summerne med relationer: indikationerne er symboler = , < , > , der viser de relative værdier for visse tilstødende regioner. Et eksempel med kun 8 relationer er givet, men det vides ikke, om dette tal er den nedre grænse.
Den fremgangsmåde, der er beskrevet her, er historisk den første strategi, der blev brugt til at tælle løsningerne på et klassisk sudoku-gitter (3 × 3-regioner i et 9 × 9-gitter). Det blev foreslået af Felgenhauer og Jarvis.
Analysen begynder med at studere permutationerne for det første bånd, der anvendes i gyldige løsninger. Når ækvivalensklassen og symmetrierne for dette bånd til delvise løsninger er identificeret, er vi interesserede i de to andre bånd, der konstrueres og tælles for hver ækvivalensklasse. Ved at tage summen af alle kombinationer opnår vi det samlede antal opløsninger, dvs. 6 670 903 75202172936960 (ca. 6,67 × 10 21 ).
For at reducere søgerummet antager vi, at omdøbning (for eksempel at ændre "1" til "2" og omvendt) af cellerne producerer en ækvivalent løsning. Et gitter tillader 9! = 362.880 omdøbninger af denne type: et nummer valgt blandt de 9 mulige cifre tildeles den første bokstype, et nummer fra de resterende 8 tildeles den anden boksetype, et nummer fra de resterende 7 tildeles til tredje sagsart osv.