Witam!
Poszukuję algorytmu do rozwiązywania gry piętnastka. Chodzi mi o schemat ort! pól z liczbami, który zapewniłby zawsze dojście do rozwiązania (liczby ustawione w kolejności od 1 do 15 od lewej do prawej od góry do dołu). Lub jakby ktoś jakiś algorytm znał.
Proszę - pomóżcie.
Istnieją takie ustawienia, z których nie da się dojść do pozycji startowej. Dość prosty dowód jest raczej popularny i łatwo go znaleźć.
Nie bardzo rozumiem istotę tej gry. Ale, ale...
Zapoznaj się z algorytmem 'skoczka szachowego' pewnie jest w stanie rozwiązać to zadanie.
lmmilewski - jeśli wylosujesz ustawienie to tak, ale jeśli dojdziesz do ustawienia przemieszanego prawidłowymi ruchami od pozycji posortowanej, to nie ma bata - da się wrócić.
To raczej oczywiste ;-). Wracając do problemu - proponuję zadać pytanie na forum opss - tam jest takie zadanie.
No tak. I właśnie dlatego na forum OPSS czy SPOJ nie uzyska odpowiedzi :P
Tam mogą dać mu co najwyżej kilka mało mówiących wskazówek.
kornelius napisał(a)
Witam!
Poszukuję algorytmu do rozwiązywania gry piętnastka. Chodzi mi o schemat ort! pól z liczbami, który zapewniłby zawsze dojście do rozwiązania (liczby ustawione w kolejności od 1 do 15 od lewej do prawej od góry do dołu). Lub jakby ktoś jakiś algorytm znał.
Proszę - pomóżcie.
Zobacz poniższy link:
Darek'u, co innego symulacja a co innego rozwiązanie.
Choć może nie wszyscy pamiętają zabawkę starszą o wiek od kostki Rubika (nie mylić z Rubikiem) :)
W każdej chwili możliwe są nie więcej niż 4 ruchy, łatwo chyba o rekurencyjne zapisanie tego? Takie "siłowe" rozwiązanie nie powinno zająć więcej niż naście linijek.
Chociaż, problem tak stary, że z pewnością od czasów Sama Lloyda doczekał się bogatej literatury, a wydaje mi się że nawet kilku samobójstw :D
na opss problem jest zupełnie inny, dotyczy tego czy z danego układu da się przejść do układu końcowego i w rozwiązaniu raczej nikt nie dba o to by próbować rzeczywiście symulować ruchy. Sprawdza się parzystość permutacji ;) siłowe-wykładnicze znajdowanie ścieżki będzie paskudnie wolne. Chętnie się dowiem jak to zrobić...