Jak reprezentować Kostkę Rubika w strukturze danych

Jeśli próbuję symulować Kostkę Rubika , w jaki sposób stworzyłbyś strukturę danych do przechowywania stanu kostki w pamięci, z X liczbą płytek na stronę?

Rzeczy do rozważenia:

• kostka może mieć dowolny rozmiar
• jest to kostka Rubika, więc warstwy można obracać

Co jest złego w zwykłej starej tablicy rozmiarów [6X][X]? Nie musisz wiedzieć o wewnętrznych mini-kostkach, ponieważ ich nie widzisz; nie są częścią stanu kostki. Ukryj dwie brzydkie metody za ładnym i prostym w obsłudze interfejsem, przetestuj na śmierć na jednostce, i gotowe!

Należy zauważyć, że jestem zapaloną jednostką szybkości, ale nigdy nie próbowałem programowo reprezentować kostki Rubika w algorytmie lub strukturze danych.

Prawdopodobnie stworzyłbym osobne struktury danych, aby uchwycić unikalne aspekty każdego bloku w sześcianie.

Na kostce są 3 różne rodzaje bloków:

1. Blok narożny - ma trzy kolorowe ściany i trzy sąsiadujące ze sobą elementy, z którymi w dowolnej chwili będzie dzielił bok.

2. Blok krawędzi - ma dwie kolorowe ściany i 4 sąsiadujące ze sobą elementy, z którymi będzie dzielić bok w dowolnym momencie. W blokach 3x3 zawsze ma 2 elementy środkowe i 2 elementy narożne.

3. Blok centralny - w sześcianie 3x3 element ten nie jest ruchomy, ale można go obracać. Zawsze będzie mieć 4 sąsiadujące bloki krawędzi. W większych kostkach znajduje się wiele bloków środkowych, które mogłyby współdzielić z innym blokiem środkowym lub elementem krawędziowym. Bloki środkowe nigdy nie sąsiadują z blokiem narożnym.

Wiedząc o tym, Blok może mieć listę odniesień do innych bloków, których dotyka. Chciałbym zachować kolejną listę list, która byłaby listą bloków reprezentujących pojedynczą ścianę kostki i listę, która przechowuje odniesienia do każdej powierzchni kostki.

Każda twarz sześcianu byłaby reprezentowana jako unikalna twarz.

Przy tych strukturach danych byłoby dość łatwo napisać algorytm, który wykonuje transformację obrotu na każdej powierzchni, przenosząc odpowiednie bloki do odpowiednich list i z nich.

EDYCJA: Ważna uwaga, te listy należy oczywiście zamówić, ale zapomniałem o tym wspomnieć. Na przykład, jeśli odwrócę prawą stronę, wówczas blok lewego rogu po prawej stronie przesunie się do prawego rogu prawej strony i zostanie obrócony zgodnie z ruchem wskazówek zegara.

Kiedy myślę o tym problemie, myślę o statycznym sześcianie z kolorami poruszającymi się po nim w znanych wzorach. Więc....

Obiekt kostki zawiera 6 obiektów bocznych, które pozostają w stałym indeksie 0-5. Każda strona zawiera 9 obiektów pozycji, które pozostają na stałe indeksowane od 0 do 8. Każda pozycja zawiera kolor.

Dla uproszczenia wykonuj każdą akcję w krokach co ćwierć obrotu. Istnieją 3 osie obrotu, każda w 2 możliwych kierunkach, co daje w sumie 6 możliwych działań na sześcianie. Dzięki tym informacjom staje się dość prostym zadaniem mapowanie 6 możliwych działań na kostce.

Tak więc kolor zielony po stronie 6, pozycja 3, może przesunąć się między innymi na stronę 1 pozycję 3 lub stronę 2 pozycja 7, w zależności od podjętych działań. Nie zbadałem tego wystarczająco, aby znaleźć jakieś matematyczne tłumaczenia, ale prawdopodobnie pojawią się wzorce, które można wykorzystać w kodzie.

Używając struktury danych, skąd mam wiedzieć, czy dana kostka w pewnym stanie jest do rozwiązania? Sam zmagałem się z tym pytaniem i jeszcze nie znalazłem odpowiedzi.

Aby to zrobić, nigdy nie zaczynaj od losowego stanu kostki. Zamiast tego zacznij od stanu rozwiązanego i wykonaj n akcji programowo, aby ustawić kostkę w losowy stan początkowy. Ponieważ podjęto jedynie czynności prawne, aby uzyskać bieżący stan, kostka musi być rozwiązalna.

Odkryłem, że układ współrzędnych xyz jest prostym sposobem adresowania kostki Rubika, a matryce rotacyjne to prosty, ogólny sposób implementacji rotacji.

Utworzyłem klasę Piece zawierającą wektor pozycji (x, y, z). Kawałek można obracać, stosując macierz obrotu do jego położenia (mnożenie macierz-wektor). Piece śledzi również kolory w krotce (cx, cy, cz), nadając kolory skierowane wzdłuż każdej osi. Mała logika zapewnia, że ​​kolory te są odpowiednio aktualizowane podczas obrotu: obrót o 90 stopni w płaszczyźnie XY oznacza, że ​​zmienilibyśmy wartości cxi cy.

Ponieważ cała logika obrotu jest zawarta w klasie Kawałek, Kostka może przechowywać nieuporządkowaną listę Kawałków, a obroty można wykonywać w sposób ogólny. Aby wykonać obrót lewej powierzchni, zaznacz wszystkie elementy o współrzędnej x równej -1 i zastosuj odpowiednią macierz obrotu do każdego elementu. Aby wykonać obrót całego sześcianu, zastosuj tę samą macierz obrotu do każdego elementu.

Ta implementacja jest prosta i ma kilka drobiazgów:

1. Pozycja obiektu Piece zmieni się, ale jego kolory się nie zmienią. Oznacza to, że możesz poprosić o czerwono-zielony kawałek, zatrzymać się na obiekcie, wykonać kilka obrotów i sprawdzić ten sam obiekt, aby zobaczyć, gdzie skończył się czerwono-zielony kawałek.
2. Każdy typ elementu (krawędź, środek, narożnik) ma unikalny wzór współrzędnych. W przypadku sześcianu 3x3 element narożny nie ma zer w wektorze położenia ( (-1, 1, 1)), krawędź ma dokładnie jedno zero ( (1, 0, -1)), a element środkowy ma dwa zera ( (-1, 0, 0)).
3. Macierze obrotu działające dla kostki 3x3 będą działać dla kostki NxN.

Wady:

1. Mnożenie wektora macierzowego jest wolniejsze niż zamiana wartości w tablicach.
2. Wyszukiwanie w czasie liniowym kawałków według pozycji. Będziesz musiał przechowywać Kawałki w zewnętrznej strukturze danych i aktualizować je podczas rotacji w celu ciągłego wyszukiwania według pozycji. To niweczy elegancję korzystania z macierzy rotacji i przecieka logikę rotacji do twojej klasy Cube. Gdybym wdrażał jakiekolwiek rozwiązanie algo oparte na wyszukiwaniu, użyłbym innej implementacji.
3. Analiza wzorów (podczas rozwiązywania) nie jest tak przyjemna, jak mogłaby być. Kawałek nie ma wiedzy na temat sąsiednich elementów, a analiza byłaby powolna z powodu powyższych problemów z wydajnością.

możesz użyć prostej tablicy (każdy element ma mapowanie 1 do 1 na kwadrat na twarzy) i symulować każdy obrót z pewną permutacją

możesz uciec tylko 3 niezbędnymi kombinacjami: obróć plasterek z osią przez przednią powierzchnię, obróć sześcian wokół osi pionowej i obróć sześcian nad osią poziomą przez lewą i prawą ścianę. wszystkie pozostałe ruchy można wyrazić poprzez połączenie tych trzech elementów.

najprostszym sposobem sprawdzenia, czy sześcian jest do rozwiązania, jest jego rozwiązanie (znajdź serię permutacji, które rozwiążą sześcian), jeśli skończysz z 2 krawędziami, które zamieniły miejsce, pojedynczą przewróconą krawędzią, pojedynczym odwróconym rogiem lub 2 zamienione rogi masz nierozerwalną kostkę

Pierwszym warunkiem, który da się rozwiązać, jest obecność każdego elementu, a kolory na każdym elemencie mogą być użyte do złożenia sześcianu. Jest to względnie trywialny warunek, którego prawdę można ustalić za pomocą prostej listy kontrolnej. Schemat kolorów na „standardowej” kostce jest zdefiniowany , ale nawet jeśli nie masz do czynienia ze standardową kostką, jest ich tylko 6! możliwe kombinacje rozwiązanych twarzy.

Gdy wszystkie elementy i kolory są prawidłowe, kwestią jest ustalenie, czy dana konfiguracja fizyczna jest możliwa do rozwiązania. Nie wszystkie są. Najbardziej naiwnym sposobem sprawdzenia tego jest uruchomienie algorytmu rozwiązywania kostki i sprawdzenie, czy kończy się on rozwiązaną kostką. Nie wiem, czy istnieją fantazyjne techniki kombinatoryczne w celu ustalenia możliwości rozwiązania problemu bez próby rozwiązania kostki.

Co do struktury danych ... to prawie nie ma znaczenia. Trudność polega na prawidłowym przekształceniu i możliwości reprezentowania stanu kostki w sposób, który pozwala starannie pracować z dostępnymi algorytmami w literaturze. Jak wskazał trzon klonu, istnieją trzy rodzaje kawałków. Literatura na temat rozwiązywania kostek Rubika zawsze odnosi się do sztuk według ich rodzaju. Transformacje są również reprezentowane na wiele sposobów (patrz notacja Singmaster ). Ponadto wszystkie rozwiązania, które widziałem, zawsze odnoszą się do jednego elementu jako punktu odniesienia (zwykle umieszczając biały środkowy element na dole).

Ponieważ otrzymałeś już świetne odpowiedzi, pozwól mi dodać tylko szczegół.

Niezależnie od konkretnego przedstawienia, pamiętaj, że soczewki są bardzo dobrym narzędziem do „powiększania” różnych części sześcianu. Na przykład spójrz na funkcję cycleLeftw tym kodzie Haskell . Jest to funkcja ogólna, która cyklicznie dopuszcza dowolną listę długości 4. Kod do wykonania ruchu L wygląda następująco:

moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW

cycleLeftDziała zatem w oparciu o pogląd podany przez leftCols . Podobnie, rotateSideCWktóra jest funkcją ogólną opowiadającą się za jej obróconą wersją, działa w widoku podanym przez leftSide. Pozostałe ruchy można wykonać w podobny sposób.

Celem tej biblioteki Haskell jest tworzenie ładnych zdjęć. Myślę, że się udało:

Wygląda na to, że zadajesz dwa osobne pytania.

1. Jak przedstawić sześcian z liczbą X boków?

Jeśli zamierzasz symulować prawdziwą kostkę Rubika, wszystkie kostki Rubika mają 6 boków. Myślę, że masz na myśli „liczbę X płytek na wymiar na stronę”. Każda strona oryginalnej kostki Rubika ma wymiary 3 x 3. Inne rozmiary to 4x4 (kostka profesora), 5x5 i 6x6.

Przedstawiłbym dane z 6 stron, używając „standardowej” notacji rozwiązywania kostki:

• PRZÓD: twarz zwrócona w stronę solvera
• PLECY
• DOBRZE
• LEWO
• W GÓRĘ
• NA DÓŁ

Każda strona to dwuwymiarowa tablica X na X.

Podoba mi się pomysł @maple_shaft, aby inaczej reprezentować różne elementy (mini-kostki): elementy środkowe, krawędziowe i narożne mają odpowiednio 1, 2 lub 3 kolory.

Przedstawiłbym relacje między nimi jako (dwukierunkowy) wykres z krawędziami łączącymi sąsiednie elementy. Każdy element będzie miał szereg szczelin na krawędzie (połączenia): 4 szczeliny w środkowych częściach, 4 szczeliny w krawędziach, 3 szczeliny w narożnikach. Alternatywnie, elementy środkowe mogą mieć 4 połączenia z elementami krawędziowymi i 4 oddzielnie dla elementów narożnych i / lub elementy krawędziowe mogą mieć 2 połączenia z elementami środkowymi i 2 oddzielnie dla elementów narożnych.

Te tablice są uporządkowane w taki sposób, że iteracja po krawędziach wykresu zawsze reprezentuje „ten sam” obrót, modulo obrót sześcianu. To jest, np. Dla elementu centralnego, jeśli obrócisz sześcian tak, aby jego powierzchnia znajdowała się na górze, kolejność połączeń jest zawsze zgodna z ruchem wskazówek zegara. Podobnie w przypadku elementów krawędziowych i narożnych. Ta właściwość zachowuje się po obrotach twarzy (a przynajmniej tak mi się teraz wydaje).

• Znalezienie elementów należących do krawędzi jest banalne.
• Znalezienie elementów należących do twarzy jest banalne.
• Znalezienie twarzy skierowanych w danym kierunku do danej twarzy lub twarzy przeciwnej to przemieszczenie 2 lub 3 dobrze zdefiniowanych połączeń.
• Aby obrócić twarz, zaktualizuj połączenia wszystkich elementów połączonych z centralnym elementem twarzy.

Wykrywanie wyraźnie nierozwiązywalnych warunków (zamienione / odwrócone krawędzie, zamienione narożniki) jest również, miejmy nadzieję, łatwe, ponieważ znalezienie elementów określonego typu i ich orientacji jest proste.

A co z węzłami i wskaźnikami?

Zakładając, że zawsze jest 6 twarzy, a ten 1 węzeł reprezentuje 1 kwadrat na 1 twarzy:

r , g , b
r , g , b
r , g , b
|   |   |
r , g , b - r , g , b
r , g , b - r , g , b
r , g , b - r , g , b

Węzeł ma wskaźnik do każdego węzła obok niego. Obrót koła migruje wskaźnik (Liczba węzłów / Liczba ścian) -1 węzłów, w tym przypadku 2. Ponieważ wszystkie obroty są obrotami kół, wystarczy zbudować jedną rotatefunkcję. Jest rekurencyjny, przesuwając każdy węzeł o jedno miejsce i sprawdzając, czy przesunął je wystarczająco, ponieważ zgromadzi liczbę węzłów i zawsze są cztery twarze. Jeśli nie, zwiększ liczbę przeniesionych wartości i ponownie obróć połączenie.

Nie zapomnij, że jest podwójnie powiązany, więc zaktualizuj również nowo wskazane węzły. Zawsze będzie się przesuwać Wysokość * Szerokość liczby węzłów, z jednym wskaźnikiem aktualizowanym na węzeł, więc powinna być zaktualizowana Wysokość * Szerokość * 2 liczba wskaźników.

Ponieważ wszystkie węzły wskazują na siebie, po prostu chodź w kółko, aktualizując każdy węzeł, gdy do niego dojdziesz.

Powinno to działać dla dowolnej wielkości kostki, bez przypadków krawędziowych i skomplikowanej logiki. To tylko wskaźnik chodzenia / aktualizacji.

Z osobistego doświadczenia korzystanie z zestawu do śledzenia każdej obrotowej części sześcianu działa dobrze. Każda pod kostka jest w trzech zestawach bez względu na rozmiar kostki rubika. Aby więc znaleźć pod kostkę gdzieś na kostce rubika, po prostu weź przecięcie trzech zestawów (wynikiem jest jedna pod kostka). Aby wykonać ruch, usuń wpływające podrzędne z zestawów uczestniczących w ruchu, a następnie umieść je z powrotem w zestawach, które zabiorą je w wyniku ruchu.

Kostka 4 na 4 będzie miała 12 zestawów. 6 zestawów dla 6 ścian i 6 zestawów dla sześciu pasm otaczających sześcian. Każda z powierzchni ma 16 sub-kostek, a każda z pasm ma 12 sub-kostek. Istnieje w sumie 56 pod kostek. Każda pod kostka zawiera informacje o kolorze i kierunku kolorów. Sama kostka rubika jest tablicą 4 na 4 na 4, a każdy element zawiera informacje składające się z 3 zestawów, które definiują pod kostkę w tym miejscu.

W przeciwieństwie do pozostałych 11 odpowiedzi, ta struktura danych wykorzystuje skrzyżowanie zestawów do zdefiniowania położenia każdego podbloku w kostce. To oszczędza pracy związanej z koniecznością aktualizowania bliskich podbloków po wprowadzeniu zmiany.