06.03.2018

Problem konika szachowego

Czy słyszeliście kiedyś o problemie konika szachowego? Otóż konik (lub inaczej skoczek) w kolejnych swoich ruchach chciałby odwiedzić wszystkie pola szachownicy dokładnie jeden raz. Czy jest to możliwe?

Czy istnieje rozwiązanie problemu konika szachowego?

Zagadnienie nazywane problemem konika szachowego, to jedno z zagadnień algorytmicznych, znane zapewne wszystkim studentom kierunków informatycznych. Dla szachownicy kwadratowej rozmiarach 3×3 pola oraz dla szachownicy o rozmiarach 4×4, zagadnienie to nie ma rozwiązania. Natomiast dla plansz kwadratowych o rozmiarach większych niż cztery pola, istnieją ścieżki otwarte dla konika szachowego. Ścieżka otwarta to taka ścieżka, w której po ostatnim ruchu konik nie może wrócić na pozycję startową. W ścieżce zamkniętej, po wykonaniu ostatniego ruchu, skoczek wraca na pole z którego rozpoczął.

Jak porusza się konik?

Dla przypomnienia podamy, że skoczek (konik) to figura szachowa, która porusza się dwa pola do przodu / do tyłu / w lewo / w prawo i jedno pole pod kątem prostym. Skoczek rozpoczyna ruch z pola czarnego a kończy na białym (lub odwrotnie). Plansza na której rozgrywana jest gra w szachy, nazywana jest szachownicą i ma kształt kwadratu o boku 8 pól. Łącznie na szachownicy są 64 pola czarne i białe ułożone na przemian.

Komentarze: (1)

  1. W tym zagadnieniu pewne sekwencje ruchów prowadzą do blokady, dlatego próbując poszczególne ruchy często trzeba wracać do poprzednich położeń i próbować iść innymi ścieżkami. To rekurencja 😉

    domino, Odpowiedz