Losowanie pola enum

Witam!

Robię aktualnie generator labiryntu. Cały algorytm działa na zasadzie:

Dopóki są wolne miejsca w tablicy:
1. Wylosuj kierunek
2. Jeśli pole nie zostało odwiedzone, to przejdź tam i włóż na stos współrzędne
3. Jeśli nie ma możliwości ruchu (pola na lewo, prawo, z góry i z dołu były już odwiedzone) to zdejmij ze stosu poprzednią pozycje


Ogólnie algorytm działa dobrze, jednak mam pewien problem, a mianowicie zastanawiam się jak najlepiej zoptymalizować losowanie kierunku. Aktualnie losuję pole z enum odpowiadające konkretnemu kierunkowi.
Problem polega na tym, że gdy zostaje np możliwość ruchu tylko w jednym kierunku, to często algorytm losuje kilkukrotnie kierunki w których nie może się poruszać, na przykład:

[ ]( )[ ]
[ ]( )[ ]
[ ]( )[ ]
[ ][*][ ]
[ ][ ][ ]

( ) - pola, które nie zostały odwiedzone
[ ] - pola odwiedzone
[*] - pole w którym "znajduje się" algorytm

Jedyny możliwy ruch jest w górę, ale algorytm ma tylko 25% szans na trafienie za pierwszym razem w poprawny kierunek.

Pytania są następujące
1. Czy jest sens usprawniania tego? dla tablicy 10x10 pętla wykonuje się około 250 razy, dla 12x12 około 350 razy, 20x20 ok 950
2. Czy da się to zrobić inaczej niż siłowo sprawdzać jakie są możliwości?

Odpowiedzi na pytania:
1. Aktualnie komputery mają już taką moc obliczeniową, że jeżeli nie potrzebujesz generować ogromnych labiryntów, to nie zauważysz różnicy w czasie. Zresztą z danych, które podałeś można wyliczyć, że czas jest tym lepszy im większy ma być labirynt.
2. Istnieją różne algorytmy stworzone do rozwiązywania problemu który rozważasz. Powiem to tak - nie znam się na nich ale podejrzewam, że metoda siłowa jest wśród nich najpowszechniejsza, ale tutaj i tak wracam do tego o czym już wspomniałem - mocy obliczeniowej masz prawdopodobnie pod dostatkiem do takich obliczeń.

EDIT: Sam osobiście jestem zwolennikiem maksymalnej optymalizacji niezależnie od widoczności efektów. Jeżeli chcesz to zrobić, to dlaczego nie - zawsze jakąś naukę z tego wyniesiesz.

Protip algorytm A* i jego wariacje/optymalizacje, w tym kierunku bym szukał odpowiedzi na twoje pytania.