Kio Estas La Aritmetiko Malantaŭ La Malplena Krado de Sudoku?

Sudoku Blank Grid estas uzita en la Simetrio de Sudoku,ĝi implicas vicon kaj kolumnojn de 4×4,16×16 kaj pli kun malgrandaj kaj variaj kradoj.

Sudoku-enigmoj povas esti studitaj matematike por respondi demandojn kiel ekzemple “Kiom da plenaj Sudoku-kradoj?”, “Kio estas la minimuma nombro da sugestoj en vera enigmo?” kaj “Kiel Sudoku-kradoj povas esti simetriaj?” uzante kombinecajn kaj grupajn teoriojn.

La ĉefaj rezultoj estas tiuj por klasika Sudoku, la nombro da finitaj kradoj estas 6,670,903,752,021,072,936,960 (6.67×1021), kiu, retenante la validecon de la transformo reduktas al 5,472,730,538 signife malsamaj grupoj.

Estas 26 specoj de simetrio, sed ili troviĝas nur en ĉirkaŭ 0.005% de ĉiuj plenigitaj kradoj.

Enigmo kun unika solvo devas havi almenaŭ 17 solvoj, kaj por ĉiu solvita krado estas ne pli ol 21 solvoj. La plej granda minimuma trovita enigmo havas 40 postsignoj.

Similaj rezultoj estas konataj pro variaĵoj kaj pli malgrandaj kradoj. Precizaj rezultoj ne estas konataj por Sudokoj pli ol la klasika 9×9 krado, kvankam ekzistas taksoj kiuj estas konsiderataj sufiĉe precizaj.

Kalkulaj Solvoj Al Sudoku

Interesa demando estas, kiom da manieroj povas a 9 de 9 Sudoku-krado estu plenigita por kontentigi la Ununuran Regulon?

Alivorte, kiom da malsamaj Sudoku-solvoj ekzistas? Ni priskribas la metodon uzatan de Bertram Felgenhauer kaj Fraser Jarvis frue 2006 por kalkuli ĉi tiun nombron.

Por konservi la normon de nia lingvo, ni nomas tri vicojn de blokoj strioj de krado kaj tri kolumnoj de blokoj stakoj. Ĉelo en ĉi tiu vico kaj la j-kolumno estas konsiderata kiel ĉe (mi,j).

Ni nomas la nombron da individuaj kradoj Sudoku N. Unue, ni nomas la kradblokojn jene:

Kiom da manieroj ekzistas por plenigi B1 en valida maniero? Ĉar ekzistas 9 signoj kiuj povas plenigi B1, unu en ĉiu ĉelo, tio estas 9 opcioj por la unua ĉelo.

Por ĉiu el ĉi tiuj 9 opcioj, estas 8 opcioj por la dua ĉelo. Por ĉiu el ĉi tiuj 8 opcioj, estas 7 foriris al la tria ĉelo.

Esence, ni kalkulas la nombron da permutaĵoj de 9 karakteroj: kiom da manieroj ni povas loki 9 karakteroj en 9 lokoj, aŭ kiom da manieroj ni povas mendi 9 aferojn.

Estas 9 manieroj plenigi B1. Komencante kun valida B1-bloko, ni povas akiri ajnan alian validan B1-blokon per remarko aŭ rearanĝo de nombroj.

Do, la unua simpliga supozo kiun ni povas fari estas ke B1 estas plenigita kun nombroj 1, 2, 3, …, 9 en ordo, kiel montrite sube.

Nun ni povas kalkuli kiom da realaj kradaj finaĵoj havas ĉi tiu aparta B1: ni nomu ĝin N1. La tutsumo de realaj Sudoku-kradoj estas N1×9!, do N1=N/9!…

Ni konsideru la manierojn plenigi la unuajn vicojn en B2 kaj B3. Ekde 1, 2 kaj 3 okazas en la unua vico en B1, ĉi tiuj nombroj ne povas okazi en la aliaj vicoj.

Tial, nur la nombroj 4, 5, 6, 7, 8 kaj 9 de la dua kaj tria vicoj de B1 povas renkonti en la unua vico en B2 kaj B3.

Listigu ĉiujn eblajn manierojn plenigi la unuajn vicojn en B2 kaj B3, ĝis rearanĝi la nombrojn en ĉiu bloko. Konsileto: Estas dek manieroj fari tion, por ke la interŝanĝo de B2 kaj B3 ĉi tiuj dek manieroj donis al vi dek pliajn manierojn., entute dudek.

Ni nomas du el ĉi tiuj eblecoj puraj supraj linioj: kiam nombroj {4,5,6}, kiel en la dua vico de B1, estas stokitaj kune en B2, kaj nombroj {7,8,9}, kiel en la tria vico de B1, estas stokitaj kune en B3, kaj ŝanĝita versio de ĉi tio.

La aliaj eblecoj estas miksitaj supraj linioj, dum ili miksas la arojn {4,5,6} kaj {7,8,9} kiam uzata por plenigi la unuajn liniojn de B2 kaj B3.

Donitaj ĉi tiuj dudek eblecoj por la unua linio de la krado (ĝis rearanĝi la nombrojn en ĉiu bloko), ni povas eltrovi kiel plenigi la unuan linion.

Pensu pri kiel vi povas kompletigi la unuan bandon komencante per la pura supra vico 1,2,3;{4,5,6};{7,8,9}.

(Notu: Ni skribas a,b,c por indiki ordigitan triopon de nombroj kaj {a,b,c} por indiki ilin en ajna ordo.)

Kiom da totalaj eblecoj estas, nombrante malsamajn nombromendojn ene de ĉiu vico en B2 kaj B3? Ĉu ĉi tiu nombro estas la sama kiel por la alia pura supra vico, 1,2,3;{7,8,9};{4,5,6}?

Memoru, ni volas teni B1 fiksita ĉar ni jam kalkulis la nombron da kradoj, kiuj povas esti akiritaj per remarkado de la naŭ ciferoj en ĝi..

Montriĝas, ke ekzistas (3!)⁶ manieroj kompletigi la unuan bandon fiksrigardante kun la pura supra vico 1,2,3;{4,5,6};{7,8,9}.

Ĉi tio estas ĉar ni estas devigitaj meti {7,8,9};{1,2,3} en la dua vico en B2 kaj B3 kaj {1,2,3};{4,5,6} en la tria vico, kaj tiam ni povas reordigi la tri ciferojn en ĉiu el la ses vicoj de B2 kaj B3 por ricevi ĉiujn agordojn.

La respondo estas la sama por la alia pura supra vico, ĉar ĉi-kaze ĉio, kion ni faris, estas interŝanĝita B2 kun B3.

La kazoj de la miksitaj supraj vicoj estas pli komplikaj. Ni konsideru la supran vicon 1,2,3;{4,6,8};{5,7,9}. Ĉi tio povas esti kompletigita al la unua bando kiel en la sekva bildo, kie a, b, kaj c estas la nombroj 1, 2, 3 en ajna ordo.

Post elekto de a, b kaj c estas la du ceteraj nombroj en ajna ordo, ĉar ili estas en la sama vico.

Ĉar estas tri ebloj por a, kaj tri ciferoj en ĉiu el la ses aroj en B2 kaj B3 povas esti preterlasitaj por akiri malsamajn validajn frontpaĝojn, la totala nombro de agordoj en ĉi tiu kazo estas 3×(3!)6.

Vi povas simile labori tra ĉiu el la ceteraj dek sep frontvicaj kazoj por akiri la saman nombron.

Nun ni havas la nombron da eblaj frontpaĝoj difinitaj de B1: ĉi tio estas 2×(3!)6+18×3×(3!)6=2612736, kie la unua parto de la sumo estas la nombro da unuaj paĝaj kompletigoj de la retaj supraj vicoj kaj la dua estas la nombro da unuaj paĝaj kompletigoj de la miksitaj supraj vicoj.

Anstataŭ kalkuli kiom da frontpaĝaj kompletigoj de ĉiu el ĉi tiuj 2612736 Trajtoj, Felgenhauer kaj Jarvis determinis kiuj frontpaĝoj havas la saman nombron da unuapaĝaj kompletigoj de la supra malplena.

Ĉi tiu analizo reduktas la nombron da ĉefpaĝoj konsiderendaj dum kalkulado.

Jen kelkaj operacioj, kiuj lasas la nombron da finaĵoj de la unua intervala krado senŝanĝa: rimarkante la nombrojn, aŭskultante iun el la blokoj en la unua gamo, aŭskultante la kolumnojn en iu ajn bloko kaj aŭskultante la tri vicojn de la gamo. Kun iu el ĉi tiuj B1-ŝanĝoj, ni povas remarki la nombrojn por restarigi ĝian norman formon.

Aranĝo B1, B2 kaj B3 konservas la nombron da kradaj finaĵoj, ĉar se ni komencas per iu reala Sudoku-krado, la sola maniero konservi ĝin reala estas marki B4, B5, B6 kaj B7, B8, B9 respektive tiel ke la stakoj restu la samaj.

Alivorte, ĉiu reala frontpaĝa kradfino donas precize unu realan frontpaĝan kradfinon, t.e. ajna B1, B2, B3-permutaĵo.
Certigu tion kiam vi ŝanĝas B2 al B3 en la sekva Sudoko-krado, la nura maniero konservi la kradon valida estas ŝanĝi B5 al B6 kaj B7 al B8. Ĉi tio konservos la stakojn samaj, kvankam ilia loko ŝanĝiĝis.

Se vi havas validan Sudoku-kradon kaj vi preterlasas kolumnojn en iu ajn el B1, B2 kaj B3, kion vi devus fari kun la kolumnoj de la resto de la Sudokua krado por konservi ĝin valida? Ekzemple, se vi ŝanĝis kolumnojn 1 kaj 2 de B2 sur la supra krado, kiel vi riparus la rezultan kradon tiel ke ĝi kontentigas la Unu Regulon?

La lasta ekzerco diras al ni, ke ĉiu plenigo de la antaŭa vica krado donas unikan plenigon de la antaŭa vica krado kun kolumnoj saltitaj ene de la blokoj..

Tiaj konsideroj permesas al ni redukti la nombron de specifaj frontpaĝoj konsiderendaj dum kalkulado.

Sekvante Felgenhauer kaj Jarvis, ni rulumu tra la B2 kaj B3-kolumnoj tiel, ke la supraj vicoj de ĉiu kolumno estu en kreskanta ordo, kaj tiam interŝanĝu B2 kaj B3 se necese tiel ke la unua B2-eniro estas pli malgranda ol la B3-eniro.

Tio estas nomita leksikografia mallongigo.

Ĉar ĉiu el la du blokoj havas 6 rearanĝoj de kolonoj kaj du manieroj rearanĝi blokojn, la leksikografia stenografio diras al ni tion, donita la unuan paĝon, estas 62×2=72 aliaj frontpaĝoj kun la sama nombro da kradaj finaĵoj.

Do nun ni havas nur 2612736/72=36288 frontpaĝojn por konsideri.

Por ĉiu el ĉi tiuj eblecoj ni rigardu la rearanĝojn de ĉiuj tri supraj blokoj: estas 6. Por ĉiu el ili ekzistas 63 rearanĝoj de kolonoj ene de ĉiu bloko.

Post plenumi ĉi tiujn operaciojn, ni remarku por reveni B1 al ĝia norma formo.

simile, ni povas superregi la tri suprajn liniojn de la grupo kaj remarki por reveni B1 al norma formo. Tiuj operacioj ŝparas la nombron da frontvicaj kradkompletigoj.

Felgenhauer kaj Jarvis uzis komputilan programon por determini ke tiuj operacioj reduktas la nombron da frontpaĝoj por esti pripensitaj de 36288 al nur 416.

Ni konsideru ĉi tiun unuan grupon.

Faru diversajn operaciojn sur ĝi, kiuj konservas ĝian nombron da kradaj finaĵoj. Vi povas komenci per la jenaj: Interŝanĝu la unuan kaj la duan vicon. Remarku ĝin tiel ke B1 estas en sia norma formo. Leksikografie reduktu ĉi tiun kradon.

La ĉefa afero estas, ke la grupo kun kiu vi komencis kaj la alia grupo kun kiu vi finis havas la saman nombron da kompletigoj ĝis la plena Sudoku-krado..

Tiel, anstataŭ kalkuli la nombron da finaĵoj de la krado por ĉiu el ĉi tiuj grupoj, ni povas ĝin kalkuli nur por unu el ili.

Estas pli da paŝoj kiuj reduktas la nombron de kradoj por konsideri. Se ni havas paron da ciferoj {a,b} en unu kolumno kun a en i-a vico kaj b en j-a vico, kaj la sama paro en alia kolumno kun b en i-a vico kaj a en j-a vico, ĉiu paro havos bandon kun la sama nombro da kradaj finaĵoj kiel la originalo.

Ĉi tio estas ĉar ĉiu paro kuŝas en la sama kolumno, kaj kiam ambaŭ estas ŝanĝitaj samtempe, ununura regulo estas konservita, kiu ankaŭ kontentigas la koncernajn vicojn.

Kiel ekzemplo, rigardu nombrojn 8 kaj 9 en la sesa kaj naŭa kolumnoj de la supra ekzemplo. Konsideru ĉiujn eblajn kazojn de ĉi tiu maldekstra Felgenhauer kaj Jarvis kun 174 Disvolvu Pozitivajn Kutimojn por Konfido 416 grupoj por daŭrigi.

Ili ankaŭ pripensis aliajn agordojn de la sama aro de nombroj kuŝantaj en du malsamaj kolumnoj aŭ vicoj, kiuj povas esti preterlasitaj ene de siaj kolumnoj aŭ vicoj, lasante la nombron da kradaj finaĵoj senvaria.

Ĉi tio reduktis la nombron da frontpaĝoj al 71, kaj la serĉo por ĉiu el ĉi tiuj 71 kazoj klarigis al ili, ke efektive ekzistas nur 44 frontpaĝoj, kies nombro da kradaj kompletigoj troveblas.

Ĉiu el ĉi tiuj 44 bandoj havas la saman nombron da finaĵoj al la plena krado.

Estu C signi unu el ĉi tiuj 44 strioj. Tiam vi povas kalkuli la nombron da manieroj, kiujn C povas kompletigi al la plena Sudokua krado: nomi ĝin nc.

Ni ankaŭ bezonas la nombron da mC frontpaĝoj kiuj kunhavas ĉi tiun nombron da nC finaĵoj de la krado. Tiam, la tutsumo de Sudoku-kradoj estas nur N=ΣCmCnC, aŭ la sumo de mCnC por ĉiuj 44 strioj.

Felgenhauer kaj Jarvis skribis komputilan programon por fari la finajn kalkulojn.

Ili kalkulis la nombron da N1 validaj kompletigoj kun B1 en norma formo, komencante per 44 lenoj. Tiam ili multobligis ĉi tiun nombron per 9! por ricevi respondon.

Ili trovis ke la nombro de ebla 9 de 9 Sudoku-kradoj estas N=6670903752021072936960, kiu estas proksimume 6.671×1021.

Artikolo Kaj Bilda Kredito:

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