Programy: Teoria Obliczeń i Złożoności Obliczeniowej (TOiZO)

Sokoban to, jak zapewne wiesz, bardzo stara gra, w której gracz ma pomóc magazynierowi ustawić pewną liczbę pudeł na odpowiednich miejscach w obrębie labiryntu korytarzy. Problem polega na tym, że pudełka można tylko pchać, a nie ciągnąć, więc dość łatwo je ustawić w takiej pozycji, że już nic się z nimi nie da zrobić. Grę możesz zobaczyć w akcji np. tutaj.

Celem projektu było napisanie takiego algorytmu, który automatycznie rozwiązywałby dowolną planszę Sokobana podaną na wejściu - i to w odpowiednio krótkim czasie. Mój algorytm bazuje na algorytmie zwanym A* (A-Star).