Matematyk z Harvardu rozwiązał epicki problem szachowy sprzed 150 lat

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)ⁿ 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.