211service.com
Matemātiķi atrisina minimālo Sudoku problēmu
Sudoku ir skaitļu mīkla, kas sastāv no 9 x 9 režģa, kurā dažās šūnās ir norādes ciparu formā no 1 līdz 9. Risinātāja uzdevums ir aizpildīt pārējās šūnas tā, lai katra rinda, kolonna un 3 × 3 lodziņš režģī ir visi deviņi cipari.
Ir vēl viens nerakstīts noteikums: mīklai ir jābūt tikai vienam risinājumam. Tātad režģos nevar būt tikai dažas sākuma norādes.
Ir viegli saprast, kāpēc. Režģim ar 7 norādēm nevar būt unikāla atbilde, jo divus trūkstošos ciparus vienmēr var apmainīt jebkurā risinājumā. Līdzīgs arguments izskaidro, kāpēc režģiem ar mazāk norādēm ir jābūt arī vairākiem risinājumiem.
Taču nav tik viegli saprast, kāpēc režģim ar 8 norādēm nevar būt unikāls risinājums vai arī tādam, kurā ir 9 vai vairāk norādes.
Tas rada interesantu jautājumu matemātiķiem: kāds ir minimālais Sudoku pavedienu skaits, kas rada unikālu atbildi?
Šis ir jautājums, kas ir smags pāri Sudoku kopienai, jo īpaši tāpēc, ka viņi domā, ka zina atbildi. Sudoku fanātiķi ir atraduši daudzus piemērus režģim ar 17 norādēm, kuriem ir unikāls risinājums, taču viņi nekad nav atraduši vienu ar 16 norādēm.
Tas liek domāt, ka minimālais skaitlis ir 17, taču neviens nav spējis pierādīt, ka kaut kur mīklu vietā nepastāv 16 pavedienu risinājums.
Ienāc Gerijs Makgvairs un draugi Dublinas Universitātes koledžā. Šie puiši ir atrisinājuši problēmu, izmantojot pārbaudītu un uzticamu matemātisko paņēmienu, ko izmanto tīrā brutālā spēka paņēmienā.
Būtībā šie puiši ir izpētījuši visus iespējamos 16 norāžu risinājumus katram iespējamajam Sudoku tīklam. Viņi saka, ka mūsu meklējumos netika atrasta neviena atbilstoša 16 pavedienu mīkla, taču, ja tāda būtu bijusi, mēs to būtu atraduši.
Tas ir iespaidīgs varoņdarbs. Ir tieši 6, 670, 903, 752, 021, 072, 936, 960 iespējamie Sudoku risinājumi (apmēram 10^21). Tas ir daudz vairāk, nekā var pārbaudīt saprātīgā laika periodā.
Bet, tā kā tas būtu, nav nepieciešams tos visus pārbaudīt. Dažādi simetrijas argumenti pierāda, ka daudzi no šiem režģiem ir līdzvērtīgi. Tas samazina pārbaudāmo skaitu līdz 5, 472, 730, 538.
Tāpēc Makgaivers un līdzinieki uzrakstīja programmu Checker, lai pārbaudītu, vai katrā no šiem režģiem nav 16 atlupu risinājuma.
Taču viena režģa pārbaudes process pats par sevi ir grūts. Viens no veidiem, kā to izdarīt, ir izpētīt visas iespējamās 16 norāžu apakškopas, lai noskaidrotu, vai kāds no tiem noved pie unikāla risinājuma. Problēma ir tāda, ka katram režģim ir aptuveni 10^16 apakškopas.
Atkal noder nedaudz matemātikas. Makgvairs un viņa kolēģi izmantoja dažus gudrus argumentus, lai parādītu, ka noteiktas apakškopas ir līdzvērtīgas daudzām citām, un tas ievērojami samazina pārbaudāmo apakškopu skaitu.
Neskatoties uz to, iegūtais aprēķins joprojām ir briesmonis. Dublinas komanda saka, ka apstrādes laiks iekārtā ar 640 Intel Xeon seškodolu procesoriem prasīja 7,1 miljonu kodolstundu. Tās sākās 2011. gada janvārī un beidzās decembrī.
Viss vingrinājums var šķist mazliet matemātisks jautrs, taču šāda veida problēmu risināšanai ir daudz svarīgu pielietojumu. Makgvairs un kolēģi saka, ka Sudoku režģa pārbaudes problēma formāli ir līdzvērtīga problēmām gēnu ekspresijas analīzē un datortīklu un programmatūras testēšanā.
Tātad Dublinas komandas metodēm aprēķinu paātrināšanai būs tieša ietekme arī šajās jomās.
Bet, lai gan rezultāts ir nepārprotami iespaidīgs, Minimālā Sudoku problēma nav pilnībā atrisināta.
Šī problēma kliedz pēc eleganta pierādījuma, kas ļauj mums saprast, kāpēc minimālajam skaitlim ir jābūt 17; drīzāk kā pierādījums tam, ka nevar būt unikālu risinājumu 7 vai mazāk pavedieniem.
Es zinu, ka tas ir liels jautājums, bet noteikti ir vērts censties.
Atsauce: arxiv.org/abs/1201.0749 : nav 16 pazīmju Sudoku: Sudoku minimālā norādes skaita problēmas risināšana
Labojums: šī ziņa tika rediģēta 6. janvārī, lai atspoguļotu argumentu, ka, ja n-clue režģis ir unikāli atrisināms, tad arī cipara pievienošanai, lai izveidotu n+1 pavedienu režģi, ir jābūt unikāli atrisināmam. Tātad, ja nav unikāli atrisināmu 16 norāžu režģu, nevar būt unikāli atrisināmu režģu ar mazāk norāžu skaitu. Paldies RealMurph un abooij.