Jak reprezentować Kostkę Rubika w strukturze danych

58

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ć
Mel
źródło
2
Zadanie domowe? Albo problem w świecie rzeczywistym ...
sdg
4
Możesz być zainteresowany kodem źródłowym tego Solvera Cube Rubika .
mouviciel
22
Jestem prawie pewien, że liczba boków sześcianu powinna wynosić 6
Simon Bergot
3
Byłbym ciekawy, gdyby model Kostki Rubika spłaszczył się, dzięki czemu mogłem widzieć wszystkie boki jednocześnie. Hmm, mam ochotę to teraz napisać. Może to być kształt litery T lub nawet bez końca kafelki, jeśli to możliwe (nie pomyślałem tego drugiego).
Lee Kowalkowski
6
Czuję pokusę, by zacytować Erica Evansa: „Modele nie są ani dobre, ani złe. Są po prostu mniej lub bardziej przydatne” (cytat prawdopodobnie nie w 100% poprawny, jak cytowano z pamięci)
Pete

Odpowiedzi:

37

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!

dasblinkenlight
źródło
31
nawet prawdziwa kostka Rubika nie ma żadnych wewnętrznych mini-kostek
jk.
8
To zadziała, ale twój algorytm będzie prawdopodobnie niezwykle skomplikowany, aby pomieścić tak prostą strukturę danych.
wałek klonowy
6
As long as you know how the six surfaces are "threaded" together Właśnie to da ci bardziej solidna struktura danych. Myślę, że walczymy o to samo. Boki tablicy, a strona jest tablicą bloków, jednak istnieje wiele interesujących właściwości boków i bloków, które pomagają odkryć, że „wątki” Nie podoba mi się ten termin, ponieważ można go pomylić z wielowątkowością; )
wałek klonowy
7
@maple_shaft "Właśnie to daje ci bardziej solidna struktura danych." Nie wiem o tym: struktura danych z większą „strukturą” niekoniecznie spowodowałaby dodatkową przypadkową złożoność związaną z konfigurowaniem, utrzymywaniem i dostępem do poszczególnych części tej struktury. Trudno powiedzieć, co byłoby bardziej skomplikowane - wdrożenie brzydkich zmian na zwykłej tablicy z niektórymi skrzynkowymi narożnikami plus „swobodna jazda” przy dostępie do poszczególnych komórek lub struktura z nieco mniej złożonymi zmianami i nieco bardziej złożonymi odczytami.
dasblinkenlight
16
Jako ktoś, kto napisał programy do manipulowania kostką Rubika, podjąłem proste podejście polegające na użyciu sześciu dwuwymiarowych tablic, po jednej na twarz. To prawda, że ​​musisz wprowadzić pewne podstawowe operacje na kostce, które są trochę denerwujące, ale potem możesz zapomnieć o reprezentacji. To nigdy nie było dla mnie problemem. Często zastanawiałem się, jak działałyby inne reprezentacje z perspektywy wydajności, ale nigdy nie czułem się obciążony z punktu widzenia kodowania.
PeterAllenWebb
39

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.

wałek klonowy
źródło
zgadzają się, że każdy blok musiałby mieć unikalne właściwości. ale transformacja nie byłaby nużąca, ponieważ musisz zaktualizować odniesienia do sąsiednich bloków i twojego list of lists. może lepiej mieć po prostu nieuporządkowaną listę bloków, które możesz zapytać. i po prostu aktualizujesz sąsiednie odniesienia do bloku podczas wykonywania transformacji. Jeśli chcesz listę wszystkich bloków na powierzchni, możesz zapytać o listę wszystkich sąsiadujących bloków z blokami środkowymi, prawda?
Mel
@Mel Można to zrobić w obu kierunkach, ale po rozmowie z dasblinkenlight uważam, że jego podejście byłoby mniej skomplikowane. Chciałbym, aby jego odpowiedź miała więcej głosów niż moja. Nie jestem aż tak dobry z algorytmami i najbardziej wydajnym, po prostu bardzo lubię kostki rubika i zbieram je (ponad 40 różnych rodzajów z całego świata).
wałek klonowy
Chociaż odpowiedź dasblinknenlight jest najprostszym rozwiązaniem, nagradzam cię nagrodą, ponieważ podoba mi się fakt, że twoja odpowiedź zawiera logikę, która byłaby potrzebna dla takiej struktury danych, oraz różne atrybuty bloku
Rachel
Ten model danych jest bardziej zgodny z rzeczywistością, ale sprawia, że ​​niektóre proste operacje, które chciałbyś wykonać, są trudniejsze niż powinny być - Samo uzyskanie stanu kostki wymagałoby rekurencyjnego przemieszczania się po listach kostek, co jest uciążliwe.
Ziv
@Ziv Prawda, ale pytanie dotyczyło struktury danych i niekoniecznie algorytmów.
wałek klonowy
13

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.

Matthew Vines
źródło
1
Klasyczna rada „nie chcesz zaczynać odtąd”!
Ergwun,
8

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ą.
użytkownik156217
źródło
3
Przekonałem się, że tego rodzaju implementacja najlepiej reprezentuje kostkę w programie graficznym 3D. Mnożenie macierzy umożliwia animację rotacji warstw. Zobacz repozytorium github, aby zobaczyć przykładową implementację tego podejścia. Rozważam, że aby dodać solver do mojej kostki 3D, potrzebuję algorytmu i struktury danych z jednej z pozostałych odpowiedzi.
Jonathan Wilson
5

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ę

maniak zapadkowy
źródło
1
the most straightforward way of know whether a cube is solvable is to solve it. Korzystając z modelu, który sugerujesz, myślę, że to prawda. Ale jeśli użyjesz modelu bliższego do @ wałka klonu i obrotu toru, możesz szybko sprawdzić, czy sześcian 3x3x3 jest rozwiązalny, sprawdzając sumę przewrotów krawędzi mod 2 wynosi 0, a obrót narożnika mod 3 wynosi 0. Następnie sprawdź parzystość permutacji przez licząc swapy krawędziowe i narożne (potrzebne, aby wrócić do rozwiązania), ich suma mod 2 musi wynosić 0 (parzystość całkowita). Są to niezbędne i wystarczające testy, aby udowodnić, że sześcian jest do rozwiązania.
jimhark
3

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).

Angelo
źródło
1
Dla punktu 2 zamiast zaczynać od losowej kostki i sprawdzać, czy można ją rozwiązać. Zaczynam od rozwiązanej kostki i wykonuję n przypadkowych akcji na kostce, aby uzyskać losowy stan.
Matthew Vines
Tak, absolutnie, jest to najprostszy sposób na wygenerowanie konfiguracji, którą fizycznie można rozwiązać. Rozpoczęcie od dowolnej konfiguracji i ustalenie, czy da się ją rozwiązać, jest zdecydowanie odrębnym, ale powiązanym problemem.
Angelo,
2
Przypuszczasz, że mogą istnieć „fantazyjne techniki” pozwalające ustalić, czy sześcian można rozwiązać; w rzeczywistości są. Jeśli zdemontujesz kostkę, ale utrzymasz naklejki, a następnie ponownie ją złożysz, niekoniecznie otrzymasz kostkę, którą można rozwiązać; w rzeczywistości szanse wynoszą jeden do dwunastu w porównaniu z tym, że masz kostkę do rozwiązania. Możesz ustalić, czy jesteś w stanie do rozwiązania, poprzez analizę parzystości krawędzi i narożników; tak naprawdę nie musisz próbować rozwiązać sześcianu.
Eric Lippert,
1
Oto krótki przegląd trzech rodzajów właściwości pary kostek, które należy zachować, aby kostka mogła zostać rozwiązana. ryanheise.com/cube/cube_laws.html .
Eric Lippert,
1
Zadałem
Mel.
3

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: Biblioteka diagramów-rubików-kostek w akcji

Ingo Blechschmidt
źródło
2

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.

B Seven
źródło
Możesz kupić kostkę 17x17 ! Ma pewne mechaniczne kompromisy, ale w rzeczywistości jest izomorficzny.
RBerteig,
1

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.

9000
źródło
1

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.

Spencer Rathbun
źródło
-1

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.

Martyn Strong
źródło
wydaje się, że nie oferuje to nic istotnego w porównaniu z punktami przedstawionymi i wyjaśnionymi w poprzednich 11 odpowiedziach
gnat