Zimne Piwnice to jedno z zadań na Obozie Naukowo-Treningowym im. Antoniego Kreczmara
w roku 2013. Mamy labirynt 20x15, w którym jest 6 skarbów i strażnik. Bajtur
i strażnik na przemian wykonują ruchy w 8 kierunkach, przy czym strażnik zawsze
rusza się tak, żeby zminimalizować euklidesową odległość od poszukiwacza (w przypadku
remisu stoi w miejscu). Oficjalnym zadaniem algorytmicznym było napisanie programu,
który dla danej planszy (w formacie ASCII) określi, ile ruchów Bajtur potrzebuje, by zebrać największą
możliwą liczbę skarbów i uciec z labiryntu. Dodatkowy konkurs polegał na tym, by stworzyć
taką planszę, na której
Bajtur będzie musiał wykonać jak największą liczbę ruchów.
Na tej stronie możesz wpisać własny labirynt i zobaczyć, jak Bajtur ucieka w nim przed
strażnikiem. Pokazana jest najkrótsza możliwa trasa Bajtura (wśród takich, które
zdobywają największą możliwą liczbę skarbów). Zachęcam do obejrzenia
labiryntu, w którym potrzeba 1115 ruchów i spróbowania
wymyślenia czegoś lepszego (jest możliwe ręczne wymyślenie czegoś lepszego).
Zamierzam co jakiś czas patrzeć na wysyłane labirynty, także jak zobaczę coś ciekawego,
to dodam do sekcji "rozwiązania" poniżej (można się podpisać pod labiryntem).
W sierpniu 2015 Tomek Czajka znalazł
dużo lepsze rozwiązanie (4888 ruchów).
Rozwiązanie zostało znalezione przy użyciu symulowanego wyżarzania (Simulated Annealing).