Sudoku matematikasi - Mathematics of Sudoku

Sudoku jumboqlari o'rganish mumkin matematik jihatdan kabi savollarga javob berish uchun "Sudoku to'ldirilgan nechta to'r bor?", "Yaroqli jumboqdagi ko'rsatmalarning minimal soni qancha?"va "Sudoku kataklari qanday usullar bilan nosimmetrik bo'lishi mumkin?" yordamida kombinatorika va guruh nazariyasi.

Asosiy natijalar shundan iboratki, klassik Sudoku uchun to'ldirilgan katakchalar soni 6,670,903,752,021,072,936,960 (6.67×10²¹) ga kamaytiradi 5,472,730,538 mohiyatan boshqacha ostida guruhlar konvertatsiyalarni saqlovchi haqiqiyligi. Simmetriyaning 26 turi mavjud, ammo ularni faqatgina barcha to'ldirilgan katakchalarning 0,005% atrofida topish mumkin. Noyob echimga ega bo'lgan jumboq bo'lishi kerak kamida 17 ta maslahat, va har bir echilgan panjara uchun eng ko'p 21 ta ma'lumotga ega bo'lgan echiladigan jumboq mavjud. Hozirgacha topilgan eng katta minimal jumboq 40 ta maslahatga ega.

Shunga o'xshash natijalar variantlar va kichikroq tarmoqlar uchun ma'lum. Sudokus uchun klassik 9 × 9 katakchadan kattaroq aniq natijalar ma'lum emas, ammo taxminlarga ko'ra ular juda to'g'ri.

Umumiy nuqtai

Sudoku tahlili ikkita asosiy yo'nalishga bo'linadi: (1) to'ldirilgan katakchalar va (2) jumboqlarning xususiyatlarini tahlil qilish. Dastlabki tahlil asosan echimlarni sanab o'tishga qaratilgan bo'lib, natijalar birinchi marta 2004 yilda paydo bo'ldi.^[1]

Juda ko'p .. lar bor Sudoku variantlari, qisman hajmi bilan tavsiflangan (N) va ularning shakli mintaqalar. Belgilanmagan bo'lsa, ushbu maqoladagi munozarada klassik Sudoku, ya'ni. N= 9 (9 × 9 katak va 3 × 3 mintaqalar). To'rtburchakli Sudoku satr ustun o'lchamidagi to'rtburchaklar mintaqalardan foydalanadi R×C. Boshqa variantlarga notekis shakllangan mintaqalar yoki qo'shimcha cheklovlar kiritilgan (giperkub ) yoki turli xil cheklash turlari (Samunamupure ).

Mintaqalar ham chaqiriladi bloklar yoki qutilar. A guruh bu 3 qator va 3 qutini o'z ichiga olgan panjaraning bir qismidir va a suyakka bu 3 ta ustun va 3 ta qutini o'z ichiga olgan panjaraning bir qismidir. A jumboq qisman yakunlangan panjarava boshlang'ich qiymatlari berilganlar yoki maslahatlar. A to'g'ri jumboq noyob echimga ega. A minimal jumboq - bu tegishli jumboq, undan qo'shimcha echimlarni taklif qilmasdan hech qanday maslahat olib tashlanmaydi. Qarang Sudoku lug'ati boshqa terminologiya uchun.^[2]

Sudokusni o'yinchi nuqtai nazaridan hal qilish Denis Bertierning "Sudokuning yashirin mantig'i" (2007) kitobida o'rganilgan^[3] bu "yashirin xy-zanjirlar" kabi strategiyalarni ko'rib chiqadi.

Matematik kontekst

Sudoku jumboqlarini hal qilishning umumiy muammosi n²×n² panjaralari n×n bloklari ma'lum To'liq emas.^[4] Uchun n= 3 (klassik Sudoku), ammo bu natija amaliy ahamiyatga ega emas: algoritmlar kabi Raqsga havolalar jumboqlarni soniyaning kichik qismida hal qilishi mumkin, chunki masalaning kichikligi.^{[iqtibos kerak ]}

Jumboqni a shaklida ifodalash mumkin grafik rang berish muammo.^[5] Maqsad qisman 9 rang berilgan holda ma'lum bir grafikaning 9 rangini tuzishdan iborat. The Sudoku grafigi 81 ta tepalikka ega, har bir katak uchun bitta tepalik. Tepaliklar buyurtma qilingan juftliklar bilan belgilanadi (x, y), qaerda x va y 1 dan 9 gacha bo'lgan tamsayılar. Bunday holda, (x, y) va (x′, y′) Chekka bilan birlashtiriladi, agar:

• x = x′ (Xuddi shu ustun) yoki,
• y = y′ (Xuddi shu qatorda) yoki,
• ⌈ x/3 ⌉ = ⌈ x′ / 3 ⌉ va ⌈ y/3 ⌉ = ⌈ y′ / 3 ⌉ (xuddi shu 3 × 3 katak)

So'ngra jumboq har bir tepaga 1 dan 9 gacha bo'lgan butun sonni belgilash bilan yakunlanadi, shunday qilib chekka bilan birlashtirilgan tepaliklar ularga berilgan bir xil songa ega bo'lmaydi.

Sudoku eritmasi panjarasi ham Lotin maydoni.^[5] Lotin kvadratlariga qaraganda Sudoku katakchalari sezilarli darajada kam, chunki Sudoku qo'shimcha mintaqaviy cheklovlarni keltirib chiqaradi.

Sudokus guruh jadvallaridan

Ishda bo'lgani kabi Lotin kvadratlari (qo'shimcha- yoki) ko'paytirish jadvallari (Kayli stollari ) sonli guruhlardan Sudokus va tegishli raqamlar jadvallarini tuzishda foydalanish mumkin. Ya'ni, olish kerak kichik guruhlar va kvant guruhlari hisobga:

Masalan, oling ${ displaystyle mathbb {Z} _ {n} oplus mathbb {Z} _ {n}}$ har bir komponentni alohida-alohida modulga qo'shib, juftliklar guruhi ${ displaystyle n}$.Komponentlardan birini tashlab, biz to'satdan o'zimizni topamiz ${ displaystyle mathbb {Z} _ {n}}$ (va bu xaritalash, albatta, tegishli qo'shimchalar bilan mos keladi, ya'ni u a guruh homomorfizmi Bundan tashqari, bittasi a ekanligini aytadi kvant guruhi Birinchisi, chunki ba'zi birlari turli xil elementlar yangi guruhda tenglashadilar, ammo bu ham a kichik guruh, chunki biz etishmayotgan komponentni shunchaki to'ldirishimiz mumkin ${ displaystyle 0}$ orqaga qaytish ${ displaystyle mathbb {Z} _ {n} oplus mathbb {Z} _ {n}}$.

Ushbu ko'rinish ostida biz misolni yozamiz, 1-to‘r, uchun ${ displaystyle n = 3}$.

Har bir Sudoku mintaqasi ikkinchi komponentda bir xil ko'rinadi (ya'ni kichik guruhga o'xshash) ${ displaystyle mathbb {Z} _ {3}}$), chunki ular birinchisidan qat'i nazar qo'shiladi, boshqa tomondan, birinchi komponentlar har bir blokda teng bo'ladi va agar biz har bir blokni bitta katak deb tasavvur qilsak, bu birinchi komponentlar bir xil naqshni namoyish etadi (ya'ni kvant guruhi) ${ displaystyle mathbb {Z} _ {3}}$). Maqolasida ta'kidlanganidek Lotin kvadratlari, bu lotin tartibidagi kvadrat ${ displaystyle 9}$.

Endi Sudoku berish uchun har bir blok har bir blokga aynan bir marta qayta taqsimlanadigan qilib (masalan, ustunlarni) qatorlarni (yoki ularga teng ravishda) o'zgartiraylik - masalan, ularni buyurtma qilish ${ displaystyle 1,4,7,2,5,8,3,6,9}$.Bu albatta lotin kvadrat xususiyatini saqlaydi. Bundan tashqari, har bir blokda chiziqlar qurilish bo'yicha alohida birinchi komponentga ega va blokdagi har bir satr ikkinchi komponent orqali alohida yozuvlarga ega, chunki bloklarning ikkinchi komponentlari dastlab lotin tartib kvadratini tashkil qilgan ${ displaystyle 3}$ (kichik guruhdan ${ displaystyle mathbb {Z} _ {3}}$). Shunday qilib biz Sudokuga etib kelamiz (agar xohlasangiz juftlarni 1 ... 9 raqamlariga o'zgartiring). Yuqoridagi misol va qatorni almashtirish bilan biz etib kelamiz Grid 2.

1-to‘r - Qo'shish jadvali ${ displaystyle mathbb {Z} _ {3} oplus mathbb {Z} _ {3}}$ (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1)

Grid 2 - Sudoku ishlab chiqarish (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (0,0) (0,1) (0,2) (2,0) (2,1) (2,2) (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (0,1) (0,2) (0,0) (1,1) (1,2) (1,0) (2,1) (2,2) (2,0) (1,1) (1,2) (1,0) (2,1) (2,2) (2,0) (0,1) (0,2) (0,0) (2,1) (2,2) (2,0) (0,1) (0,2) (0,0) (1,1) (1,2) (1,0) (0,2) (0,0) (0,1) (1,2) (1,0) (1,1) (2,2) (2,0) (2,1) (1,2) (1,0) (1,1) (2,2) (2,0) (2,1) (0,2) (0,0) (0,1) (2,2) (2,0) (2,1) (0,2) (0,0) (0,1) (1,2) (1,0) (1,1)

Ushbu usulning ishlashi uchun umuman olganda ikkita teng o'lchovli guruh mahsuloti kerak emas. Qisqa deb nomlangan aniq ketma-ketlik tegishli hajmdagi sonli guruh allaqachon ishni bajaradi. Masalan, guruhni sinab ko'ring ${ displaystyle mathbb {Z} _ {4}}$ va kichik guruh bilan ${ displaystyle mathbb {Z} _ {2}}$.Sudokuslarning hammasi ham shu tarzda ishlab chiqarilmasligi aniq (allaqachon ro'yxatga olish dalillaridan) ko'rinadi.

Variantlar

Sudokuni a deb talqin qilish mumkin plitka (yoki qopqoq ) ning Lotin maydoni bilan poliominolar (the mintaqalar Sudoku). Klassik 9 × 9 Sudoku to'rtburchakdan yasalgan nonominolar. Sudoku qoidalarini boshqa o'lchamdagi boshqotirmalarda qo'llash mumkin, garchi faqat N²×N² Sudoku jumboqlarini to'rtburchaklarli poliominolar bilan qoplash mumkin.

Ga qarang Sudoku lug'ati variantlarning kengaytirilgan ro'yxati uchun.

To'rtburchaklar mintaqalar

Ommabop variant to'rtburchaklar mintaqalardan yasalgan (bloklar yoki qutilar) - masalan, 2 × 3 geksominolar 6 × 6 katakchada plitka bilan qoplangan. Ushbu variantni muhokama qilish uchun quyidagi yozuvlardan foydalaniladi:

• R×C bilan to'rtburchaklar mintaqani bildiradi R qatorlar va C ustunlar.
• Ko'zda tutilgan panjara konfiguratsiyasi quyidagilarga ega:
  • panjara o'lchamlari N×N, qayerda N = R×C
  • N bloklar (qutilar) hajmi R×C, a C×R "super tarmoq"
  • C guruhlar hajmi R×Niborat R gorizontal ravishda ulashgan bloklar
  • R vayronalar hajmi N×Ciborat C vertikal ravishda ulashgan bloklar

Kvadrat bilan sudoku N×N mintaqalar to'rtburchaklar Sudokuga qaraganda nosimmetrikdir, chunki har bir satr va ustun kesishgan N mintaqalar va aktsiyalar N har birida hujayralar. Bantlar va to'plamlar soni ham teng N. "3 × 3" Sudoku qo'shimcha ravishda noyobdir: N qatoridan ustun qatoriga cheklovlar soni ham Bitta qoida (ya'ni mavjud N= 3 turi birliklar).

Jigsaw sudokus

Mintaqalari (shart) kvadrat yoki to'rtburchaklar bo'lmagan Sudoku Jigsaw Sudoku deb nomlanadi. Xususan, an N×N kvadrat qaerda N astar faqat tartibsiz plitka bilan qoplanishi mumkin N-ominolar. Ning kichik qiymatlari uchun N kvadratga plitka qo'yish usullari soni (nosimmetrikliklar bundan mustasno) hisoblangan (ketma-ketlik) A172477 ichida OEIS ).^[6] Uchun N ≥ 4 ushbu plitalarning ba'zilari hech qanday lotin kvadratiga mos kelmaydi; ya'ni bunday plitka ustidagi barcha Sudoku jumboqlarida echim yo'q.^[6]

Yechimlar

"Sudoku tarmog'i qancha?" Degan savolga javob. o'xshash echimlar qachon boshqacha ko'rib chiqilishini aniqlashga bog'liq.

Oddiy Sudoku

Barcha echimlar

Sanab o'tish uchun barchasi mumkin bo'lgan echimlar, ularning har qanday mos keladigan (81) hujayra qiymatlari farq qiladigan bo'lsa, ikkita echim alohida hisoblanadi. Shunga o'xshash echimlar orasidagi simmetriya munosabatlari e'tiborga olinmaydi., Masalan. eritmaning aylanishi alohida hisoblanadi. Nosimmetrikliklar hisoblash strategiyasida muhim rol o'ynaydi, ammo hisoblashda emas barchasi mumkin bo'lgan echimlar.

Sanab chiqishni yakunlash bo'yicha birinchi ma'lum echim QSCGZ (Guenter Stertenbrink) tomonidan joylashtirilgan jumboq yangiliklar guruhi 2003 yilda,^[7][8][9] olish 6,670,903,752,021,072,936,960 (6.67×10²¹) aniq echimlar.

2005 yilda o'tkazilgan tadqiqotda Felgenxauer va Jarvis^[10][9] tahlil qildi almashtirishlar tegishli echimlarda ishlatiladigan yuqori tarmoqli. Bir marta Band1 simmetriya va ekvivalentlik darslari qisman panjara echimlari aniqlandi, pastki ikkita polosaning komplektlari qurildi va har bir ekvivalentlik sinfi uchun hisoblandi. Ekvivalentlik sinflari bo'yicha yakunlarni yakunlash, sinf kattaligi bo'yicha, echimlarning umumiy sonini 6,670,903,752,021,072,936,960 qilib, QSCGZ tomonidan olingan qiymatni tasdiqlaydi. Keyinchalik bu qiymat mustaqil ravishda bir necha bor tasdiqlangan. Keyinchalik tarmoqli ishlab chiqarishga asoslangan ikkinchi hisoblash texnikasi ishlab chiqilgan bo'lib, u hisob-kitob qilish jihatidan ancha kam intensiv bo'lib, keyinchalik ushbu uslub dastlabki tsikllar singari hisoblash tsikllari sonining 1/97 qismiga ehtiyoj sezdi, ammo uni o'rnatish ancha murakkablashdi.

Aslida turli xil echimlar

O'zgarishlarni saqlaydigan amal qilish muddati

Ikkita to'g'ri panjara mohiyatan xuddi shunday deb nomlangan narsa yordamida boshqasidan olinishi mumkin Transformatsiyani saqlaydigan haqiqiylik (VPT). Ushbu transformatsiyalar har doim yaroqli katakchani boshqa joriy tarmoqqa aylantiradi. Ikkita asosiy turi mavjud: belgini almashtirish (qayta nomlash) va hujayralarni almashtirish (qayta o'zgartirish). Ular:

• Belgilarni qayta tiklash (9!)
  (Barcha mumkin bo'lgan qayta nomlash kombinatsiyalari bekor qilingandan so'ng, faqat bittasi bundan mustasno: masalan, yuqori qatorni [123456789] darajasida ushlab turish, sobit katakchalar soni 18,383,222,420,692,992 gacha kamayadi. Bu qiymat 9 ga bo'linib 6,670,903,752,021,072,936,960 ga teng!)
  

va qayta tashkil etish (aralashtirish):

• Tarmoqli almashtirishlar (3!)
• Tarmoq ichidagi qatorlarni almashtirish (3! × 3! × 3!)
• Stack permutations (3!)
• Stek ichidagi ustunlarni almashtirish (3! × 3! × 3!)
• Ko'zgu, transpozitsiya va aylanish (2)
  (Yuqoridagi permutatsiyalar bilan birgalikda bitta transpozitsiya yoki to'rtdan bir burilishni hisobga olgan holda, aks ettirish, transpozitsiya va aylanishlarning har qanday kombinatsiyasi hosil bo'lishi mumkin, shuning uchun bu operatsiyalar faqat 2 faktorga yordam beradi)

Ushbu operatsiyalar ekvivalent panjaralar o'rtasidagi munosabatni belgilaydi. 81 katak katak qiymatiga kelsak, qayta tashkil etish operatsiyalari a ni tashkil qiladi kichik guruh ning nosimmetrik guruh S₈₁, 3-buyurtma!⁸× 2 = 3,359,232. Qayta nomlash operatsiyalari izomorfik S bilan₉ va qo'shimcha 9 hosil qiling! = 362,880 ga teng bo'lgan panjara. Ushbu operatsiyalarni katakchada qo'llash natijaga olib keladi!⁸× 2 × 9! yoki 1 218,998,108,160 asosan teng keladigan panjaralar. Ammo sudokuslarning oz miqdori mavjud bo'lib, ular uchun yuqoridagi operatsiyalar kamroq panjara hosil qiladi; bu o'zlariga o'xshash yoki avtomorf sudokus. Barcha noyob tarmoqlarning atigi 0,01% faqat avtomorfikdir^[11], lekin ularni hisoblash aslida har xil sudokuslarning aniq sonini baholash uchun zarurdir.

Sudoku simmetriya guruhi

Sudoku simmetriyasining aniq tuzilishi guruh yordamida qisqacha ifodalanishi mumkin gulchambar mahsuloti (≀). Mumkin bo'lgan qator (yoki ustun) almashtirishlar guruhni tashkil qiladi izomorfik ga S₃ ≀ S₃ 3-buyurtma!⁴ = 1,296^[12]. Barcha qayta tashkil etish guruhi transpozitsiya operatsiyasini bajarishga imkon beradi (izomorfik C₂) ushbu guruhning ikkita nusxasida harakat qiling, bittasi qatorni almashtirish uchun va ikkinchisi ustunni almashtirish uchun. Bu S₃ ≀ S₃ ≀ C₂, buyurtma guruhi 1,296² × 2 = 3,359,232. Va nihoyat, qayta yozish operatsiyalari qayta tiklash operatsiyalari bilan almashtiriladi, shuning uchun to'liq soduku (VPT) guruhi (S₃ ≀ S₃ ≀ C₂) × S₉ buyurtma 1,218,998,108,160.

Ruxsat etilgan nuqtalar va Burnsayd lemmasi

Ushbu operatsiyalar yordamida erishish mumkin bo'lgan teng tarmoqlar to'plami (qayta nomlashni hisobga olmaganda) orbitada qayta qurish harakati ostida panjara guruh. Keyinchalik bir-biridan farq qiladigan echimlar soni orbitalar soni bo'lib, ular yordamida hisoblash mumkin Burnside lemmasi. Burnside sobit nuqtalar qayta tashkil etish jarayonida o'zgarmas yoki faqat qayta nomlash bilan farq qiladigan kataklardir. Hisoblashni soddalashtirish uchun qayta tuzish guruhining elementlari saralanadi konjugatsiya darslari, ularning elementlari bir xil sobit nuqtalarga ega. Ma'lum bo'lishicha, qayta tashkil etish guruhining 275 konjugatsiya sinfidan atigi 27 tasida aniq nuqtalar mavjud^[13]; ushbu konjugatsiya sinflari tugallangan sudoku katakchalarida bo'lishi mumkin bo'lgan har xil simmetriya turlarini (o'ziga o'xshashlik yoki avtomorfizm) ifodalaydi. Ushbu texnikadan foydalanib, Ed Rassel va Frazer Jarvis birinchi bo'lib sudoku echimlarining sonini hisoblab chiqdilar. 5,472,730,538^[13][14].

Qayta qurish guruhining konjugatsiya sinflari sobit nuqtalari bilan ("avtomorfizmlar" va ularning tarqalishi)^[13]

Nomi yoki tarkibi[15]	Kod	Sinf Id.[13]	Sinf hajmi[13]	Hujayra davrlari	O [15]	F [15]	Ruxsat etilgan katakchalar soni (qayta nomlashgacha), har bir element uchun[13]	Ruxsat etilgan katakchalar soni, har bir element uchun	Ruxsat etilgan katakchalar soni (qayta nomlashgacha), butun sinf	Ruxsat etilgan katakchalar soni, butun sinf
Shaxsiyat	e	1	1		1	81	18,383,222,420,692,992	6,670,903,752,021,072,936,960	18,383,222,420,692,992	6,670,903,752,021,072,936,960
Mini qatorlar (MR)	ccc	8	16	27×3	3	0	107,495,424	39,007,939,461,120	1,719,926,784	624,127,031,377,920
2 MR, 1 tibbiyot	ccc | v	7	96	27×3	3	0	21,233,664	7,705,271,992,320	2,038,431,744	739,706,111,262,720
1 MR, 2 tibbiyot	ccc | cc	9	192	27×3	3	0	4,204,224	1,525,628,805,120	807,211,008	292,920,730,583,040
Mini diagonallar (MD)	ccc | ccc	10	64	27×3	3	0	2,508,084	910,133,521,920	160,517,376	58,248,545,402,880
Satrlarga sakrash (JR)	C	25	144	27×3	3	0	14,837,760	5,384,326,348,800	2,136,637,440	775,342,994,227,200
2 JR, 1 GR	C | v	28	864	27×3	3	0	2,085,120	756,648,345,600	1,801,543,680	653,744,170,598,400
1 JR, 2 GR	C | cc	30	1,728	27×3	3	0	294,912	107,017,666,560	509,607,936	184,926,527,815,680
Qatlamli qatorlar (GR)	C | ccc	32	1,152	27×3	3	0	6,342,480	2,301,559,142,400	7,306,536,960	2,651,396,132,044,800
To'liq qatorlar (FR)	C9	27	288	9×9	9	0	5,184	1,881,169,920	1,492,992	541,776,936,960
2 FR, 1 WR	C9 | v	26	1,728	9×9	9	0	2,592	940,584,960	4,478,976	1,625,330,810,880
1 FR, 2 WR	C9 | cc	29	3,456	9×9	9	0	1,296	470,292,480	4,478,976	1,625,330,810,880
To'lqinli qatorlar (WR)	C9 | ccc	31	2,304	9×9	9	0	648	235,146,240	1,492,992	541,776,936,960
Sakrash diagonallari (JD)	C | C	22	5,184	27×3	3	0	323,928	117,546,992,640	1,679,242,752	609,363,609,845,760
Singan ustunlar (miloddan avvalgi)	C | C9	24	20,736	9×9	9	0	288	104,509,440	5,971,968	2,167,107,747,840
To'liq diagonallar (FD)	C9 | C9	23	20,736	9×9	9	0	162	58,786,560	3,359,232	1,218,998,108,160
Diagonal Mirror (DM)	T	37	1,296	36×2	2	9	30,258,432	10,980,179,804,160	39,214,927,872	14,230,313,026,191,360
DM + MD	T ccc	40	10,368	3×3, 12×6	6	0	1,854	672,779,520	19,222,272	6,975,378,063,360
DM + JD	T C	43	93,312	3×3, 12×6	6	0	288	104,509,440	26,873,856	9,751,984,865,280
Chorak burilish (QT)	T sS	86	69,984	20×4	4	1	13,056	4,737,761,280	913,711,104	331,567,485,419,520
Yarim burilish (HT)	sS | sS	79	2,916	40×2	2	1	155,492,352	56,425,064,693,760	453,415,698,432	164,535,488,647,004,160
Ustun tayoqchalar (CS)	S | sss	134	972	36×2	2	9	449,445,888	163,094,923,837,440	436,861,403,136	158,528,265,969,991,680
CS + MC	cS6 | sss	135	3,888	3×3, 12×6	6	0	27,648	10,032,906,240	107,495,424	39,007,939,461,120
CS + GR	cS6 | C6	142	31,104	3×3, 12×6	6	0	6,480	2,351,462,400	201,553,920	73,139,886,489,600
CS + JR / B2, GR / B13	S6 | C6	143	15,552	3×3, 12×6	6	0	1,728	627,056,640	26,873,856	9,751,984,865,280
CS + GR / Band2, JR / B13	cS | C6	144	15,552	3×3, 12×6	6	0	3,456	1,254,113,280	53,747,712	19,503,969,730,560
CS + JR	S | C6	145	7,776	3×3, 12×6	6	0	13,824	5,016,453,120	107,495,424	39,007,939,461,120
(ahamiyatsiz)									949,129,933,824	344,420,270,386,053,120
jami									18,384,171,550,626,816	6,671,248,172,291,458,990,080

E'tibor bering, panjara bir vaqtning o'zida bir nechta o'zgarishlarning sobit nuqtasi bo'lishi mumkin; Masalan, chorak burilish simmetriyasiga ega bo'lgan har qanday panjara ham yarim burilish simmetriyasiga ega. Muayyan panjarani o'rnatadigan barcha o'zgarishlarning kombinatsiyasi bu stabilizator kichik guruhi ("avtomorfizm guruhi").

Stabilizator kichik guruhlari

Rassel ahamiyatsiz bo'lmagan 122 ta "mohiyatan boshqacha" ro'yxatni tuzdi stabilizator kichik guruhi konjugatsiya sinflari ("avtomorfizm guruhlari"),^[16][17] misol panjarasi bilan bir qatorda guruhdagi VPT konjugatsiya sinflari, generatorlar to'plami va ushbu stabilizator sinfiga ega bo'lgan bir-biridan deyarli har xil kataklar (orbitalar) soni. Izomorfizmgacha 26 xil guruh tuzilishi mavjud.^[18] Keyingi bobda keltirilgan 15 xil stabilizator guruhining o'lchamlari mavjud.

Asosan teng keladigan katakchalar soni

Aslida noyob tarmoqlarning har birini tahlil qilish mumkin^[11] o'zaro o'xshashlik ("avtomorfizmlar") uchun aslida teng keladigan panjara sonidagi "etishmovchilik" ni baholash. Natijalar quyidagi jadvalda umumlashtiriladi. Umuman olganda 5 472 730 538 ta panjaradan 560 151 tasi (taxminan 0,01%) o'ziga o'xshashlik shakliga ega (ahamiyatsiz bo'lmagan stabilizator).

Orbitaning o'lchamini (ya'ni, aslida teng keladigan katakchalar sonini) yordamida hisoblash mumkin orbita-stabilizator teoremasi: bu sudoku simmetriya guruhining kattaligi stabilizator (yoki "avtomorfizm") guruhining kattaligiga bo'linadi. Aslida noyob panjaralar sonini (orbitalar sonini) orbitaning kattaligi bilan ko'paytirish ushbu stabilizator guruhining o'lchamiga ega bo'lgan kataklarning umumiy sonini beradi; yig'indisi yana bir bor mumkin bo'lgan sudoku katakchalarini taqdim etadi. "Automorphic" katakchalari kichikroq orbitaga ega, shuning uchun tasodifiy panjara simmetriyasiga ega bo'lish ehtimoli pasayadi: mohiyatan har xil panjaralar uchun 10000 dan taxminan 1000 dan barcha tarmoqlar uchun taxminan 20000 dan 1 gacha.

Stabilizator guruhi kattaligi bo'yicha sudoku katakchalari soni^[11]

Hajmi stabilizator guruh	Yo'q, aslida noyob tarmoqlar (orbitalar soni)	Ekvivalent panjaralar (orbitaning kattaligi), qayta nomlashni e'tiborsiz qoldirish	Panjara soni, qayta nomlashni e'tiborsiz qoldirish	Ekvivalent panjaralar (orbitaning kattaligi), shu jumladan qayta nomlash	Tarmoqlarning umumiy soni
1	5,472,170,387	3,359,232	18,382,289,873,462,784	1,218,998,108,160	6,670,565,349,282,175,057,920
2	548,449	1,679,616	921,183,715,584	609,499,054,080	334,279,146,711,121,920
3	7,336	1,119,744	8,214,441,984	406,332,702,720	2,980,856,707,153,920
4	2,826	839,808	2,373,297,408	304,749,527,040	861,222,163,415,040
6	1,257	559,872	703,759,104	203,166,351,360	255,380,103,659,520
8	29	419,904	12,177,216	152,374,763,520	4,418,868,142,080
9	42	373,248	15,676,416	135,444,234,240	5,688,657,838,080
12	92	279,936	25,754,112	101,583,175,680	9,345,652,162,560
18	85	186,624	15,863,040	67,722,117,120	5,756,379,955,200
27	2	124,416	248,832	45,148,078,080	90,296,156,160
36	15	93,312	1,399,680	33,861,058,560	507,915,878,400
54	11	62,208	684,288	22,574,039,040	248,314,429,440
72	2	46,656	93,312	16,930,529,280	33,861,058,560
108	3	31,104	93,312	11,287,019,520	33,861,058,560
162	1	20,736	20,736	7,524,679,680	7,524,679,680
648	1	5,184	5,184	1,881,169,920	1,881,169,920
>1	560,151		932,547,230,208		338,402,738,897,879,040
	5,472,730,538		18,383,222,420,692,992		6,670,903,752,021,072,936,960

Boshqa variantlar

Sudoku-ning ko'plab variantlari bo'yicha sanoq natijalari hisoblab chiqilgan: ular quyida keltirilgan.

Sudoku qo'shimcha cheklovlar bilan

Quyida klassik 3 × 3 Sudoku (9 × 9 panjara) ning barcha cheklovlari keltirilgan. Turlarning nomlari standartlashtirilmagan: ta'riflarni ko'rish uchun atributlar havolasini bosing. Oddiy Soduku taqqoslash uchun oxirgi qatorga kiritilgan.

Turi	Panjara soni	Atribut	Tasdiqlanganmi?
Kvasi-sehrli Sudoku	248,832	Jons, Perkins va Roach[19]	Ha[iqtibos kerak ]
Sehrli Sudoku	5,971,968	Stertenbrink[20]	Ha[iqtibos kerak ]
Hypercube	37,739,520	Stertenbrink[21]	Ha[iqtibos kerak ]
3doku	104,015,259,648	Stertenbrink[22]	Ha[iqtibos kerak ]
NRC Sudoku	6,337,174,388,428,800	Brouwer[23]	Ha[iqtibos kerak ]
Sudoku X	55,613,393,399,531,520	Rassel[24]	Ha[iqtibos kerak ]
Guruhlarni ajratish	201,105,135,151,764,480	Rassel[25]	Ha[iqtibos kerak ]

To'rtburchaklar mintaqalar bilan Sudoku

Jadvalda blok o'lchamlari mintaqalarning o'lchamlari (masalan, oddiy Sudokuda 3 × 3). "Rel Err" ustuni oddiy taxminiylikni qanday ko'rsatib beradi^[26] hisoblangan tasmalar soni asosida (quyida keltirilgan bo'limlarda batafsil) tarmoqning haqiqiy soni bilan taqqoslanadi: bu hozirgacha baholangan barcha holatlarda bu juda kam. Kvadrat blokli panjaralar uchun raqamlar (n² × n²) (ketma-ketlikda) berilgan A107739 ichida OEIS ) va 2 × uchun raqamlar n bloklar (2n × 2n kataklar) (ketma-ketlikda) berilgan A291187 ichida OEIS ).

O'xshash Lotin kvadratlari, sudoku katakchalari soni bo'lishi mumkin kamaytirilgan qisman standartlashtirilgan shaklga ega bo'lgan birma-bir yozishmalar mavjudligini ta'kidlab, unda birinchi blokda kanonik yorliqlar mavjud bo'lib, ikkala yuqori satr va chap tomondagi ustunlar tartiblangan (qoidalar imkon qadar, ya'ni bloklar ichida va to'plamlar / bantlarning o'zlari). Bilan panjara uchun ${ displaystyle R times C}$ bloklari, har bir bunday kamaytirilgan panjara mos keladi

umumiy tarmoqlar,^[27][28] bu 9! × 72² yoki oddiy 3 × 3 Sudoku uchun 1,881,169,920. Ushbu pasayish har doim birma-bir bo'lib, quyida ko'rib chiqilgan o'zgarishlarni ('Sudoku simmetriyalari') saqlaydigan butun kuchlilik harakatlaridan farq qiladi.

O'lchamlari		To'liq katakchalar soni				Est. xato (pastga qarang)	Qismi Lotin kvadratlari
Tarmoq	Bloklar	To'liq	Kattalik	Atribut	Tasdiqlanganmi?
4×4	2×2	288	2.8800×102	turli xil[29]	Ha	−11.1%	0.5×100
6×6	2×3	28,200,960	2.8201×107	Pettersen[30]	Ha[31]	−5.88%	3.5×10−2
8×8	2×4	29,136,487,207,403,520	2.9136×1016	Rassel[31]	Ha[32]	−1.91%	2.7×10−4
9×9	3×3	6,670,903,752,021,072,936,960	6.6709×1021	Stertenbrink[7]	Ha[9]	−0.207%	1.2×10−6
10×10	2×5	1,903,816,047,972,624,930,994,913,280,000	1.9038×1030	Pettersen[33]	Ha[34]	−0.375%	1.9×10−7
12×12	3×4	81,171,437,193,104,932,746,936,103,027,318,645,818,654,720,000	8.1171×1046	Pettersen / kumush[35]	Yo'q	−0.132%[35]	noma'lum
12×12	2×6	38,296,278,920,738,107,863,746,324,732,012,492,486,187,417,600,000	3.8296×1049	Pettersen[36]	Yo'q	−0.238%[36]	noma'lum
15×15	3×5	noma'lum	est.3.5086×1084	Kumush[37]	Yo'q	n / a	noma'lum
16×16	4×4	noma'lum	est.5.9584×1098	Kumush[38]	Yo'q	n / a	noma'lum
20×20	4×5	noma'lum	est.3.1764×10175	Kumush[39]	Yo'q	n / a	noma'lum
25×25	5×5	noma'lum	est.4.3648×10308	Kumush / Pettersen[40]	Yo'q	n / a	noma'lum

Hal qilingan Sudoku amallari bo'yicha amal qiladi konvertatsiyalarni saqlovchi haqiqiyligi (yana qarang Jarvis^[13]). Har bir transformatsiya uchun o'zgarmas katakchalar sonini sinchkovlik bilan hisoblash orqali, aslida Sudoku panjaralarining turlicha sonini hisoblash mumkin (yuqoriga qarang). Shu kabi usullar boshqa o'lchamdagi sudoku katakchalarida ham qo'llanilgan; natijalar quyidagi jadvalda umumlashtiriladi. Kvadrat blokli panjaralar uchun (ketma-ketlik) A109741 ichida OEIS ) transpozitsiya transformatsiyasi VPT (simmetriya) guruhiga kiritilishi yoki kiritilmasligi (quyida kursiv bilan). Asosan turli xil katakchalar sonini, asosan avtomorfik sudokuslar sonini ahamiyatsiz deb hisoblaydigan VPT guruhi (osonlik bilan hisoblab chiqiladigan) miqdoriga bo'lish orqali (ma'lum yoki taxmin qilingan) umumiy tarmoqlarni hisoblash mumkin. 2 × raqamlar n bloklar (2n × 2n katakchalar) (ketma-ketlikda) berilgan A291188 ichida OEIS ).

O'lchamlari		Aslida har xil panjaralar soni	VPT guruhining hajmi	Birlashma soni. sinflar (qayta nomlashsiz)	Malumot
Tarmoq	Bloklar
4×4	2×2	2	128 × 4!		[41][42]
4×4	2×2	3	64 × 4!		[41]
6×6	2×3	49	3,456 × 6!	90	Jarvis / Rassel[43], Pettersen[41]
8×8	2×4	1,673,187	4,423,368 × 8!	400	Rassel[44] , Pettersen[41]
9×9	3×3	5,472,730,538	3,359,232 × 9!	275	Jarvis / Rassel[13], Pettersen[45][41]
9×9	3×3	10,945,437,157	1,679,616 × 9!	484	Jarvis / Rassel[13], Pettersen[45][41]
10×10	2×5	4,743,933,602,050,718	110,592,000 × 10!	1260	Pettersen / Rassel[46][47]
16×16	4×4	est. 2.2458×1071	(4!)10 × 2 × 16!		(taxmin matnda tushuntirilgan)[48]

Baholash usuli

Kevin Kilfoilning usuli^[49] (Pettersen tomonidan umumlashtirilgan^[26]) tugallangan katakchalar sonini taxminiy tugallangan polosalar va stakalar sonidan foydalangan holda taxmin qilish uchun ishlatilishi mumkin. Usul Sudoku satrlari va ustunlar cheklovlari, birinchi yaqinlashishga, shartli ravishda mustaqil qutidagi cheklov berilgan. Bu beradi Kilfoil-Kumush-Pettersen formulasi:^[26]

${ displaystyle { mbox {R × C katakchali RC × RC katakchalari soni}} simeq { frac {(b_ {R, C}) ^ {C} times (b_ {C, R}) ^ { R}} {(RC)! ^ {RC}}}}$

qayerda ${ displaystyle b_ {R, C}}$ to'ldirish usullarining soni a R×RC guruhi R gorizontal ravishda qo'shni R×C qutilar (teng ravishda, ${ displaystyle b_ {C, R}}$ to'ldirish usullarining soni a RC×C to'plami C vertikal ravishda qo'shni R×C qutilar) va maxraj (RC)!^RC - bu faqat qutidagi ziddiyatlarni qondirishda panjarani to'ldirish usullarining soni.

Pettersen tushuntirganidek: «Mana shunday: Qo'y X makon bo'lishi ${ displaystyle (nm) times (nm)}$- sudoku qonuniy lentalari tomonidan qurilgan, ammo ustunlar Sudoku qoidalariga rioya qilish-qilinmasligiga e'tibor bermasdan. Hajmi X bu ${ displaystyle b (n, m) ^ {m}}$. Shuningdek, ruxsat bering Y qatorlarga e'tibor bermasdan, qonuniy stacklar tomonidan qurilgan panjaralar to'plami bo'ling, #Y keyin ${ displaystyle b (m, n) ^ {n}}$. Nxm-sudoku katakchalari keyinning kesishmasidir X va Y. Tasodifiy ${ displaystyle x ( in X)}$ va ${ displaystyle y ( in Y)}$ ehtimollik bilan berilgan qutida bir xil ${ displaystyle (nm)!}$va ushbu ehtimolliklar har bir quti uchun mustaqil ekanligi taxminiga binoan biz yuqoridagi taxminlarga erishamiz. "^[26]

Ushbu taxmin klassik 9 × 9 katakchasi uchun taxminan 0,2% gacha, aniq qiymatlari ma'lum bo'lgan kattaroq katakchalar uchun esa 1% atrofida ekanligini tasdiqladi (yuqoridagi jadvalga qarang).

Bantlar soni

Mumkin bo'lgan polosalar soni uchun aniq formulalar ${ displaystyle b_ {R, C}}$ to'ldirilgan sudoku katakchasida o'lchamlari bloklari bilan R×C ma'lum:

O'lchamlari		Bantlar soni	Atribut	Tasdiqlanganmi?
Band	Bloklar
2×2C	2×C	${ displaystyle b_ {2, C} = (2C)! (C!) ^ {2}}$	(aniq natija)	Ha[iqtibos kerak ]
3×3C	3×C	${ displaystyle b_ {3, C} = (3C)! (C!) ^ {6} sum _ {k = 0} ^ {C} {C select k} ^ {3}}$ bu erda yig'indisi sifatida tanilgan Cth Franel raqami (ketma-ketlik A000172 ichida OEIS )	Pettersen[30]	Ha[iqtibos kerak ]
4×4C	4×C	${ displaystyle b_ {4, C} = (4C)! (C!) ^ {12} sum _ {a, b, c} { left ({ frac {C! ^ {2}} {a! b! c!}} cdot sum _ {k_ {12}, k_ {13}, k_ {14}, atop k_ {23}, k_ {24}, k_ {34}} {{a select k_ {12}} {b ni tanlang k_ {13}} {c ni tanlang k_ {14}} {c ni tanlang k_ {23}} {b ni tanlang k_ {24}} {a ni tanlang k_ {34}}} o'ng) ^ {2}}}$ qaerda: tashqi chaqiriq hamma narsadan olinadi a,b,v shunday qilib 0≤a,b,v va a+b+v=2C. ichki chaqiriq hamma narsadan olinadi k12,k13,k14,k23,k24,k34 ≥ 0 shunday k12,k34 ≤ a va k13,k24 ≤ b va k14,k23 ≤ v va k12+k13+k14 = a−k12+k23+k24 = b−k13+v−k23+k34 = v−k14+b−k24+a−k34 = C Tashqi summa tasmaning ikkitadan 2 qutidan iborat ikkita "subbands" ga bo'linishiga mos keladi; raqamlar a, b va v bo'linishni tavsiflang va ikkala pastki polosaga mos kelishi kerak, shuning uchun summand kvadratga o'tkazilishi mumkin. Split o'zgaruvchilar quyidagicha tavsiflanadi: "a birinchi kataklardagi 1 va 2-qatordagi belgilar soni (ya'ni 1-satrda 1-satrda va 2-satrda 2-satrda YOKI 2-satrda 1-satrda va 2-satrda 1-satrda joylashgan belgilar). Bundan tashqari, bu birinchi ikkita qutidagi 3 va 4 qatorlaridagi belgilar soni, shuningdek oxirgi ikkita qutidagi 1 va 2 qatorlaridagi belgilar soni va 3 va 4 qatorlaridagi belgilar soni birinchi ikkita quti. b - bu birinchi ikkita qutidagi 1 va 3 qatorlaridagi belgilar soni, o'zgaruvchiga nisbatan boshqa kombinatsiyalar bilan birga a. v bu birinchi ikki qutidagi 1 va 4 qatorlaridagi belgilar soni. "[50] Ichki yig'indida berilgan uchun pastki bandlar soni sanab chiqiladi a,b,v spetsifikatsiyasi: "Ular orasida a 1 va 2-qatorda 1 va 2 qatorlarda joylashgan belgilar, k12 1-satrda 1-qatorda (va shu tariqa 2-satrda 2-qatorda) qancha turishini sanaydi. Umuman olganda, uchun men<jqatorda joylashgan belgilar orasida men va j birinchi ikkita qutida, kij ularning qanchasi qatorda ekanligini aytadi men 1-qator va qatorda j 2-qutiga. "[50]	Pettersen[51]	Ha[52]

Bir nechta ma'lum guruhlar soni quyida keltirilgan. Petersen algoritmi,^[53] Silver tomonidan amalga oshirilgan va takomillashtirilgan,^[54] guruhni pastki polosalarga ajratadi, keyinchalik ular ekvivalentlik sinflariga birlashtiriladi; hozirda ularni aniq baholash uchun eng tez ma'lum bo'lgan texnikadir b_{R, C}.

O'lchamlari		Bantlar soni	Atribut	Tasdiqlanganmi?
Band	Bloklar
3×6	3×2	6! × 2!6 × 10 = 460800	Pettersen (formula)
3×9	3×3	9! × 3!6 × 56 = 9! × 2612736 = 948109639680 ≈ 9.4811×1011 (44 ekvivalentlik sinflari)[10][55])	Turli xil[10][30]
3×12	3×4	12! × 4!6 × 346 = 31672366418991513600 ≈ 3.1672×1019	Stertenbrink[iqtibos kerak ]	Ha[50]
3×15	3×5	15! × 5!6 × 2252 ≈ 8.7934×1027	Pettersen (formula)[37]
(kattaroq 3 × C qiymatlarni yuqorida keltirilgan formuladan foydalanib osongina hisoblash mumkin)
4×8	4×2	8! × 2!12 × 5016 = 828396011520 ≈ 8.2840×1011	[iqtibos kerak ]
4×12	4×3	12! × 3!12 × 2180544 = 2273614462643364849254400 ≈ 2.2736×1024	Pettersen[30]	Ha[50]
4×16	4×4	16! × 4!12 × 1273431960 ≈ 9.7304×1038	Kumush[38][56]	Ha[iqtibos kerak ]
4×20	4×5	20! × 5!12 × 879491145024 ≈ 1.9078×1055	Rassel[56]	Ha[iqtibos kerak ]
4×24	4×6	24! × 6!12 × 677542845061056 ≈ 8.1589×1072	Rassel[56]	Ha[iqtibos kerak ]
4×28	4×7	28! × 7!12 × 563690747238465024 ≈ 4.6169×1091	Rassel[56]	Ha[iqtibos kerak ]
(4 × 100 gacha bo'lgan hisob-kitoblarni Kumush amalga oshirgan,[57] lekin bu erda yozilmagan)
5×10	5×2	10! × 2!20 × 364867776 ≈ 1.3883×1021 (355 ekvivalentlik sinflari)[33])	[iqtibos kerak ]	Yo'q
5×15	5×3	15! × 3!20 × 324408987992064 ≈ 1.5510×1042	Kumush[39]	Habir xil muallif, boshqa usul
5×20	5×4	20! × 4!20 × 518910423730214314176 ≈ 5.0751×1066	Kumush[39]	Habir xil muallif, boshqa usul
5×25	5×5	25! × 5!20 × 1165037550432885119709241344 ≈ 6.9280×1093	Pettersen / kumush[40]	Yo'q
5×30	5×6	30! × 6!20 × 3261734691836217181002772823310336 ≈ 1.2127×10123	Pettersen / kumush[40]	Yo'q
5×35	5×7	35! × 7!20 × 10664509989209199533282539525535793414144 ≈ 1.2325×10154	Pettersen / kumush[58]	Yo'q
5×40	5×8	40! × 8!20 × 39119312409010825966116046645368393936122855616 ≈ 4.1157×10186	Pettersen / kumush[54]	Yo'q
5×45	5×9	45! × 9!20 × 156805448016006165940259131378329076911634037242834944 ≈ 2.9406×10220	Pettersen / kumush[iqtibos kerak ]	Yo'q
5×50	5×10	50! × 10!20 × 674431748701227492664421138490224315931126734765581948747776 ≈ 3.2157×10255	Pettersen / kumush[iqtibos kerak ]	Yo'q
6×12	6×2	12! × 2!30 × 9480675056071680 = 4876139207527966044188061990912000 ≈ 4.8761×1033	Pettersen[59]	Yo'q

Bulmacalar

Berilganlarning minimal soni

Oddiy Sudokus (to'g'ri boshqotirmalar) noyob echimga ega. A minimal Sudoku - bu Sudoku bo'lib, undan tegishli Sudoku-ni qoldirib, uni olib tashlash mumkin emas. Turli xil minimal Sudokus turli xil belgilarga ega bo'lishi mumkin. Ushbu bo'limda to'g'ri jumboqlar uchun berilganlarning minimal soni muhokama qilinadi.

Oddiy Sudoku

17 ta ma'lumotga ega Sudoku.

17 ta ko'rsatma va diagonal simmetriyaga ega Sudoku.[60]

18 ta ishora va ortogonal simmetriyaga ega Sudoku.[61]

19 ta ko'rsatma va ikki tomonlama ortogonal simmetriyaga ega Sudoku.[63]

Ko'p Sudokus 17 ta ma'lumot bilan topilgan, ammo ularni topish ahamiyatsiz ish emas.^[64][65] Gari Makguayr, Bastian Tugemann va Gilles Civarioning 2012 yil 1 yanvarda chop etgan maqolasida har qanday to'g'ri Sudoku-dagi ko'rsatmalarning minimal soni 17 ga teng ekanligi kompyuterda to'liq qidiruv orqali qanday isbotlanganligi tushuntirilgan.^[66][67][12] va bu mustaqil ravishda 2013 yil sentyabr oyida tasdiqlangan.^[68] Diagonali simmetriya bilan bir nechta 17 ta jumboq Ed Rassell tomonidan ekvivalentlik o'zgarishi orqali qidiruvdan so'ng taqdim etildi. Gordon Royl 17 ta jumboqlarning ma'lumotlar bazasi.^[69][60] Sudoku jumboqlari 18 ta, 180 ° burilish simmetriyasi bilan, boshqalari esa ortogonal simmetriya bilan topilgan, ammo bu ikkala holatda ham bu son minimal bo'lishi ma'lum emas.^[61] Sudoku jumboqlari 19 ta ma'lumotdan iborat bo'lib, ular ikki tomonlama ortogonal simmetriya bilan topilgan va yana bu narsa uchun bu ko'rsatmalar soni minimal bo'lganligi noma'lum.^[63]

24 ta ma'lumotga ega Sudoku, dihedral simmetriya (ikkala ortogonal o'qdagi simmetriya, 90 ° rotatsion simmetriya, 180 ° rotatsion simmetriya va diagonal simmetriya) mavjud bo'lganligi ma'lum va shuningdek avtomorfik. Shunga qaramay, bu Sudoku sinfi uchun ushbu ko'rsatkichlarning minimalligi ma'lum emas.^[62][70] Ikki tomonlama diagonal simmetriyaga ega bo'lgan Sudoku-dagi eng kam ko'rsatmalar 18 ga teng, va kamida bitta holatda bunday Sudoku ham namoyish etadi avtomorfizm.

5.472.730.538 orasida Aslida turli xil eritma panjaralari, faqat 4tasida 20 ta jumboq yo'q - o'sha 4 ta katakchada 21 ta jumboq mavjud.^[71]

Boshqa o'lchamdagi Sudokus

• 4 × 4 (2 × 2) Sudoku: 4 × 4 Sudoku-dagi eng kam ko'rsatmalar 4 ta bo'lib, ulardan 13 ta teng bo'lmagan jumboq mavjud. (Ushbu o'lchamdagi teng bo'lmagan minimal Sudokuslarning umumiy soni 36 tani tashkil qiladi).^[72]
• 6 × 6 (2 × 3) Sudoku: eng kam ma'lumot 8 ga teng.^[73]
• 8 × 8 (2 × 4) Sudoku: eng kichik ko'rsatmalar 14.^[73]
• 10 × 10 (2 × 5) Sudoku: 22 ta maslahatlar bilan kamida bitta jumboq yaratildi.^[74] Bu mumkin bo'lgan eng kam bo'lganligi ma'lum emas.
• 12 × 12 (2 × 6) Sudoku: 32 ta ma'lumotdan iborat kamida bitta jumboq yaratildi.^[74] Bu mumkin bo'lgan eng kam bo'lganligi ma'lum emas.
• 12 × 12 (3 × 4) Sudoku: 30 ta maslahat bilan kamida bitta jumboq yaratildi.^[74] Bu mumkin bo'lgan eng kam bo'lganligi ma'lum emas.
• 15 × 15 (3 × 5) Sudoku: 48 ta maslahatlar bilan kamida bitta jumboq yaratildi.^[74] Bu mumkin bo'lgan eng kam bo'lganligi ma'lum emas.
• 16 × 16 (4 × 4) Sudoku: 55 ta maslahat bilan kamida bitta jumboq yaratildi.^[74] Bu mumkin bo'lgan eng kam bo'lganligi ma'lum emas.
• 25 × 25 (5 × 5) Sudoku: 151 ta ma'lumotdan iborat jumboq yaratildi.^{[75][iqtibos kerak ]} Bu mumkin bo'lgan eng kam bo'lganligi ma'lum emas.

Sudoku qo'shimcha cheklovlar bilan

Qo'shimcha cheklovlar (bu erda, 3 × 3 Sudokusda) eng kam miqdordagi ko'rsatmalarga olib keladi.

• Ajratilgan guruhlar: ba'zi 12 ta jumboq^[76] Glenn Fouler tomonidan namoyish etilgan. Keyinchalik, 11 ta jumboq ham topildi. Bu mumkin bo'lgan eng yaxshi ekanligi ma'lum emas.
• Hypercube: har xil 8 ta jumboq^[77] Guenter Stertenbrink tomonidan namoyish etilgan. Bu mumkin bo'lgan eng yaxshisi.
• Sehrli Sudoku: 7 ta misol^[78] Guenter Stertenbrink tomonidan taqdim etilgan. Bu mumkin bo'lgan eng yaxshi ekanligi ma'lum emas.
• Knight-ga qarshi Sudoku: 9 ta misol^[79] Reddit foydalanuvchisi u / wand125 tomonidan taqdim etilgan. Bu mumkin bo'lgan eng yaxshi deb gumon qilinmoqda.
• Sudoku X: 7193 ta 12 ta jumboq ro'yxati^[80] Rud van der Verf tomonidan to'plangan. Bu mumkin bo'lgan eng yaxshi ekanligi ma'lum emas.
• NRC Sudoku: 11 ta misol^[23] Andries Brouwer tomonidan taqdim etilgan. Bu mumkin bo'lgan eng yaxshi ekanligi ma'lum emas.
• 2-Quaz-Magic Sudoku: 4 ta misol^[81] Toni Forbes tomonidan taqdim etilgan. Bu mumkin bo'lgan eng yaxshi deb gumon qilinmoqda.

Sudoku tartibsiz hududlarga ega

"Du-sum-oh"^[82] (a.k.a. "geometriya number place") jumboqlari 3 × 3 o'rniga (yoki R×C) belgilangan o'lchamdagi tartibsiz shakllarga ega Sudoku mintaqalari. Bob Xarris isbotladi^[83] yaratish har doim ham mumkin (N - 1) -yangilangan du-sum-ohlar N×N va bir nechta misollarni yaratdi. Yoxan de Ruiter buni isbotladi^[84] bu har qanday kishi uchun N> 3 Sudoku jumboqiga aylantirib bo'lmaydigan poliomino plitalari mavjud N o'lchamning tartibsiz shakllari N.

Sumning umumiy joyi ("Killer Sudoku")

Jami sonli joyda (Samunampure) mintaqalar tartibsiz shaklga va har xil o'lchamlarga ega. Har qanday satr, ustun yoki mintaqada takrorlanadigan qiymatga ega bo'lmagan odatiy cheklovlar qo'llaniladi. Maslahatlar mintaqalar ichidagi qiymatlar yig'indisi sifatida berilgan (masalan, 10-yig'indisi bo'lgan 4 katakli mintaqa qandaydir tartibda 1,2,3,4 qiymatlardan iborat bo'lishi kerak). Samunampure uchun ko'rsatmalarning minimal soni ma'lum emas va hatto taxmin qilinmaydi. Miyuki Misavaning veb-saytidagi variant^[85] yig'indilarni munosabatlar bilan almashtiradi: ko'rsatmalar belgi =, < va > qo'shni mintaqa yig'indilarining (ba'zilari hammasi emas) nisbiy qiymatlarini ko'rsatish. U faqat sakkizta munosabatlar bilan bir misolni namoyish etadi. Bu eng yaxshi mumkinmi yoki yo'qmi noma'lum.

Berilganlarning maksimal soni

A uchun eng yaxshi ko'rsatmalar minimal Sudoku 40 yoshda deb ishoniladi, ulardan faqat ikkitasi ma'lum. Agar Sudokusning ikkalasidan ham biron bir maslahat olib tashlansa, jumboq bir nechta echimga ega bo'lar edi (va shuning uchun tegishli Sudoku bo'lmaydi). Ushbu Sudokuslarni topish bo'yicha ishlarda boshqa yuqori darajadagi jumboqlar, shu jumladan 36 ta ma'lumotdan iborat 6 500 000 000 dan ortiq minimal jumboqlar katalogga kiritilgan. Taxminan 2600 ta minimal Sudokus topildi va 39 ta ma'lumot topildi.^[86]

Agar eritmaning o'ziga xosligi talabidan voz kechilsa, 41 ta minimal minimal psevdo-jumboq mavjud ekanligi ma'lum, ammo ularni bir nechta eritma panjarasida bajarish mumkin. Har qanday maslahatni olib tashlash tugallanishlar sonini ko'paytiradi va shu nuqtai nazardan 41 ta maslahatning hech biri ortiqcha bo'lmaydi. Berilganlar bilan to'ldirilgan katakning yarmidan ko'prog'i bilan (81 ta katakchadan 41 tasi) o'ziga xoslik hal etish cheklovi hali ham ustunlik qiladi minimallik cheklash.^[87]

Ga kelsak eng Sudokuda hanuzgacha ma'lumot olish mumkin emas noyob echimini taqdim etish, bu to'liq tarmoqqa to'rtta qisqa (77). Agar har birida ikkita sonli ikkita misol etishmayotgan bo'lsa va ular egallashi kerak bo'lgan kataklar to'rtburchak to'rtburchakning burchaklari bo'lsa va ushbu katakchalarning aniq ikkitasi bitta mintaqaning ichida bo'lsa, oxirgi raqamlarni qo'shishning ikkita usuli bor (ikkita echim).

Minimal jumboqlarning soni

Minimal Sudokus soni (Sudokus, unda biron bir maslahat o'chirilmasdan, echimning o'ziga xosligini yo'qotmasdan) aniq ma'lum emas. Biroq, statistik metodlar generator bilan birlashtirilgan ("CSPning xolis statistikasi - boshqariladigan tarafkashlik generatori"),^[88] taxminan (0,065% nisbiy xato bilan) mavjudligini ko'rsating:

• 3.10 × 10³⁷ minimal jumboq,
• 2.55 × 10²⁵ mohiyatan teng bo'lmagan minimal jumboqlar.

Boshqa mualliflar tezroq usullarni qo'lladilar va qo'shimcha aniq tarqatish statistikasini hisobladilar.^[89]

Ma'lumot geometriyasining cheklovlari

To'g'ri Sudoku uchun etarli bo'lmagan bir qator ko'rsatkichlar.

Sudoku, 30 katakli (5 x 6) bo'sh to'rtburchak. (22 ta maslahat)

To'qqiz bo'sh guruh bilan Sudoku. (22 ta maslahat)

Hech bir Sudoku yuqoridagi naqshdagi pozitsiyalar oralig'ida cheklangan ma'lumotlarga ega bo'lmasligi mumkin (birinchi rasm).^[90] Tegishli Sudoku-dagi eng katta to'rtburchaklar orgonal "teshik" (hech qanday ma'lumotga ega bo'lmagan mintaqa) 30 hujayradan iborat to'rtburchak (5 × 6 to'rtburchaklar maydon) deb ishoniladi.^[91][92] Bir misol - 22 ta ma'lumotga ega Sudoku (ikkinchi rasm). Sudokudagi eng katta bo'sh guruhlar soni (qatorlar, ustunlar va qutilar) to'qqiztaga to'g'ri keladi. Bir misol - 3 ta bo'sh satr, 3 ta ustunli ustun va 3 ta bo'sh quti bo'lgan Sudoku (uchinchi rasm).^[93][94]

Automorphic Sudokus

Sudoku panjarasi, agar uni asl tarmoqqa olib boradigan tarzda o'zgartirish mumkin bo'lsa, xuddi shu transformatsiya boshqa yo'l bilan qaytib kelmasa, avtomorfik bo'ladi. Avtomorfik bo'lgan katakchaning bir misoli 180 daraja aylantirilishi mumkin bo'lgan panjara bo'lishi mumkin, natijada yangi katak paydo bo'ladi, bu erda yangi katak qiymatlari asl panjara o'rnini bosadi. Automorphic Sudokus - bu avtomorfik tarmoqni hal qiladigan Sudoku jumboqlari. Avtomorfik Sudokusning ikkita misoli va avtomorfik tarmoq quyida keltirilgan.

18 ta ma'lumotga ega bo'lgan avtomorfli Sudoku (ikki tomonlama diagonal simmetriya)[95]

24 ta maslahatga ega bo'lgan avtomorfik Sudoku (ikki tomonlama diagonal simmetriya va tarjima simmetriyasi)[96]

"Eng kanonik" echimlar panjarasi (648 avtomorfizm)

Har birida bir-biridan farq qiladigan katakchalar soni
avtomorfizmni hisoblash

Avtomatik- morfizmlar	Yo'q panjara	Avtomatik- morfizmlar	Yo'q panjara
1	5472170387	18	85
2	548449	27	2
3	7336	36	15
4	2826	54	11
6	1257	72	2
8	29	108	3
9	42	162	1
12	92	648	1

Dastlabki ikkita misolda, agar Sudoku 180 gradusga aylantirilsa va (123456789) -> (987654321) almashtirish bilan yozilgan bo'lsa, u yana o'sha Sudokuga qaytishiga e'tibor bering. Ushbu Sudokuslar boshqa yo'l bilan aytganda, har 180 graduslik aylanma juftlik (a, b) (a) + (b) = 10 qoidaga amal qilish xususiyatiga ega.

Ushbu Sudokuslar avtomorf bo'lganligi sababli, ularning echimlari tarmoqlari ham avtomorfdir. Bundan tashqari, har bir echilgan hujayra bir xil texnikada echilgan nosimmetrik sherikga ega (va juftlik a + b = 10 shaklini oladi). E'tibor bering, ikkinchi misolda Sudoku ham namoyish etadi tarjima (or repetition) symmetry; clues are clustered in groups, with the clues in each group ordered sequentially (i.e., n, n+1, n+2, and n+3).

The third image is the Most Canonical solution grid.^[97] This grid has 648 automorphisms and contributes to all ~6.67×10²¹ solution grids by factor of 1/648 compared to any non-automorphic grid.

In these examples the automorphisms are easy to identify, but in general automorphism is not always obvious. The table at right shows the number of the essentially different Sudoku solution grids for all existing automorphisms.^[11]

Details of enumerating distinct grids (9×9)

An enumeration technique based on band generation was developed that is significantly less computationally intensive. The strategy begins by analyzing the almashtirishlar of the top band used in valid solutions. Once the Band1 simmetriya va ekvivalentlik sinfi for the partial solutions are identified, the completions of the lower two bands are constructed and counted for each equivalence class.

Counting the top band permutations

1	2	3
4	5	6
7	8	9

The Band1 algorithm proceeds as follows:

• Choose a canonical labeling of the digits by assigning values for B1 (see grid), and compute the rest of the Band1 permutations relative B1.
• Compute the permutations of B2 by bo'lish the B1 cell values over the B2 row uch egizaklar. From the triplet combinations compute the B2 permutations. There are k=0..3 ways to choose the:

B1 r11 values for B2 r22, the rest must go to r16,

B1 r12 values for B2 r23, the rest must go to r16,

B1 r13 values for B2 r21, the rest must go to r16, i.e.

${displaystyle {mbox{N combinations for B2}}=sum _{k=0}^{3}{{3 choose k}^{3}}}$

(This expression may be generalized to any R×3 box band variant. (Pettersen^[30]). Thus B2 contributes 56 × 6³ almashtirishlar.

• The choices for B3 triplets are row-wise determined by the B1 B2 row triplets. B3 always contributes 6³ almashtirishlar.

The permutations for Band1 are 9! × 56 × 6⁶ = 9! × 2612736 ≈ 9.48×10¹¹.

Band1 permutation details

Triplet rBR(box/row) Labels

r 1 1 r 1 2 r 1 3

r 2 1 r 2 2 r 2 3

r 3 1 r 3 2 r 3 3

The permutations of B1 are the number of ways to relabel the 9 digits, 9! = 362880. Counting the permutations for B2 is more complicated, because the choices for B2 depend on the values in B1. (This is a visual representation of the expression given above.) The conditional calculation needs a branch (sub-calculation) for each alternative. Fortunately, there are just 4 cases for the top B2 triplet (r21): it contains either 0, 1, 2, or 3 of the digits from the B1 middle row triplet(r12). Once this B2 top row choice is made, the rest of the B2 combinations are fixed. The Band1 row triplet labels are shown on the right.

(Note: Conditional combinations becomes an increasingly difficult as the computation progresses through the grid. At this point the impact is minimal.)

Case 0 Matching Cells Triplets

1 2 3 4 5 6 7 8 9

7 8 9 1 2 3 4 5 6

4 5 6 7 8 9 1 2 3

Case 0: No Overlap. The choices for the triplets can be determined by elimination.

r21 can't be r11 or r12 so it must be = r13; r31 must be = r12 etc.

The Case 0 diagram shows this configuration, where the pink cells are triplet values that can be arranged in any order within the triplet.Each triplet has 3! = 6 permutations. The 6 triplets contribute 6⁶ almashtirishlar.

Case 3: 3 Digits Match: triplet r21 = r12. The same logic as case 0 applies, but with a different triplet usage.Triplet r22 must be = r13, etc.The number of permutations is again 6⁶ (Felgenhauer/Jarvis).^[10] Call the cases 0 and 3 the pure match ish.

Case 1 Match – Triplet Cell Options

1 2 3 4 5 6 7 8 9

3 3 2 1 3 2 1 2 1

3 2 1 3 2 1 3 2 1

Case 1: 1 Match for r21 from r12

In the Case 1 diagram, B1 cells show canonical values, which are color-coded to show their row-wise distribution in B2 triplets. Colors reflect distribution but not location or values. For this case: the B2 top row triplet (r21) has 1 value from B1 middle triplet, the other colorings can now be deduced. Masalan, the B2 bottom row triplet (r23) coloring is forced by r21: the other 2 B1 middle values must go to bottom, etc. Fill in the number of B2 options for each color, 3..1, beginning top left. The B3 color-coding is omitted since the B3 choices are row-wise determined by B1, B2. B3 always contributes 3! permutations per row triplet, or 6³ for the block.

For B2, the triplet values can appear in any position, so a 3! permutation factor still applies, for each triplet. However,since some of the values were paired relative to their origin, using the raw option counts would overcount the number of permutations, due to interchangeability within the pairing. The option counts need to be divided by the permuted size of their grouping (2), here 2! = 2 (See ${displaystyle color {Blue}{n choose k}}$ ) The pair in each row cancels the 2s for the B2 option counts, leaving a B2 contribution of 3³ × 6³. The B2×B3 combined contribution is 3³ × 6⁶.

Case 2 Match – Triplet Cell Options

1 2 3 4 5 6 7 8 9

3 2 3 2 1 3 2 1 1

3 2 1 3 2 1 3 2 1

Case 2: 2 Matches for r21 from r12. The same logic as case 1 applies, but with the B2 option count column groupings reversed. Case 3 also contributes 3³×6⁶ almashtirishlar.

Totaling the 4 cases for Band1 B1..B3 gives9! × 2 × (3³ + 1) × 6⁶ = 9! 56 × 6⁶ almashtirishlar.

Band1 symmetries and equivalence classes

Nosimmetrikliklar are used to reduce the computational effort to enumerate the Band1 permutations. A simmetriya is an operation that preserves a quality of an object. For a Sudoku grid, a symmetry is a transformation whose result is also a valid grid. The following symmetries apply independently for the top band:

• Block B1 values may be relabeled, giving 9! almashtirishlar
• Blocks B1..3 may be interchanged, with 3!=6 permutations
• Rows 1..3 may be interchanged, with 3!=6 permutations
• Within each block, the 3 columns may be interchanged, giving 3!³ = 6³ almashtirishlar.

Combined, the symmetries give 9! × 6⁵ = 362880 × 7776 equivalent permutations for each Band1 solution.

A symmetry defines an ekvivalentlik munosabati, here, between the solutions, and bo'limlar the solutions into a set of ekvivalentlik darslari. The Band1 row, column and block symmetries divide the ${displaystyle 56 imes 6^{6}}$ permutations into (not less than) 336 (56×6) equivalence classes with (up to) 6⁵ permutations in each, and 9! relabeling permutations for each class. (Min/Max caveats apply since some permutations may not yield distinct elements due to relabeling.)

Since the solution for any member of an equivalence class can be generated from the solution of any other member, we only need to enumerate the solutions for a single member in order to enumerate all solutions over all classes. Ruxsat bering

• sb : be a valid permutation of the top band
• Sb = [sb] : be an equivalence class, relative to sb and some ekvivalentlik munosabati
• Sb.z = |Sb| : the size of Sb, be the number of sb elements (permutations) in [sb]
• Sb.n : be the number of Band2,3 completions for (any) sb in Sb
• {Sb} : be the set of all Sb equivalence classes relative to the ekvivalentlik munosabati
• {Sb}.z = |{Sb}| : be the number of equivalence classes

The total number of solutions N keyin:

N =  Σ{Sb} Sb.z  ×  Sb.n

Solution and counting permutation symmetry

The Band1 symmetries (above) are solution permutation symmetries defined so that a permuted solution is also a solution. For the purpose of enumerating solutions, a counting symmetry for grid completion can be used to define band equivalence classes that yield a minimal number of classes.

Counting symmetry partitions valid Band1 permutations into classes that place the same completion constraints on lower bands; all members of a band counting symmetry equivalence class must have the same number of grid completions since the completion constraints are equivalent. Counting symmetry constraints are identified by the Band1 column triplets (a column value set, no implied element order). Using band counting symmetry, a minimal generating set of 44 equivalence classes^[55] tashkil etildi.

(1) Band1 Example 1 2 3 4 5 6 7 8 9 5 8 6 9 1 7 4 3 2 7 4 9 8 2 3 5 1 6

(2) Column Triplets 1 2 3 4 5 6 7 8 9 4 1 2 5 3 6 9 8 7 5 1 3 7 2 6 8 4 9

(3) Ordered Col. Triplets 1 2 3 4 5 6 7 8 9 1 3 5 2 6 7 4 9 8 1 2 4 3 6 5 8 7 9

The following sequence demonstrates mapping a band configuration to a counting symmetry equivalence class. Begin with a valid band configuration (1). Build column triplets by ordering the column values within each column. This is not a valid Sudoku band, but does place the same constraints on the lower bands as the example (2). Construct an equivalence class ID from the B2, B3 column triplet values. Use column and box swaps to achieve the lowest lexicographical ID. The last figure shows the column and box ordering for the ID: 124 369 578 138 267 459. All Band1 permutations with this counting symmetry ID will have the same number of grid completions as the original example. An extension of this process can be used to build the largest possible band counting symmetry equivalence classes (3).

Note, while column triplets are used to construct and identify the equivalence classes, the class members themselves are the valid Band1 permutations: class size (Sb.z) reflects column triplet permutations compatible with the Bitta qoida solution requirements. Counting symmetry is a completion property and applies only to a partial grid (band or stack). Solution symmetry for preserving solutions can be applied to either partial grids (bands, stacks) or full grid solutions. Lastly note, counting symmetry is more restrictive than simple numeric completion count equality: two (distinct) bands belong to the same counting symmetry equivalence class only if they impose equivalent completion constraints.

Band 1 reduction details

Symmetries group similar object into ekvivalentlik darslari. Two numbers need to be distinguished for equivalence classes, and band symmetries as used here, a third:

• the number of equivalence classes ({Sb}.n).
• The kardinallik, size or number of elements in an equivalence class, which may vary by class (Sb.z)
• the number of Band2,3 completions compatible with a member of a Band1 equivalence class (Sb.n)

The Band1 (6⁵) symmetries divide the (56×6⁶) Band1 valid permutations into (not less than) 336 (56×6) equivalence classes with (up to) ${displaystyle 6^{5}}$ permutations each.The not less than va qadar caveats are necessary, since some combinations of the transformations may not produce distinct results, when relabeling is required (see below). Consequently, some equivalence classes may contain less than 6⁵ distinct permutations and the theoretical minimum number of classes may not be achieved.

Each of the valid Band1 permutations can be expanded (completed) into a specific number of solutions with the Band2,3 permutations. By virtue of their similarity, each member of an equivalence class will have the same number of completions. Consequently, we only need to construct the solutions for one member of each equivalence class and then multiply the number of solutions by the size of the equivalence class. We are still left with the task of identifying and calculating the size of each equivalence class. Further progress requires the dexterous application of computational techniques to catalogue (classify and count) the permutations into equivalence classes.

Felgenhauer/Jarvis^[10] catalogued the Band1 permutations using lexicographical ordered IDs based on the ordered digits from blocks B2,3. Block 1 uses a canonical digit assignment and is not needed for a unique ID. Equivalence class identification and linkage uses the lowest ID within the class.

Application of the (2×6²) B2,3 symmetry permutations produces 36288 (28×6⁴) equivalence classes, each of size 72. Since the size is fixed, the computation only needs to find the 36288 equivalence class IDs. (Note: in this case,for any Band1 permutation, applying these permutations to achieve the lowest ID provides an index to the associated equivalence class.)

Application of the rest of the block, column and row symmetries provided further reduction, i.e. allocation of the 36288 IDs into fewer, larger equivalence classes.When the B1 canonical labeling is lost through a transformation, the result is relabeled to the canonical B1 usage and then catalogued under this ID. This approach generated 416 equivalence classes, somewhat less effective than the theoretical 336 minimum limit for a full reduction. Qo'llash counting symmetry patterns for duplicate paired digits achieved reduction to 174 and then to 71 equivalence classes. The introduction of equivalence classes based on band counting symmetry (subsequent to Felgenhauer/Jarvis by Russell^[55]) reduced the equivalence classes to a minimum generating set of 44.

The diversity of the ~2.6×10⁶, 56×6⁶ Band1 permutations can be reduced to a set of 44 Band1 equivalence classes. Each of the 44 equivalence classes can be expanded to millions of distinct full solutions, but the entire solution space has a common origin in these 44. The 44 equivalence classes play a central role in other enumeration approaches as well, and speculation will return to the characteristics of the 44 classes when puzzle properties are explored later.

Band 2–3 completion and results

Enumerating the Sudoku solutions breaks into an initial setup stage and then into two nested loops. Initially all the valid Band1 permutations are grouped into equivalence classes, who each impose a common constraint on the Band2,3 completions.For each of the Band1 equivalence classes, all possible Band2,3 solutions need to be enumerated. An outer Band1 loop iterates over the 44 equivalence classes. In the inner loop, all lower band completions for each of the Band1 equivalence class are found and counted.

The computation required for the lower band solution search can be minimised by the same type of symmetry application used for Band1. There are 6! (720) permutations for the 6 values in column 1 of Band2,3. Applying the lower band (2) and row within band (6×6) permutations creates 10 equivalence classes of size 72. At this point, completing 10 sets of solutions for the remaining 48 cells with a recursive descent, orqaga qaytish algorithm is feasible with 2 GHz class PC so further simplification is not required to carry out the enumeration. Using this approach, the number of ways of filling in a blank Sudoku grid has been shown to be 6,670,903,752,021,072,936,960 (6.67×10²¹).^[10]

The result, as confirmed by Russell,^[55] also contains the distribution of solution counts for the 44 equivalence classes. The listed values are before application of the 9! factor for labeling and the two 72 factors (72² = 5184) for each of Stack 2,3 and Band2,3 permutations. The number of completions for each class is consistently on the order of 100,000,000, while the number of Band1 permutations covered by each class however varies from 4 – 3240. Within this wide size range, there are clearly two clusters. Ranked by size, the lower 33 classes average ~400 permutations/class, while the upper 11 average ~2100. The disparity in consistency between the distributions for size and number of completions or the separation into two clusters by size is yet to be examined.

Shuningdek qarang

• Sudoku - asosiy maqola
• Sudoku echish algoritmlari
• Sudoku lug'ati
• Kombinatorial portlash (with summary of grid count of Sudoku compared to Latin squares)
• Sudoku variants
• Raqsga havolalar
• Sudoku Codes

Adabiyotlar

Qo'shimcha o'qish

• Rozenxaus, Jeyson; Taalman, Laura (2011). Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle. Oksford universiteti matbuoti.

Tashqi havolalar

• V. Elser's difference-map algorithm also solves Sudoku
• Sudoku Puzzle — an Exercise in Constraint Programming and Visual Prolog 7 by Carsten Kehler Holst (in Visual Prolog )
• Sudoku Squares and Chromatic Polynomials tomonidan Gertsberg and Murty, treats Sudoku puzzles as vertexni bo'yash muammolar grafik nazariyasi.