Prolog - ukladanka z klockow

Dostałem niedawno układankę(http://www.knobelholz.de/index.php?page=shop.product_details&flypage=shop.flypage&product_id=45&category_id=8&manufacturer_id=0&option=com_virtuemart&Itemid=26&vmcchk=1&Itemid=26). Wygląda to tak, że mamy 25 klocków o kształcie o długości 4 jednostek + jeden wystający kawałek z boku. Klocki te trzeba złożyć w kostkę o wymiarach 5 x 5 x 5.

Moje podejście było takie, Każdy klocek może wystąpić w przestrzeni w jednym z 24 układów, zrobiłem sobie z tego macierz, i do każdej pozycji w kostce układałem wszystkie możliwości(odrzucając te, które wystawały poza świat). W efekcie dostałem kostkę, która zawiera kilkaset kolidujących klocków. Każdy klocek zajmuje 5 punktów w przestrzeni. Czyli dla każdego punktu mam stos punktów od poszczególnych klocków. Żeby uzyskać rozwiązanie, ściągam z każdego stosu większego od 1, pierwszy z brzegu klocek, usuwając też jego wystąpienie na innych stosach. Jak na którymś stosie zostanie 0 elementów, to odkładam klocka i biorę następnego. Powtarzam to, aż dostanę stosy jednoelementowe.

Wydaje mi się, ze podejście poprawne(testowałem na mniejszych danych) ale zbyt złożone, Atom 1.6 ghz rozwiązuje to już od 193H :) Ma ktoś jakiś lepszy pomysł ?

Mógłbyś opisać dokładniej tą kostkę? Nigdy takiej nie widziałem, a na stronie nie ma żadnego opisu.

Z tego co zrozumiałem, jest tak:
5 * klocek o długości 5:

/\/\/\/\/\
\/\/\/\/\/

1* klocek wyjątkowy:

/\/\/\/\/\
\/\//\\/\/
    \/

i zadanie polega na ułożeniu kostki 5x5x5?

każdy klocek wygląda mniej więcej tak:

 
 x
xxxx

typowy algorytm sprawdzający wszystkie układy w tym przypadku się nie sprawdza, bo jest ich po prostu za dużo. Potrzebuję pomysłu na jakąś konkretną optymalizację...

Osobie, która nie posiada takiej zabawki trochę ciężko wymyśleć dobrą strategię układania. Jeśli chodzi o tego typu problemy to na podstawie dotychczasowych przygód z Prologiem mogę ci dać następujące rady:

1. Dobrze jest rozwiązywać łamigłówkę w jakimś dobrym porządku, chaos zazwyczaj nie popłacał, w twoim przypadku spróbowałbym układać klocki "warstwowo" od podstawy w góre tj. najpierw ustalasz klocki mające koniec w punktach na wys. 1, nasptępnie jeśli udało się, to przechodzisz do punktów na wys. 2 i tak dalej. (być może tak właśnie robisz, nie do końca zrozumiałem twój algorytm:) ). W ten sposób stopniowo masz wypełniony coraz wyższy prostopadłościan i intuicyjnie szybciej powinieneś wykrywać problemy.

2. Dobrze jest nawracać jak najwcześniej, tzn. lepiej w każdym kroku wykonać jakieś dodatkowe obliczenia i nawrócić niż czegoś nie zauważyć i przeszukiwać niepotrzebnie całe poddrzewo stanów . Możesz spróbować po wstawieniu klocka badać czy nie powstały jakieś puste przestrzenie zamknięte przez inne klocki tzn. takie do których na pewno nic nie wciśniesz (wystarczy ci liczba punktów takiego obszaru, jeśli jest niepodzielna przez 5 to nawracamy). Można takie sprawdzenie wykonać szybko, powienien wystarczyć jakiś dfs czy coś w ten deseń, na każdy krok backtrackingu.

Nie napisałeś czy szukasz pierwszego lepszego rozwiązania czy wszystkich, jeśli wszystkich to wiedz że może być ich b. b. dużo i siłą rzeczy obliczenia trwają tydzień.

to moje podejscie jest wlasnie mniej wiecej takie, sprawdzalem 2 algorytmy, pierwszy polegal na wypelnianiu kolejnych pol i sprawdzal po kazdym dolozeniu czy ten wybor nie 'blokuje' ktoregos pola, drugi algorytm to wygenerowanie wszystkich mozliwosci i usuwanie nadmiarowych. niestety oba te rozwiazania maja zbyt duza zlozonosc obliczeniowa.
ponizej jeden z moich algorytmow(ten z usuwaniem nadmiarowych klockow):

 main:-
	write('Wyznaczam klocki...'),nl,
	wyznaczKlocki(LK),
	write('Ukladam stosy...'),nl,
	wyznaczStosy(LK, LS),
	write('Usuwam nadmiar...'),nl,
	usunNadmiar(LS, W),
	write('Wypisuje wynik...'),nl,
	wypisz(W).

usunNadmiar(LS, W):-
	wybierzStos(LS, S),
	!,
	wybierzKlocka(S, K),
	usunKlocka(LS, K, LS1),
	usunNadmiar(LS1, W).
usunNadmiar(LS, LS).

wybierzStos(LS, S):-
	wybierzStos(LS, [], S).
wybierzStos([(_, H)|_], _, H):-
	length(H, I),
	I > 1,
	!.
wybierzStos([_|T], L, W):-
	wybierzStos(T, L, W).

wybierzKlocka([H|_], H).
wybierzKlocka([_|T], K):-
	wybierzKlocka(T, K).

usunKlocka(LS, K, W):-
	usunKlocka(LS, K, [], W).
usunKlocka([], _, W, W).
usunKlocka([(P, L)|T], K, LS, W):-
	delete(L, K, L1),
	length(L1, I),
	I > 0,
	usunKlocka(T, K, [(P, L1)|LS], W).

wyznaczStosy(LK, LS):-
	wyznaczPusteStosy(PLS),
	wyznaczStosy(LK, PLS, LS).

wyznaczStosy([], LS, LS):-!.
wyznaczStosy([K|T], PLS, LS):-
	dodajKlocka(K, PLS, PLS1),
	wyznaczStosy(T, PLS1, LS).

dodajKlocka((_, []), PLS, PLS):-!.
dodajKlocka((ID, [H|T]), PLS, W):-
	    dopisz(ID, H, PLS, PLS1),
	    dodajKlocka((ID, T), PLS1, W).

dopisz(ID, H, PLS, W):-
	dopisz(ID, H, PLS, [], W).
dopisz(_, _, [], W, W):-!.
dopisz(ID, P1, [(P2, L)|T], PLS, W):-
	P1 == P2,
	!,
	dopisz(ID, P1, T, [(P1, [ID|L])|PLS], W).
dopisz(ID, P, [H|T], PLS, W):-
	dopisz(ID, P, T, [H|PLS], W).

wyznaczPusteStosy(PLS):-
	wyznaczPusteStosy((0, 0, 0), [], PLS).
wyznaczPusteStosy((4, 4, 4), PLS, PLS):-!.
wyznaczPusteStosy(P, PLS, W):-
	zwieksz(P, P1),
	wyznaczPusteStosy(P1, [(P, [])|PLS], W).

wyznaczKlocki(LK):-
	wyznaczKlocki([], (0, 0, 0), 0, LK).
wyznaczKlocki(LK, (4, 4, 4), _, LK):-!.
wyznaczKlocki(LK, P, I, W):-
	mozliwosci(M),
	wyznaczNaPozycji(M, P, I, [], Ky),
	zwieksz(P, P1),
	length(Ky, L),
	I1 is I + L,
	append(Ky, LK, LK1),
	wyznaczKlocki(LK1, P1, I1, W).

wyznaczNaPozycji([], _, _, W, W):-!.
wyznaczNaPozycji([M|T], P, I, Ky, W):-
	generuj(M, P, I, K),
	!,
	I1 is I + 1,
	wyznaczNaPozycji(T, P, I1, [K|Ky], W).
wyznaczNaPozycji([_|T], P, I, Ky, W):-
	wyznaczNaPozycji(T, P, I, Ky, W).

generuj([(X1, Y1, Z1), (X2, Y2, Z2), (X3, Y3, Z3), (X4, Y4, Z4), (X5, Y5, Z5)], (Xp, Yp, Zp), I, W):-
	Xm1 is X1 + Xp, Xm1 < 5, Xm1 >= 0,	Ym1 is Y1 + Yp, Ym1 < 5, Ym1 >= 0,	Zm1 is Z1 + Zp, Zm1 < 5, Zm1 >= 0,
	Xm2 is X2 + Xp, Xm2 < 5, Xm2 >= 0,	Ym2 is Y2 + Yp, Ym2 < 5, Ym2 >= 0,	Zm2 is Z2 + Zp, Zm2 < 5, Zm2 >= 0,
	Xm3 is X3 + Xp, Xm3 < 5, Xm3 >= 0,	Ym3 is Y3 + Yp, Ym3 < 5, Ym3 >= 0,	Zm3 is Z3 + Zp, Zm3 < 5, Zm3 >= 0,
	Xm4 is X4 + Xp, Xm4 < 5, Xm4 >= 0,	Ym4 is Y4 + Yp, Ym4 < 5, Ym4 >= 0,	Zm4 is Z4 + Zp, Zm4 < 5, Zm4 >= 0,
	Xm5 is X5 + Xp, Xm5 < 5, Xm5 >= 0,	Ym5 is Y5 + Yp, Ym5 < 5, Ym5 >= 0,	Zm5 is Z5 + Zp, Zm5 < 5, Zm5 >= 0,
	W = (I, [(Xm1, Ym1, Zm1), (Xm2, Ym2, Zm2), (Xm3, Ym3, Zm3), (Xm4, Ym4, Zm4), (Xm5, Ym5, Zm5)]).

zwieksz((4, Y, 4), (0, Y1, 0)):-Y1 is Y + 1,!.
zwieksz((4, Y, Z), (0, Y, Z1)):-Z1 is Z + 1,!.
zwieksz((X, Y, Z), (X1, Y, Z)):-X1 is X + 1,!.

mozliwosci([[(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (2, 0, 1)],
	    [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (2, 1, 0)],
	    [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (2, -1, 0)],
	    [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (2, 0, -1)],
	    %
	    [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (1, 0, 1)],
	    [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (1, 1, 0)],
	    [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (1, -1, 0)],
	    [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (1, 0, -1)],
	    %%%
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 2)],
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (1, 0, 2)],
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, -1, 2)],
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (-1, 0, 2)],
	    %
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 1)],
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (1, 0, 1)],
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, -1, 1)],
	    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (-1, 0, 1)],
	    %%%
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (0, 2, 1)],
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (1, 2, 0)],
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (0, 2, -1)],
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (-1, 2, 0)],
	    %
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (0, 1, 1)],
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (1, 1, 0)],
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (0, 1, -1)],
	    [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 0), (-1, 1, 0)]]).


wypisz(L):-
	wypisz(0, L).

wypisz(_, []):-!.
wypisz(I, [H|T]):-
	write(I),write(': '),write(H),nl,
	I1 is I + 1,
	wypisz(I1, T).