konto usunięte
Temat: ukladanka z klockow
Dostałem niedawno układankę(http://www.knobelholz.de/index.php?page=shop.product_d.... 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ł ?