Permutation Puzzle Swap Cubies
Niedawno uruchomiłem układankę online RAVEL . To trójwymiarowa tablica kostek, które należy ułożyć w kolejności kolorów. Prawnym posunięciem jest przesunięcie rzędu, kolumny lub pasa o dowolną liczbę spacji. Kostki, które są wypychane z końca, są wkładane na drugim końcu.
Proponuję odwiedzić RAVEL , kliknąć zakładkę „Experimenter” i wypróbować kilka RAVELÓW o różnych wymiarach, aby lepiej docenić to, co następuje.
Przypuszczam, że wszystkie permutacje można rozwiązać, ale ponieważ nie wiem na pewno, tasuję RAVEL serią przypadkowych legalnych ruchów.
Pytanie pierwsze:
Czy konieczne jest tasowanie z legalnymi ruchami? A może mógłbym po prostu potasować to z przypadkowymi zamianami i nadal można to rozwiązać? Innymi słowy: czy to przypuszczenie jest prawdziwe, czy wszystkie permutacje można rozwiązać?
Moje drugie pytanie dotyczy technik rozwiązywania. Rozwiązuję RAVELy warstwa po warstwie, używając metod ad hoc, aby przenieść kostki na miejsce bez zmiany pozycji już umieszczonych. Ale w ostatniej warstwie używam sformalizowanych metod dla ostatnich kilku kostek.
Algorytm cyklu 3
Ten algorytm zmienia pozycje trzech kostek, pozostawiając wszystkie pozostałe kostki na miejscu. Przestrzeń między trzema sześcianami nie ma znaczenia, o ile tworzą kąt prosty: kostki 1 i 2 w tym samym rzędzie, kostki 2 i 3 w tej samej kolumnie.
Algorytm:
- Przeciągnij zielony sześcian do wierzchołka (pozycja niebieska).
- Przeciągnij czerwoną do pozycji wierzchołka.
- Przeciągnij wierzchołek do miejsca, w którym zaczyna się zielony.
- Przeciągnij wierzchołek do miejsca, w którym zaczął się czerwony.
Liczby na obrazku pokazują sekwencję ruchów. Aby jechać w przeciwnym kierunku, zmień 1 na 2, a przełącznik 3 na 4.
Zamień dwa kostki
Często możesz zakończyć rozwiązywanie RAVEL, używając tylko powyższych procedur. Ale czasami pozostają pary zamienionych kostek. Nie znam ogólnego algorytmu zamiany par, który działa dla wszystkich rozmiarów RAVEL. Udało mi się rozwiązać kilka przykładów, po prostu machając rękami, próbując wszystkiego.
Znalazłem procedurę zamiany par na RAVEL, gdzie jeden z wymiarów jest równy 4.
Rysunek przedstawia sekwencję ruchów, aby zamienić kostkę czerwoną i zieloną. Wymiar pionowy musi wynosić cztery.
Pytanie drugie:
Czy potrafisz stworzyć algorytm wymiany par, który będzie działał dla wszystkich rozmiarów RAVEL?
☺ ☺ ☺
Odpowiedzi
Ta łamigłówka to trójwymiarowa wersja tej układanki, która jest dostępna w kolekcji puzzli Simona Tathama pod nazwą Sixteen . Ta łamigłówka była już wcześniej omawiana: Techniki rozwiązywania łamigłówek przesuwających się po rzędach
Tutaj odpowiedź ma również zastosowanie, więc nie będę wchodził w szczegóły.
Pytanie 1:
Każda permutacja z równą parzystością jest możliwa i łatwa do rozwiązania przy użyciu 3 cykli. Jeśli wszystkie wymiary są nieparzyste, to każdy ruch jest permutacją parzystą, więc nie są możliwe żadne dziwne permutacje. W szczególności żadna pojedyncza zamiana nie jest w tym przypadku możliwa. Jeśli przynajmniej jeden wymiar jest parzysty, dostępne są również nieparzyste permutacje, więc wszystkie permutacje można rozwiązać.
Pytanie 2:
Jeśli jeden lub więcej wymiarów jest parzystych, to przesunięcie wzdłuż takiego wymiaru jest dziwną permutacją. Dlatego możesz zrobić takie przesunięcie i rozwiązać większość przesuniętych elementów za pomocą 3 cykli i zostać z pojedynczą zamianą.
Załóżmy, że A to ruch, który przesuwa wiersz zawierający$2n$ bloków, B jest przesunięciem przecinającej się linii bloków, a B 'jest odwrotnością B. Następnie sekwencja ruchu BAB'A powtórzona $n-1$ razy, po których nastąpi BAAB'A, spowoduje zamianę dwóch sąsiednich bloków w linii A.