Sudoku Blank Grid wordt gebruikt in de symmetrie van Sudoku,het omvat rijen en kolommen van 4×4,16×16 en meer met kleine en variantrasters.

Sudoku-puzzels kunnen wiskundig worden bestudeerd om vragen te beantwoorden zoals: “Hoeveel volledige Sudoku-rasters?”, “Wat is het minimum aantal hints in een echte puzzel??” en “Hoe kunnen Sudoku-rasters symmetrisch zijn??” door gebruik te maken van combinatorische en groepstheorieën.

De belangrijkste resultaten zijn dat voor klassieke Sudoku, het aantal voltooide rasters is 6,670,903,752,021,072,936,960 (6.67×1021), welke, met behoud van de geldigheid van de transformatie reduceert tot 5,472,730,538 significant verschillende groepen.

Er zijn 26 soorten symmetrie, maar ze zijn alleen te vinden in ongeveer 0.005% van alle gevulde roosters.

Een puzzel met een unieke oplossing moet minimaal hebben 17 oplossingen, en voor elk opgelost rooster zijn er niet meer dan 21 oplossingen. De grootste minimum gevonden puzzel heeft 40 aanwijzingen.

Vergelijkbare resultaten zijn bekend voor varianten en kleinere roosters. Nauwkeurige resultaten zijn niet bekender voor Sudoku's dan voor het klassieke 9×9-raster, hoewel er schattingen zijn die als redelijk nauwkeurig worden beschouwd.

Berekeningsoplossingen voor Sudoku

Een interessante vraag is:, op hoeveel manieren kan een 9 door 9 Sudoku-raster moet worden gevuld om te voldoen aan de enkele regel?

Met andere woorden, hoeveel verschillende Sudoku-oplossingen zijn er?? We beschrijven de methode die Bertram Felgenhauer en Fraser Jarvis in het begin hebben gebruikt 2006 om dit aantal te berekenen.

Om de standaard van onze taal te behouden, we noemen drie rijen blokken stroken van een raster en drie kolommen blokken stapels. Een cel in deze rij en de j-kolom wordt beschouwd als at (ik,j).

We noemen het aantal individuele roosters Sudoku N. Eerste, we noemen de rasterblokken als volgt:

Hoeveel manieren zijn er om B1 op een geldige manier in te vullen?? Aangezien er zijn 9 tekens die B1 . kunnen vullen, één in elke cel, dat is 9 opties voor de eerste cel.

Voor elk van deze 9 opties, er zijn 8 opties voor de tweede cel. Voor elk van deze 8 opties, er zijn 7 links voor de derde cel.

Eigenlijk, we berekenen het aantal permutaties van 9 karakters: hoeveel manieren we kunnen plaatsen? 9 karakters in 9 plaatsen, of hoeveel manieren we kunnen bestellen 9 dingen.

Er zijn 9 manieren om B1 in te vullen. Beginnend met een geldig B1-blok, we kunnen elk ander geldig B1-blok krijgen door nummers opnieuw te markeren of te herschikken.

Zo, de eerste vereenvoudigende veronderstelling die we kunnen maken is dat B1 gevuld is met getallen 1, 2, 3, …, 9 in volgorde, zoals hieronder weergegeven:.

Nu kunnen we berekenen hoeveel werkelijke rasteruitgangen deze specifieke B1 heeft: laten we het N1 noemen. Het totale aantal werkelijke Sudoku-rasters is N1×9!, dus N1=N/9!…

Laten we eens kijken naar de manieren om de eerste rijen in B2 en B3 te vullen. Sinds 1, 2 en 3 voorkomen in de eerste rij in B1, deze getallen kunnen niet in de andere rijen voorkomen.

daarom, alleen de cijfers 4, 5, 6, 7, 8 en 9 van de tweede en derde rij van B1 kunnen elkaar ontmoeten in de eerste rij in B2 en B3.

Maak een lijst van alle mogelijke manieren om de eerste rijen in B2 en B3 te vullen, tot het herschikken van de nummers in elk blok. Tip: Er zijn tien manieren om dit te doen, zodat de uitwisseling van B2 en B3 deze tien manieren je nog tien manieren gaf, in totaal twintig.

Twee van deze mogelijkheden noemen we pure toplijnen: wanneer nummers {4,5,6}, zoals in de tweede rij van B1, worden samen opgeslagen in B2, en cijfers {7,8,9}, zoals in de derde rij van B1, worden samen opgeslagen in B3, en een gewijzigde versie hiervan.

De andere mogelijkheden zijn gemengde toplijnen, terwijl ze de sets mixen {4,5,6} en {7,8,9} wanneer gebruikt om de eerste regels van B2 en B3 te vullen.

Gezien deze twintig mogelijkheden voor de eerste regel van het raster (tot het herschikken van de nummers in elk blok), we kunnen uitzoeken hoe we de eerste regel kunnen vullen.

Bedenk hoe je de eerste band kunt voltooien, beginnend met de pure bovenste rij 1,2,3;{4,5,6};{7,8,9}.

(Notitie: We schrijven een,b,c om een ​​geordend drievoud van getallen aan te duiden en {een,b,c} om ze in willekeurige volgorde aan te duiden.)

Hoeveel totale mogelijkheden zijn er?, het tellen van verschillende nummervolgorde binnen elke rij in B2 en B3? Is dit nummer hetzelfde als voor de andere zuivere bovenste rij?, 1,2,3;{7,8,9};{4,5,6}?

Onthouden, we willen B1 vast houden omdat we al rekening hebben gehouden met het aantal rasters dat kan worden verkregen door de negen cijfers erin te herlabelen.

Het blijkt dat er zijn (3!)⁶ manieren om de eerste band te voltooien door te staren met de pure bovenste rij 1,2,3;{4,5,6};{7,8,9}.

Dit komt omdat we genoodzaakt zijn om te zetten {7,8,9};{1,2,3} op de tweede rij in B2 en B3 en {1,2,3};{4,5,6} op de derde rij, en dan kunnen we de drie cijfers in elk van de zes rijen van B2 en B3 opnieuw ordenen om alle configuraties te krijgen.

Het antwoord is hetzelfde voor de andere pure bovenste rij, aangezien in dit geval alles wat we hebben gedaan is verwisseld B2 met B3.

De gevallen van de gemengde bovenste rijen zijn ingewikkelder. Laten we eens kijken naar de bovenste rij 1,2,3;{4,6,8};{5,7,9}. Dit kan worden aangevuld tot de eerste band zoals in de volgende afbeelding:, waar een, b, en c zijn de getallen 1, 2, 3 in elke volgorde.

Na het selecteren van een, b en c zijn de twee resterende getallen in willekeurige volgorde, omdat ze in dezelfde rij staan.

Aangezien er drie opties zijn voor a, en drie cijfers in elk van de zes sets in B2 en B3 kunnen worden overgeslagen om verschillende geldige voorpagina's te krijgen, het totale aantal configuraties is in dit geval 3×(3!)6.

U kunt op dezelfde manier door elk van de resterende zeventien zaken op de eerste rij werken om hetzelfde aantal te krijgen.

Nu hebben we het aantal mogelijke voorpagina's gedefinieerd door B1: dit is 2×(3!)6+18×3×(3!)6=2612736, waarbij het eerste deel van de som het aantal voltooide eerste pagina's is van de netto bovenste rijen en het tweede het aantal voltooide eerste pagina's van de gemengde bovenste rijen.

In plaats van te berekenen hoeveel voorpagina voltooiingen van elk van deze 2612736 Kenmerken, Felgenhauer en Jarvis bepaalden welke voorpagina's hetzelfde aantal eerste pagina's hebben ingevuld vanaf de bovenste blanco.

Deze analyse vermindert het aantal voorpagina's waarmee rekening moet worden gehouden bij de berekening.

Hier zijn enkele bewerkingen die het aantal eindes van het eerste bereikraster ongewijzigd laten: de cijfers opmerken, luisteren naar een van de blokken in het eerste bereik, luisteren naar de kolommen in een willekeurig blok en luisteren naar de drie rijen van het bereik. Met een van deze B1-wijzigingen, we kunnen de nummers opnieuw markeren om de standaardvorm te herstellen.

B1 . arrangeren, B2 en B3 behouden het aantal rastereinden, want als we beginnen met een echt Sudoku-raster, de enige manier om het echt te houden, is door B4 te markeren, B5, B6 en B7, B8, B9 respectievelijk zodat de stapels hetzelfde blijven.

Met andere woorden, elke werkelijke afsluiting van het voorpaginaraster geeft precies één werkelijke afsluiting van het voorpaginaraster, d.w.z.. elke B1, B2, B3 permutatie.
Zorg ervoor dat wanneer u B2 in B3 verandert in het volgende Sudoko-raster, de enige manier om het raster geldig te houden, is door B5 te veranderen in B6 en B7 in B8. Hierdoor blijven de stapels hetzelfde, hoewel hun locatie is veranderd.

Als je een geldig Sudoku-raster hebt en je slaat kolommen over in een van B1, B2 en B3, wat zou je moeten doen met de kolommen van de rest van het Sudoku-raster om het geldig te houden?? Bijvoorbeeld, als je kolommen hebt gewijzigd 1 en 2 van B2 op het bovenstaande rooster, hoe zou je het resulterende raster repareren zodat het voldoet aan de ene regel??

De laatste oefening vertelt ons dat elke vulling van het raster van de eerste rij een unieke vulling van het raster van de eerste rij geeft met kolommen die binnen de blokken zijn overgeslagen.

Dergelijke overwegingen stellen ons in staat om het aantal specifieke voorpagina's waarmee rekening moet worden gehouden bij het tellen te verminderen.

In navolging van Felgenhauer en Jarvis, we scrollen door de B2- en B3-kolommen zodat de bovenste rij-items van elke kolom in oplopende volgorde staan, en verwissel vervolgens B2 en B3 indien nodig, zodat de eerste B2-invoer kleiner is dan de B3-invoer.

Dit wordt lexicografische afkorting genoemd.

Aangezien elk van de twee blokken heeft 6 herschikkingen van kolommen en twee manieren om blokken te herschikken, de lexicografische steno vertelt ons dat:, gezien de eerste pagina, er zijn 62×2=72 andere voorpagina's met hetzelfde aantal rasteruitgangen.

Dus nu hebben we alleen 2612736/72=36288 voorpagina's om te overwegen.

Laten we voor elk van deze mogelijkheden eens kijken naar de herschikkingen van alle drie de bovenste blokken: er zijn 6. Voor elk van hen zijn er 63 herschikkingen van kolommen binnen elk blok.

Na het uitvoeren van deze bewerkingen, we markeren opnieuw om B1 terug te brengen naar zijn standaardvorm.

evenzo, we kunnen de bovenste drie regels van de groep overschrijven en opnieuw markeren om B1 terug te brengen naar een standaardformulier. Met deze bewerkingen wordt het aantal voltooide rasters op de eerste rij opgeslagen.

Felgenhauer en Jarvis gebruikten een computerprogramma om te bepalen dat deze operaties het aantal voorpagina's dat in aanmerking moet worden genomen, verminderen 36288 om alleen 416.

Laten we eens kijken naar deze eerste groep.

Voer er verschillende bewerkingen op uit die het aantal rastereindes opslaan. U kunt beginnen met het volgende:: Wissel de eerste en tweede rij om. Markeer het opnieuw zodat B1 in zijn standaardvorm staat. Verklein dit raster lexicografisch.

Het belangrijkste is dat de groep waarmee je begon en de andere groep waarmee je eindigde hetzelfde aantal voltooiingen hebben tot aan het volledige Sudoku-raster.

Dus, in plaats van het aantal eindes van het raster voor elk van deze groepen te berekenen, we kunnen het maar voor één ervan berekenen.

Er zijn meer stappen die het aantal te overwegen rasters verminderen. Als we een paar cijfers hebben {een,b} in één kolom met a in een i-de rij en b in een j-de rij, en hetzelfde paar in een andere kolom met b in een i-de rij en a in een j-de rij, elk paar heeft een band met hetzelfde aantal rasteruiteinden als het origineel.

Dit komt omdat elk paar in dezelfde kolom ligt, en wanneer beide tegelijkertijd worden gewijzigd, een enkele regel is opgeslagen, die ook voldoet aan de betrokken rijen.

Als voorbeeld, kijk naar cijfers 8 en 9 in de zesde en negende kolom van het bovenstaande voorbeeld. Overweeg alle mogelijke gevallen hiervan lieten Felgenhauer en Jarvis achter met: 174 van de eerste 416 groepen om mee verder te gaan.

Ze hebben ook andere configuraties van dezelfde reeks getallen overwogen die in twee verschillende kolommen of rijen liggen, die kunnen worden weggelaten in hun kolommen of rijen, het aantal rasteruitgangen onveranderlijk laten.

Dit verminderde het aantal voorpagina's tot 71, en de zoektocht naar elk van deze 71 gevallen maakten hen duidelijk dat er eigenlijk alleen 44 voorpagina's waarvan het aantal rasteraanvullingen te vinden is.

Elk van deze 44 bands heeft hetzelfde aantal eindes als het volledige raster.

Laat C een van deze aanduiden 44 strepen. Vervolgens kun je het aantal manieren berekenen waarop C het volledige Sudoku-raster kan voltooien: noem het nc.

We hebben ook het aantal mC-voorpagina's nodig die dit aantal nC-uitgangen van het raster delen. Dan, het totale aantal Sudoku-rasters is slechts N=ΣCmCnC, of de som van mCnC voor iedereen 44 strepen.

Felgenhauer en Jarvis schreven een computerprogramma om de laatste berekeningen te doen.

Ze berekenden het aantal N1 geldige aanvullingen met B1 in een standaardformulier, beginnend met 44 rijstroken. Daarna vermenigvuldigden ze dit getal met 9! om een ​​antwoord te krijgen.

Ze ontdekten dat het aantal mogelijke 9 door 9 Sudoku-rasters is N=6670903752021072936960, dat is ongeveer 6.671 × 1021.

Artikel- en afbeeldingscredits:

http://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html