152-letni problem szachowy pokonany. Oto rozwiązanie zaproponowane przez matematyka

Michael Simkin związany z Uniwersytetem Harvarda twierdzi, że rozwiązał popularny problem szachowy, zwany problemem ośmiu hetmanów. To szczególnie imponujące, gdy weźmiemy pod uwagę fakt, iż jego historia sięga 1869 roku.

Problem ośmiu hetmanów, nazywany również problemem n-królowych, odnosi się do tradycyjnej szachownicy mającej rozmiary 8×8 pól. Wyzwaniem było w tym przypadku takie rozmieszczenie hetmanów, aby wzajemnie się nie atakowały.

Czytaj też: Nowa funkcja Microsoft Edge pomoże w rozwiązywaniu matematycznych równań

I choć wiadomo, że w przypadku szachownicy o rozmiarach 8×8 istnieją 92 takie możliwe do zrealizowania konfiguracje, to odrębną kwestią było to, na ile sposobów można ustawić n królowych na planszy o wymiarach n x n. Simkin wykazał, że w przypadku dużych szachownic z dużą liczbą królowych istnieje około (0.143n)n konfiguracji. W praktyce oznaczałoby to, że na na szachownicy o wymiarach 1 000 000 na 1 000 000 liczba sposobów na ułożenie królowych tak, aby wzajemnie się nie atakowały wynosi 1 i… około pięciu milionów zer.

Reklama

Problem szachowy zwany problemem n-królowych pochodzi z XIX wieku

Jedną z trudności w kontekście rozwiązania problemu n-królowych jest brak oczywistych sposobów na jego uproszczenie. Innymi słowy, nawet na pozornie niewielkiej szachownicy liczba możliwych konfiguracji może być ogromna. Co więcej, problem pochodzący z XIX wieku wydaje się nie posiadać jakiegokolwiek wzoru, który mógłby umożliwić jego „rozbicie” na części składowe.

Czytaj też: Procesor Kunlun II stworzony do obliczeń SI rzuci wyzwanie NVIDIA A100

Simkin był w stanie uzyskać końcowy rezultat poprzez śledzenie liczby przestrzeni, które nie były atakowane po określeniu pozycji każdej kolejnej królowej. Ta wartość niemal idealnie pasowała do minimalnej liczby, co pozwoliło sądzić, że matematyk jest bliski ustalenia rzeczywistej liczby konfiguracji n-królowych. Ważny jest przy tym fakt, że mając potencjalny wzór, Simkin – zamiast ustawiać królowe w kompletnie przypadkowy sposób – wybierał miejsca, w których znajdowało się ich więcej. Ostatecznie doprowadziło to do uzyskania dokładnego wyniku.