Algorytm znajdujący rozwiązanie gry Synapse (vel Hydraulik)

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:

1. 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ą.

2. 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

Ja bym chyba sprobowal rekurencyjnie bez układania klockow w konkretnym miejscu planszy - sprawdzajac tylko czy uklad sie zmiesci, bez zastanawiania sie gdzie dokladnie maja byc ani w ktora strone to wszystko ma byc obrocone(tym mozna sie zajac na koncu). Powinno to znacznie przyspieszyc dzialanie algorytmu. Dodatkowo wprowadz zmienna ktora jest zwiekszana za kazdym razem gdy powstaje rozejscie(zostal uzyty trojnik albo krzyz) i to rozejscie nie trafia w juz istniejace rozejscie i oczywiscie jest zmniejszana jak "likwidujemy" rozejscie. Przed powrotem sprawdzaj czy na pewno (liczba rozejsc==0 i liczba pozostalych klockow==0). Oprocz tego ukladanie proponuje zaczynac od klocka z najmniejsza liczba rozejsc(wydaje mi sie, ze tak bedzie najszybciej.... wydaje, ale glowy za to nie dam).
Moze jakies bardzo odkrywcze i innowacyjne to co napisalem nie jest(pewnie na czesc z tych rozwiazan juz wczensiej wpadles), ale powinno dosc znaczaco przyspieszyc algorytm. Mam nadzieje, ze chociaz troche pomoglem :)
Napisz cos wiecej o 2 podejsciu(ze stosem), bo prawde mowiac nie zrozumialem co miales na mysli.

Co do tej rekurencji to tylko tak pobieżnie napisałem w praktyce to trochę bardziej złożone. Zrobiłem hashmape możliwych kierunków z danego elementu na boolach i w ogóle wiele różnych usprawnień ale jak już pisałem wyżej rekurencyjnie da się ułożyć coś co nie jest rozgałęzione tylko stanowi jeden obwód.

Co do stosu (lub kolejki):
Biorę jakiś (losowy, pierwszy, pierwszy po posortowaniu - to trzeba jeszcze ustalić) element i układam go na planszy. Powiedzmy że jest to element D w polu [2,2]. Z elementu D są cztery wyjścia więc na stos (do kolejki) dorzucam pola (współrzędne, wskaźniki - nieważne) [2,1], [3,2], [2,3], [1,2]. Ściągam ze element i tam dodaje następny klocek (jeżeli pasuje lub jeżeli pasuje po obróceniu), jeśli nie to biorę kolejny klocek aż jakiegoś nie wstawię, potem dorzucam na stos jego wyjścia. Czyli np. w polu [2,1] postawiłem klocek E1 więc do stosu dorzucam [3,1]. Przesuwając się na kolejne pola ściągane ze stosu sprawdzam ilość wystąpień tego pola na stosie. Jeżeli są dwa czy trzy czy cztery to wiadomo od razu jaki klocek należy tam wstawić. Ale i tak ma to pewne wady.

Jesli nadal potrzebujesz pomocy to moge sie podzielic kodem zrodlowym programu, ktory rozwiazuje ta zagadke lecz z jedna roznica taka, ze klocki sa juz ulozone na planszy trzeba je jedynie obracac. Kod jest napisany w haskellu jesli ci to nie przeszkadza

@up: zdecydowanie on już zrobił znacznie więcej niż, ty. Ty masz tak uproszczony problem, że wręcz trywialny.

@topic: ta twoja rekurencja powinna być ok. Jedynie musisz ją usprawnić. Najlepiej wprowadź zapamiętywanie analizowanych układów. W przypadku, gdy dany układ był wcześniej analizowany przerywasz rekurencję. Cały cymes kryje się w porównaniu układów w taki sprytny sposób by było to szybkie (hashowanie się przyda) uwzględniało symetrię (obroty i odbicia) i nie zżerało za dużo pamięci.