Znajdowanie ścieżek

Cześć, mam następujący problem

Rozważmy planszę rozmiaru m x n. Na takiej planszy zaznaczono pary punktów. Np. na planszy 3 x 3 możemy zaznaczyć następujące pary:

A = (1,3),(3,2)
B = (1,2),(3,1)

(orientacja jak w standardowym układzie współrzędnych)

W zadaniu chodzi o to, aby znaleźć ścieżki, łączące poszczególne punkty z danej pary. Przy czym takie ścieżki nie mogą się w żadnym punkcie przecinać, nachodzić na siebie, czy też nachodzić na punkty już zaznaczone na planszy. Dozwolone ruchy to góra,dół,prawo,lewo. W powyższym przykładzie, ścieżki mogą wyglądać np. tak:

A = (1,3) -> (2,3) -> (3,3) -> (3,2)
B = (1,2) -> (2,2) -> (2,1) -> (3,1)

(jeśli jest więcej rozwiązań, chciałbym aby były zwrócone wszystkie)

Ma ktoś pomysł jak się za to zabrać w haskellu?

Z tego co pamiętam (i o ile dobrze rozumiem treść zadania), problem jest NP-trudny.

Czyli nie ma co próbować się bawić z myśleniem nad wydajnymi (tzn. wielomianowymi) algorytmami. Zostaje pytanie jak bardzo wykładnicze może być rozwiązanie ;]. Jak duża plansza może być?

Trywialne rozwiązanie (bardzo) wykładnicze to:
Dla każdej ścieżki zaczynasz od punktu startowego, rekurencyjnie testujesz wszystkie pozycje dookoła aż dojdziesz do końca (tzn. sprawdzasz wszystkie możliwe ścieżki między tymi punktami). Jeśli się nie uda jakiejś ścieżki zamknąć, backtracking. I tak aż znajdziesz wszystkie możliwe ścieżki.

http://cs.brown.edu/research/pubs/pdfs/1996/Broder-1996-EAV.pdf