Witam Serdecznie!
Mam pewien problem donośnie idei na stworzenie algorytmu rozwiązującego grę Synapse.
Oto link do gry (jednej z jej wersji):
<url>http://www.fupa.com/play/Puzzles-free-games/synapse_v2.html </url>
Na wstępie chciałem zaznaczyć, że przeszukałem to forum jak i parę innych na których rozmowy oscylują wokół tego typu problemów. Google również nie dało żadnych rezultatów.
Problem jest następujący (w uproszczeniu, w rzeczywistości skala jest większa):
Dana jest plansza rozmiaru 5 x 5 pól (indeksowana x i y od 1 do 5)
Oraz znana liczba klocków następującego rodzaju:
A - klocek zakańczający
B - Rurka
C - Trójnik
D - Krzyż
E - Kolanko
Ponadto klocki w zależności od swojego ułożenia mają różne typy
A1 - klocek z zakończeniem w lewo
A2 - klocek z zakończeniem do góry
A3 - = // = w prawo
A4 - = // = w dół
B1 - rurka pozioma
B2 - rurka pionowa
C1.C2,C3,C4 - analogicznie jak A
D - krzyż niezależnie od położenia jest zawsze taki sam
E1.E2,E3,E4 - analogicznie jak A
Algorytm ma za zadanie ułożenie klocków na planszy w taki sposób żeby układ był "zamknięty" - czyli żeby żadne z zakończeń nie pozostawało wolne i zużyte zostały wszystkie elementy.
Algorytm na wejściu dostaje ilość i rodzaj klocków (nie typ), więc można je dowolnie obracać i umieszczać na planszy.
Przykładowe wejście
A,A,A,A,D
i wyjście dla tego przykładu
[2,1]A4
[1,2]A3
[2,2]D
[3,2]A1
[2,3]A2
Żeby wszystko maksymalnie uprościć zakładamy że dane na wejściu są zawsze prawidłowe i mają rozwiązanie.
Czego próbowałem:
-
Rekurencja - udało się stworzyć taki algorytm który działa ale tylko w wypadku kiedy jest to jeden obieg. Brutalnie tłumacząc - ułożone klocki mają kształt który dało by się narysować na kartce nie odrywając długopisu). W przypadku układu kiedy powstaje kwadrat z klocków E i B (kolanek i rurek) który w jednym miejscu ma zamiast klocka B klocek C (trójnik zamiast rurki) i zakończony jest klockiem A (zaślepką) rekurencja nie zwraca wyniku. Konkluzja rekurencyjnie powstaje linia po której "idzie" algorytm i jeżeli za którymś podejściem zejdzie się z początkiem (może się w międzyczasie krzyżować i przecinać) i przy okazji zużyje wszystkie elementy wtedy zwraca wynik. Natomiast w reszcie przypadków nie działa i ogólnie ma tragiczną złożoność obliczeniową.
-
Rozwiązanie ze stosem:
Po dodaniu elementu na planszę dorzucam na stos zakończenia tego klocka i jako następne pole wybieram pierwsze ze stosu itd. Tu jest znacznie więcej problemów. I bardzo rzadko algorytm jest w stanie coś z tego ułożyć.
Nie proszę o napisanie kodu ani nic takiego, tylko zwracam się z uprzejmą prośbą do szanownych kolegów i koleżanek, o pomoc w podsunięciu pomysłu na ugryzienie tego problemu. Przyznam się szczerze, że powoli kończą mi się pomysły i boje się że utknąłem w martwym punkcie. Mam nadzieję na jakiś świeży pomysł.
Pozdrawiam serdecznie i z góry dziękuję za każdą, ewentualną pomoc.
Z wyrazami szacunku
FLAq
ps.
pogrubienia według:
Arvin Vohra Education - Rapid Analytical Reading Announcement