Hārvardas matemātiķis būtībā ir atrisinājis episku, 150 gadus vecu šaha problēmu

(Heidija Volija/Unsplash)

Vienā līmenī šahs šķiet vienkārša spēle: 64 atsevišķi melni vai balti lauciņi, 16 figūriņas katrā pusē un divi konkurenti, kas tiecas pēc iekarošanas.

Tomēr iedziļinieties, un spēle piedāvā neticami sarežģītas iespējas, radot izaicinājumus šaha teorētiķiem un matemātiķiem, kas var palikt neatrisināti gadu desmitiem vai pat gadsimtiem.

2021. gada jūlijā viens šāds izaicinājums beidzot tika atrisināts – vismaz līdz noteiktam punktam. Matemātiķis Maikls Simkins no Hārvardas universitātes Masačūsetsā pielika savu prātu n-queens problēma tas ir mulsinājis ekspertus kopš tā pirmās iedomāšanās 1840. gados.



Ja jūs zināt savu šahu, jūs zināt, ka dāma ir visspēcīgākā figūra uz galda, kas spēj pārvietot jebkuru kvadrātu skaitu jebkurā virzienā. n-dāmu problēma jautā: ar noteiktu skaitu dāmu (n), cik izkārtojumu ir iespējams, ja dāmas atrodas pietiekami tālu viena no otras, lai neviena no tām nevarētu ņemt nevienu no pārējām?

Astoņām dāmām uz standarta 8 x 8 dēļa atbilde ir 92, lai gan lielākā daļa no tām ir tikai 12 pamatrisinājumu pagriezti vai atspoguļoti varianti.

Bet kā ar 1000 dāmām uz tāfeles, kas ir 1000 x 1000 kvadrātu? Kā ir ar miljonu karalieņu? Simkina aptuvenais problēmas risinājums ir (0,143n)n– dāmu skaits, kas reizināts ar 0,143, palielināts līdz pakāpei n.

Tas, kas jums paliek, nav precīza atbilde, taču tā ir tik tuvu, cik šobrīd iespējams. Ar miljonu dāmu skaitlis tiek parādīts kā skaitlis ar pieciem miljoniem ciparu aiz tā, tāpēc mēs to šeit neatveidosim.

Bija vajadzīgi gandrīz pieci gadi, līdz Simkins nāca klajā ar vienādojumu, izmantojot dažādas pieejas un metodes, kā arī dažus šķēršļus ceļā uz risinājumu. Galu galā matemātiķis varēja aprēķināt iespējamo risinājumu apakšējās un augšējās robežas, izmantojot dažādas metodes, konstatējot, ka tās gandrīz sakrīt.

'Ja jūs man teiktu, ka es vēlos, lai jūs savās dāmās ievietotu tā un tā, tad es varētu analizēt algoritmu un pateikt, cik daudz risinājumu ir, kas atbilst šim ierobežojumam.' saka Simkins .

'Formālā izteiksmē tas samazina problēmu līdz optimizācijas problēmai.'

Sākumā Simkins un kolēģis Zur Luria no Šveices Cīrihes Federālā tehnoloģiju institūta sadarbojies par n-karalienes problēmas variantu, kas pazīstams kā torodiālā vai modulārā problēma. Šajā gadījumā diagonāles apvijas ap dēli, lai karaliene varētu pa diagonāli pārvietoties no dēļa labās malas un atkal parādīties, piemēram, kreisajā pusē.

Tas katrai dāmai piešķir uzbrukuma simetriju, taču tā nedarbojas parasts šaha galds: dāmai galda stūrī nav tik daudz uzbrukuma leņķu kā centrā.

Galu galā pāra darbs pie toroidālās problēmas apstājās (lai gan viņi publicēja dažus rezultātus), bet Simkins galu galā pielāgoja dažus šī darba augļus savā galīgajā risinājumā.

Tā kā dēļi kļūst lielāki un palielinās dāmu skaits, pētījumi liecina, ka lielākajā daļā pieļaujamo konfigurāciju dāmas mēdz pulcēties gar dēļa malām, un vidū ir mazāk dāmu, kur tās ir pakļautas uzbrukumam. Šīs zināšanas nodrošina svērtāku pieeju.

Teorētiski vajadzētu būt iespējamai precīzākai atbildei uz n-queen mīklu, taču Simkins mūs ir satuvinājis vairāk nekā jebkad agrāk, un viņš ar prieku nodod izaicinājumu kādam citam, lai viņš varētu mācīties tālāk.

'Es domāju, ka man personīgi n-queens problēma uz kādu laiku varētu būt beigusies, nevis tāpēc, ka ar to nav nekā cita, bet tikai tāpēc, ka esmu sapņojis par šahu un esmu gatavs turpināt darbu. mana dzīve,' saka Simkins .

Simkina papīrs par risinājumu ir pieejams pirmsdrukas serverī arXiv .

Populārākas Kategorijas: Daba , Cilvēkiem , Dabu , Tech , Veselība , Skaidrotājs , Neklasificēts , Sabiedrību , Viedoklis , Telpa ,

Par Mums

Neatkarīgu, Pārbaudītu Faktu Publicēšana Par Veselību, Telpu, Dabu, Tehnoloģijām Un Vidi.