Hesabu Ni Nini Nyuma Ya Gridi Tupu ya Sudoku?

Gridi tupu ya Sudoku inatumika katika Ulinganifu wa Sudoku,inajumuisha safu na safu wima za 4x4,16×16 na zaidi na gridi ndogo na lahaja..

Mafumbo ya Sudoku yanaweza kusomwa kimahesabu kujibu maswali kama vile “Ni gridi ngapi za Sudoku kamili?”, “Ni idadi gani ya chini ya vidokezo katika fumbo halisi?” na “Gridi za Sudoku zinawezaje kuwa linganifu?” kwa kutumia nadharia za ujumuishaji na za vikundi.

Matokeo kuu ni yale ya Sudoku ya kawaida, idadi ya gridi zilizokamilishwa ni 6,670,903,752,021,072,936,960 (6.67×1021), ambayo, wakati kubakiza uhalali wa mabadiliko inapunguza 5,472,730,538 kwa kiasi kikubwa vikundi tofauti.

Kuna 26 aina za ulinganifu, lakini zinaweza kupatikana tu karibu 0.005% ya gridi zote zilizojaa.

Kitendawili chenye suluhu la kipekee lazima kiwe na angalau 17 ufumbuzi, na kwa kila kimiani kutatuliwa hakuna zaidi ya 21 ufumbuzi. Kiwango cha chini kabisa cha fumbo kilichopatikana kina 40 dalili.

Matokeo sawa yanajulikana kwa vibadala na gridi ndogo. Matokeo sahihi hayajulikani kwa Sudokus zaidi ya gridi ya classical 9×9, ingawa kuna makadirio ambayo yanachukuliwa kuwa sahihi.

Suluhisho la Mahesabu Kwa Sudoku

Swali la kuvutia ni, ni njia ngapi a 9 na 9 Gridi ya Sudoku ijazwe ili kukidhi Utawala Mmoja?

Kwa maneno mengine, ni suluhisho ngapi tofauti za Sudoku zipo? Tunaelezea njia iliyotumiwa na Bertram Felgenhauer na Fraser Jarvis mapema 2006 kuhesabu nambari hii.

Ili kudumisha kiwango cha lugha yetu, tunaita safu tatu za vitalu vipande vya gridi ya taifa na safu tatu za safu za vitalu. Seli katika safu mlalo hii na safu wima ya j inachukuliwa kuwa iko (i,lakini haifanyi yaliyomo katika hisabati kuwa tofauti).

Tunaita nambari ya gridi za kibinafsi Sudoku N. Kwanza, tunaita vitalu vya gridi ya taifa kama ifuatavyo:

Kuna njia ngapi za kujaza B1 kwa njia halali? Kwa kuwa wapo 9 wahusika ambao wanaweza kujaza B1, moja katika kila seli, hiyo ni 9 chaguzi kwa seli ya kwanza.

Kwa kila moja ya haya 9 chaguzi, kuna 8 chaguzi kwa seli ya pili. Kwa kila moja ya haya 8 chaguzi, kuna 7 kushoto kwa seli ya tatu.

Kimsingi, tunahesabu idadi ya vibali vya 9 wahusika: njia ngapi tunaweza kuweka 9 wahusika katika 9 maeneo, au ni njia ngapi tunaweza kuagiza 9 mambo.

Kuna 9 njia za kujaza B1. Kuanzia na kizuizi halali cha B1, tunaweza kupata kizuizi kingine chochote halali cha B1 kwa kuweka alama tena au kupanga upya nambari.

Kwa hivyo, dhana ya kwanza ya kurahisisha tunaweza kufanya ni kwamba B1 imejaa nambari 1, 2, 3, …, 9 ili, kama inavyoonyeshwa hapa chini.

Sasa tunaweza kuhesabu ni miisho mingapi ya gridi halisi ya B1 hii: tuiite N1. Jumla ya idadi ya gridi halisi za Sudoku ni N1×9!, kwa hivyo N1=N/9!…

Hebu fikiria njia za kujaza safu za kwanza katika B2 na B3. Tangu 1, 2 na 3 kutokea katika safu ya kwanza katika B1, nambari hizi haziwezi kutokea katika safu zingine.

Kwa hiyo, namba tu 4, 5, 6, 7, 8 na 9 kutoka safu ya pili na ya tatu ya B1 inaweza kukutana katika safu ya kwanza katika B2 na B3.

Orodhesha njia zote zinazowezekana za kujaza safu za kwanza katika B2 na B3, hadi kupanga upya nambari katika kila block. Kidokezo: Kuna njia kumi za kufanya hivyo ili kubadilishana kwa B2 na B3 njia hizi kumi kukupa njia kumi zaidi, jumla ya ishirini.

Tunaita mbili ya uwezekano huu mistari safi ya juu: wakati nambari {4,5,6}, kama katika safu ya pili ya B1, zimehifadhiwa pamoja katika B2, na nambari {7,8,9}, kama katika safu ya tatu ya B1, zimehifadhiwa pamoja katika B3, na toleo lililobadilishwa la hii.

Uwezekano mwingine ni mistari ya juu iliyochanganywa, huku wakichanganya seti {4,5,6} na {7,8,9} inapotumika kujaza mistari ya kwanza ya B2 na B3.

Kwa kuzingatia uwezekano huu ishirini kwa mstari wa kwanza wa gridi ya taifa (hadi kupanga upya nambari katika kila block), tunaweza kujua jinsi ya kujaza mstari wa kwanza.

Fikiria jinsi unavyoweza kukamilisha bendi ya kwanza kwa kuanza na safu safi ya juu 1,2,3;{4,5,6};{7,8,9}.

(Kumbuka: Tunaandika a,b,c kuashiria nambari tatu zilizoamriwa na {a,b,c} kuwaashiria kwa mpangilio wowote.)

Kuna uwezekano ngapi kwa jumla, kuhesabu mpangilio tofauti wa nambari ndani ya kila safu katika B2 na B3? Nambari hii ni sawa na ya safu nyingine safi ya juu, 1,2,3;{7,8,9};{4,5,6}?

Kumbuka, tunataka kusawazisha B1 kwa sababu tayari tumehesabu idadi ya gridi zinazoweza kupatikana kwa kuweka lebo upya tarakimu tisa ndani yake..

Inageuka wapo (3!)⁶ njia za kukamilisha bendi ya kwanza kutazama na safu safi ya juu 1,2,3;{4,5,6};{7,8,9}.

Hii ni kwa sababu tunalazimishwa kuweka {7,8,9};{1,2,3} katika safu ya pili katika B2 na B3 na {1,2,3};{4,5,6} katika safu ya tatu, na kisha tunaweza kupanga upya tarakimu tatu katika kila safu sita za B2 na B3 ili kupata usanidi wote..

Jibu ni sawa kwa safu nyingine safi ya juu, kwa kuwa katika kesi hii yote tumefanya ni kubadilishana B2 na B3.

Matukio ya safu za juu zilizochanganywa ni ngumu zaidi. Hebu fikiria safu ya juu 1,2,3;{4,6,8};{5,7,9}. Hii inaweza kukamilika kwa bendi ya kwanza kama kwenye picha ifuatayo, wapi a, b, na c ni nambari 1, 2, 3 kwa utaratibu wowote.

Baada ya kuchagua a, b na c ni nambari mbili zilizobaki kwa mpangilio wowote, kwani ziko kwenye safu moja.

Kwa kuwa kuna chaguzi tatu kwa a, na tarakimu tatu katika kila seti sita katika B2 na B3 zinaweza kurukwa ili kupata kurasa tofauti za mbele halali, jumla ya idadi ya usanidi katika kesi hii ni 3 ×(3!)6.

Vile vile unaweza kupitia kila kesi kumi na saba zilizosalia za safu ya mbele ili kupata nambari sawa.

Sasa tunayo idadi ya kurasa za mbele zinazoweza kufafanuliwa na B1: hii ni 2×(3!)6+18×3×(3!)6=2612736, ambapo sehemu ya kwanza ya jumla ni idadi ya ukamilishaji wa ukurasa wa kwanza kutoka safu mlalo za juu na ya pili ni idadi ya ukamilishaji wa ukurasa wa kwanza kutoka kwa safu mlalo zilizochanganywa za juu..

Badala ya kuhesabu ni kurasa ngapi za kurasa za mbele za kila moja ya hizi 2612736 vipengele, Felgenhauer na Jarvis waliamua ni kurasa zipi za mbele zilizo na idadi sawa ya ukamilishaji wa ukurasa wa kwanza kutoka juu tupu..

Uchambuzi huu unapunguza idadi ya kurasa za mbele zitakazozingatiwa wakati wa kukokotoa.

Hapa kuna baadhi ya shughuli ambazo huacha idadi ya miisho ya gridi ya masafa ya kwanza bila kubadilika: kuashiria nambari, kusikiliza kizuizi chochote katika safu ya kwanza, kusikiliza safu wima katika kizuizi chochote na kusikiliza safu mlalo tatu za masafa. Na yoyote ya mabadiliko haya ya B1, tunaweza kuweka alama kwenye nambari ili kurejesha umbo lake la kawaida.

Kupanga B1, B2 na B3 huweka idadi ya miisho ya gridi ya taifa, kwa sababu tukianza na gridi yoyote halisi ya Sudoku, njia pekee ya kuiweka halisi ni kuweka alama B4, B5, B6 na B7, B8, B9 kwa mtiririko huo ili safu zibaki sawa.

Kwa maneno mengine, kila usitishaji wa gridi ya ukurasa wa mbele unatoa usitishaji wa gridi ya ukurasa wa mbele kabisa, yaani. yoyote B1, B2, B3 ruhusa.
Hakikisha kuwa unapobadilisha B2 hadi B3 kwenye gridi ya Sudoko inayofuata, njia pekee ya kuweka gridi halali ni kubadilisha B5 hadi B6 na B7 hadi B8. Hii itaweka safu sawa, ingawa eneo lao limebadilika.

Ikiwa una gridi halali ya Sudoku na unaruka safu wima katika yoyote ya B1, B2 na B3, ungefanya nini na safu wima zingine za gridi ya Sudoku ili kuifanya iwe halali? Kwa mfano, ikiwa umebadilisha safu 1 na 2 ya B2 kwenye gridi ya taifa hapo juu, unawezaje kurekebisha gridi inayotokana ili kukidhi Sheria Moja?

Zoezi la mwisho linatuambia kwamba kila ujazo wa gridi ya safu ya mbele unatoa ujazo wa kipekee wa safu ya safu ya mbele na safu wima kurukwa ndani ya vizuizi..

Mawazo kama haya yanaturuhusu kupunguza idadi ya kurasa maalum za mbele zinazozingatiwa wakati wa kuhesabu.

Kufuatia Felgenhauer na Jarvis, tunasonga kupitia safu wima za B2 na B3 ili viingilio vya safu ya juu vya kila safu viwe katika mpangilio wa kupanda., na kisha ubadilishe B2 na B3 ikiwa ni lazima ili ingizo la kwanza la B2 liwe ndogo kuliko kiingilio cha B3..

Hii inaitwa ufupisho wa kileksikografia.

Kwa kuwa kila moja ya vitalu viwili ina 6 upangaji upya wa nguzo na njia mbili za kupanga upya vitalu, mkato wa kileksikografia unatuambia hivyo, ukipewa ukurasa wa kwanza, kuna kurasa 62×2=72 nyingine za mbele zenye idadi sawa ya miisho ya gridi ya taifa.

Kwa hivyo sasa tuna kurasa za mbele 2612736/72=36288 pekee za kuzingatia.

Kwa kila moja ya uwezekano huu hebu tuangalie upangaji upya wa vitalu vyote vitatu vya juu: kuna 6. Kwa kila mmoja wao kuna 63 upangaji upya wa safu wima ndani ya kila kizuizi.

Baada ya kufanya shughuli hizi, tunaweka alama tena ili kurudisha B1 katika hali yake ya kawaida.

Vile vile, tunaweza kubatilisha mistari mitatu ya juu ya kikundi na kuweka alama tena ili kurudisha B1 kwenye fomu ya kawaida. Shughuli hizi huhifadhi idadi ya ukamilishaji wa gridi ya safu mlalo ya mbele.

Felgenhauer na Jarvis walitumia programu ya kompyuta kuamua kwamba shughuli hizi hupunguza idadi ya kurasa za mbele zinazopaswa kuchukuliwa kutoka. 36288 kwa tu 416.

Hebu tuzingatie kundi hili la kwanza.

Fanya shughuli mbalimbali juu yake ambazo zinahifadhi idadi yake ya miisho ya gridi ya taifa. Unaweza kuanza na zifuatazo: Badilisha safu ya kwanza na ya pili. Weka alama tena ili B1 iwe katika hali yake ya kawaida. Punguza gridi hii kileksikografia.

Jambo kuu ni kwamba kikundi ulichoanza nacho na kikundi kingine ulichomaliza nacho kina idadi sawa ya kukamilika hadi gridi kamili ya Sudoku..

Kwa hivyo, badala ya kuhesabu idadi ya miisho ya gridi ya taifa kwa kila moja ya vikundi hivi, tunaweza tu kuhesabu kwa mmoja wao.

Kuna hatua zaidi ambazo hupunguza idadi ya gridi za kuzingatia. Ikiwa tuna jozi ya tarakimu {a,b} katika safu moja yenye a katika safu ya ith na b katika safu ya jth, na jozi sawa katika safu nyingine na b katika safu ya ith na a katika safu ya jth, kila jozi itakuwa na bendi yenye idadi sawa ya miisho ya gridi ya taifa kama ya awali.

Hii ni kwa sababu kila jozi iko kwenye safu moja, na wakati zote mbili zinabadilishwa kwa wakati mmoja, sheria moja imehifadhiwa, ambayo pia inakidhi safu zinazohusika.

Kwa mfano, angalia nambari 8 na 9 katika safu ya sita na tisa ya mfano hapo juu. Fikiria kesi zote zinazowezekana za Felgenhauer na Jarvis walioachwa nao 174 ya kwanza 416 vikundi kuendelea.

Pia wamezingatia usanidi mwingine wa seti sawa ya nambari zilizo katika safu wima au safu mbili tofauti, ambayo inaweza kuachwa ndani ya safu wima au safu, ikiacha idadi ya miisho ya gridi kuwa kigeugeu.

Hii ilipunguza idadi ya kurasa za mbele hadi 71, na utafutaji wa kila moja ya haya 71 kesi zilionyesha wazi kwao kwamba zipo tu 44 kurasa za mbele ambazo idadi ya ukamilishaji wa gridi ya taifa itapatikana.

Kila moja ya haya 44 bendi zina idadi sawa ya miisho kwa gridi kamili.

Hebu C ionyeshe mojawapo ya haya 44 kupigwa. Kisha unaweza kuhesabu idadi ya njia ambazo C inaweza kukamilisha kwa gridi kamili ya Sudoku: kuiita nc.

Tunahitaji pia idadi ya kurasa za mbele za mC zinazoshiriki nambari hii ya miisho ya nC ya gridi ya taifa. Basi, jumla ya idadi ya gridi za Sudoku ni N=ΣCmCnC tu, au jumla ya mCnC kwa wote 44 kupigwa.

Felgenhauer na Jarvis waliandika programu ya kompyuta kufanya hesabu za mwisho.

Walihesabu idadi ya ukamilishaji halali wa N1 na B1 katika fomu ya kawaida, kuanzia 44 vichochoro. Kisha wakazidisha nambari hii kwa 9! kupata jibu.

Waligundua kuwa idadi ya iwezekanavyo 9 na 9 Gridi za Sudoku ni N=6670903752021072936960, ambayo ni takriban 6.671×1021.

Kifungu Na Mikopo ya Picha:

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