Projekt Cube Solver #02 – Generowanie scrambli – teoria

Projekt Cube Solver #02 – Generowanie scrambli – teoria

Dzisiaj skupię się głównie na teorii algorytmów mieszających jaka będzie niezbędna podczas pisania generatora algorytmów mieszających.
Samym generatorem zajmę się w następnym wpisie, który pojawi się już niedługo.

Artykuł dostępny także w wersji angielskiej.

Omówienie notacji

Istnieje kilka notacji wykorzystywanych do zapisywania ruchów na kostce. Najpopularniejsza z nich to notacja wymyślona przez Davida Singmastera, w której litery odpowiadają angielskim nazwom ścianek.

Wszystkie ruchy niezbędne do modyfikacji ustawienia kostki przedstawiam poniżej. Są to:

  • U – ruch ścianką górną (up)
  • D – ruch ścianką dolna (down)
  • F – ruch ścianką przednią (front)
  • B – ruch ścianką tylną (back)
  • R – ruch ścianką prawą (right)
  • L – ruch ścianką lewą (left)

Każdy z tych ruchów oznacza ruch ścianka zgodnie ze wskazówkami zegara. Aby zapisać ruch przeciwny do wskazówek zegara należy dopisać przy nim apostrof (‚).
Ścianką można także ruszyć dwa razy co można zapisać przez dodanie cyfry 2 do oznaczenia ścianki.

Przykładowy algorytm mieszający można zatem zapisać:
R' F R' B2 U B2 L' D' R B2 D R F' R2 D F D2 B D' F L B D' L' D

a wygląd takiej kostki po pomieszaniu prezentuje się następująco:
Kostka pomieszana algorytmem R' F R' B2 U B2 L' D' R B2 D R F' R2 D F D2 B D' F L B D' L' D

Taki algorytm mieszający ma z reguły 25 ruchów, chociaż nic nie stoi na przeszkodzie aby było ich więcej.

Unikanie skracających się ruchów

Generując algorytm mieszający trzeba pamiętać o dwóch kwestiach.
Pierwsza z nich mówi, że nie należy ruszać wielokrotnie tą samą ścianką.
Przykład poniżej prezentuje wielokrotne użycie ścianki F.
R' (F F F' F2) R' F R' B2 U B2 L' D'

Taki manewr nie sprawia, że kostka jest lepiej pomieszana ponieważ ciąg ten jest tym samym co użycie ruchu:
F'

Druga kwestia dotyczy ruszania ściankami równoległymi. Poniższy przykład pokazuje ten przypadek:
R' (F B F2 B2 F') R' F R' B2 U B2 L' D'

Ruchy takie nie mają części wspólnej, nie nakładają się na siebie i dlatego taką sekwencję można łatwo skrócić do
F2 B'

Co dalej?

Dzisiaj poznaliśmy teorie niezbędną aby prawidłowo zaimplementować generator scrambli. W następnym wpisie z tej serii, który pojawi się w przyszłym tygodniu zaimplementujemy go zaczynając oczywiście od testów.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *