Halsey Andrews Z jednej strony szachy wydają się prostą grą: 64 pojedyncze czarne lub białe kwadraty, 16 pionów na stronę i dwóch przeciwników dążących do podboju.
Kop jednak trochę głębiej, a gra przedstawia niezwykle złożone możliwości, stawiając przed teoretykami szachów i matematykami wyzwania, które mogą pozostać nierozwiązane przez dziesięciolecia, a nawet stulecia.
W lipcu 2021 r. jedno z tych wyzwań zostało ostatecznie rozwiązane — przynajmniej do pewnego stopnia. Miał to na myśli matematyk Michael Simkin z Uniwersytetu Harvarda w Massachusetts problem z n-królowymi Wprawiało to w zakłopotanie ekspertów, odkąd wymyślono to po raz pierwszy w latach 40. XIX wieku.
Jeśli znasz swoje własne szachy, wiesz, że hetman jest najpotężniejszą figurą na szachownicy, zdolną do poruszania się o dowolną liczbę pól w dowolnym kierunku. Problem n-matek zadaje następujące pytanie: przy danej liczbie hetmanów (n), ile jest możliwych aranżacji, w których królowe są na tyle daleko od siebie, że żadna z nich nie może zabrać żadnej z pozostałych hetmanów?
Dla ośmiu hetmanów na standardowej planszy 8×8 odpowiedź to 92, chociaż większość tych hetmanów jest rotowanych lub odwróconych tylko przez 12 podstawowych rozwiązań.
A co z 1000 królowych na planszy o wymiarach 1000 x 1000 kwadratów? A może milion królowej? Przybliżone rozwiązanie problemu Simkina to (0,143 n)n Liczba matek pomnożona przez 0,143 do potęgi n.
To, z czym ci pozostało, nie jest dokładną odpowiedzią, ale jest tak blisko, jak to tylko możliwe. W przypadku miliona królowych liczba ta pojawia się po niej jako liczba składająca się z pięciu milionów cyfr – więc nie będziemy jej tutaj odtwarzać.
Prawie pięć lat zajęło Simkinowi wymyślenie równania, przy użyciu różnych metod i technik oraz kilku przeszkód na drodze do rozwiązania. W końcu matematyk był w stanie obliczyć dolne i górne granice możliwych rozwiązań przy użyciu różnych metod i stwierdził, że są one prawie identyczne.
„Gdybyś mi powiedział, że chcę, abyś umieścił swoje hetmany w taki a taki sposób na szachownicy, byłbym w stanie przeanalizować algorytm i powiedzieć, ile rozwiązań pasuje do tego ograniczenia” Simkin mówi.
„Z formalnego punktu widzenia sprowadza to problem do problemu optymalizacji”.
Na początku Simkin i jego kolega Zur Luria pracowali w Szwajcarskim Federalnym Instytucie Technologii w Zurychu współpracować Na odmianie problemu n-królowych znanej jako problem cykliczny lub modułowy. Na tej figurze przekątne owijają się wokół planszy, więc hetman może odsunąć się po przekątnej od prawej krawędzi planszy i pojawić się na przykład po lewej stronie.
Daje to symetrię każdej hetmana do ataku, ale nie tak działa normalna szachownica: hetman w rogu szachownicy nie ma tylu kątów ataku, jak ten w środku.
W końcu mąż Przestań pracować nad problemem pętli (Chociaż opublikowali pewne wyniki), Simkin ostatecznie zaadaptował niektóre owoce tej pracy do swojego ostatecznego rozwiązania.
Badania wykazały, że w miarę jak plansze stają się większe i liczba hetmanów wzrasta, badania wykazały, że w większości dozwolonych konfiguracji hetmany mają tendencję do gromadzenia się wzdłuż boków planszy, z mniejszą liczbą hetmanów pośrodku, gdzie są atakowane. Ta wiedza pozwala na bardziej wyważone podejście.
Teoretycznie bardziej dokładna odpowiedź na zagadkę n-królowej powinna być możliwa – ale Simkin zbliżył nas do siebie niż kiedykolwiek i chętnie przekazuje wyzwanie komuś innemu do dalszych badań.
„Myślę, że osobiście przezwyciężyłem problem n-królowych przez jakiś czas, nie dlatego, że nie mam z tym nic wspólnego, ale po prostu dlatego, że marzyłem o szachach i jestem gotowy, aby kontynuować moje życie” Simkin mówi.
Rozwiązanie papierowe Simkin dostępne na serwerze prepress arXiv.
