Šach sa pri prvom pohľade javí ako jednoduchá hra. Máte plochu so 64 čiernymi a bielymi políčkami a 16 figúrok na jednej a druhej strane, a dvoch súperov snažiacich sa o zajatie kráľa v šachu.
Ak však študujete šach hlbšie, dostávate veľké množstvo komplexných možností a následných ťahov, ktoré sú veľkými výzvami aj pre šachových veľmajstrov.
Problém 8 kráľovien
Ten, kto pozná aspoň základy hry šach, vie, že najmocnejšou figúrkou je kráľovná. Má najväčšie možnosti pohybu a v nemeckom šachovom časopise z roku 1848 bola raz položená otázka: „Vzhľadom na štandardnú šachovnicu, koľko je možných usporiadaní 8 dám tak, aby sa navzájom neohrozovali?“ Ako píše portál IFLScience, o niekoľko rokov sa objavila odpoveď, a tou je 92 spôsobov.
Následne v roku 1869 však bol predostretý nový problém, a to, ako by situácia vyzerala na oveľa väčšej šachovnici, napríklad 1 000 x 1 000. Koľkými spôsobmi by na takejto šachovnici bolo možné usporiadať 1 000 kráľovien bez ohrozenia? A čo na poli s milión krát milión?
Trvalo viac ako 150 rokov, kým sa našla odpoveď. V novom dokumente, ktorý je predtlačovo dostupný na arXi,v prichádza s odpoveďou Michael Simkin z Harvardu.
Prišiel na vzorec
Simkin vypočítal, že pre n kráľovien na šachovnici n krát n existuje približne (0,143 n)n usporiadaní kráľovien. Znamená to, že napríklad na šachovnici 1 000 x 1 000 je približne (0,143 × 1 000) 1 000 = 143 1 000 rôznych spôsobov, ako usporiadať 1 000 kráľovien. Výsledné číslo má, mimochodom, v tomto prípade dĺžku viac ako 2 000 číslic. Ak by sme sa bavili o šachovnici milión krát milión, výsledok by obsahoval 5 miliónov číslic.
Tento výsledok nie je presný, je však veľmi blízko výsledku. Existuje dôvod, prečo tento problém n-kráľovien zostal tak dlho nevyriešený. Napriek vývoju kombinatorických nástrojov, žiadny nebol taký dobrý, aby tento problém dokázal vyriešiť.
Simkin prijal hybridnú metódu a skonštruoval randomizovaný algorizmus na získanie dolnej hranice počtu usporiadaní a potom ju skombinoval s inou štandardnou metódou, aby našiel hornú hranicu. Zistil, že obidva výpočty poskytli pozoruhodne tesné výsledky.
Riešenie problému je dlho očakávaným pre fanúšikov šachu, ako aj pre Simkina osobne, ktorý na ňom pracoval už 5 rokov.
Nahlásiť chybu v článku