Mój pierwszy post na forum, mam nadzieję, że nie ostatni
Wstyd się przyznać, ale jako inżynier mam problem z rozwiązaniem prostego (jak mi się wydawało) zadania. Chodzi mianowicie o liczbę możliwych rozwiązywalnych (zaraz wyjaśnie) układów klasycznej (3x3x3) kostki Rubika.
Kod: Zaznacz cały
http://hiremebecauseimsmart.posterous.com/post/1120517680Zasadniczo kostka ma wymiary 3x3x3 sześciany. Byłoby ich 27 gdyby nie to, ze wewnątrz jest pustka. Mamy zatem 26 klocków. Ale tylko 20 z nich ma zmienne położenie. Każda z sześciu środkowych płytek na każdej ścianie ma stałą pozycję względem siebie (środkowa płytka każdej ściany określa kolor ściany).
Mamy zatem 20 ruchomych kostek.
Żeby nie było zbyt łatwo to nie wszystkie poruszają się w ten sam sposób. 8 narożników (każdy po 3 płytki) może być w 8 miejscach. 10 ścian bocznych (każda po dwie płytki) może zajmować 10 miejsc.
A żeby było mało - to dochodzi jeszcze problem rozwiązywalności.
Nie każdy "mechanicznie" złożony układ jest możliwy do rozwiązania. Innymi słowy - jeśli mielibyśmy kostkę w rozsypce i złożyli ją dowolnie (na przykład losując klocki) to nie zawsze da się ją ułożyć poprawnie. Myślę, że ilustracje poniżej oddadzą lepiej sens kwestii rozwiązywalności i nierozwiązywalności "układu":
Układ rozwiązany (i rozwiązywalny co za tym idzie):
[url=http://imageshack.us/photo/my-images/853/imag0082e.jpg/][/url]
Jednak układ z poniższych dwóch zdjęć już nie jest możliwy bez mechanicznego rozłożenia kostki (do zrobienia zdjęcia kostkę rozłożyłem mechanicznie):
[url=http://imageshack.us/photo/my-images/233/imag0083uw.jpg/][/url][[url=http://imageshack.us/photo/my-images/848/imag0084eb.jpg/][/url]
O tym, że jest to układ nierozwiązywalny może choćby świadczyć [url=http://www.wrongway.org/cgi-bin/cube/cubexcgiout?cube-311111111222222222433333333441444444555555555666666666!withgraphics]ten komunikat[/url] solvera (nota bene solver proponuje dość długie algorytmy, ale poglądowo można czasem się nim połsużyć).
Jak zatem widać trudno tu o prosty rachunek typu liczba kostek razy liczba ich możliwych położeń razy liczba orientacji ścian (bo jak wykazałem na dwóch ostatnich zdjęciach nie każda możliwa orientacja ścian nas interesuje).
Liczenie liczby układów trzeba ugryźć od strony możliwych ruchów (zaczynając od jednego układu - powiedzmy od kostki rozwiązanej). Pamiętając jednakże, że trzykrotny ruch ścianą w jednym kierunku - to to samo co jeden ruch ścianą w przeciwnym. Że dwukrotny ruch w dowolną stronę daje ten sam efekt (niezależnie od strony obrotu). Ścian mamy 6. Ale dochodzą 3 środkowe (tzw równik, południk 0, i południk 90) - których ruch z kolei można potraktować jako złożenie ruchu 6 podstawowych ścian - np. obrót równika w lewo, to to samo co jednoczesny obrót góry i dołu w przeciwną stronę, etc.
I tu się gubię, bo kompletnie nie wiem jak to ugryźć, a chciałbym zweryfikować liczbę możliwych układów, podaną na cytowanej przeze mnie stronie.
Ktoś jest w stanie mi pomóc?
Wstyd mi w sumie, że jako inżynier, z zamiłowaniem matematycznym nie potrafię sobie z tym poradzić... Ale kto pytanie nie błądzi
(A jakby kogoś interesowało po co mi to - chciałem zbadać złożoność obliczeniową - i sprawdzić czy jest sens pisania programu do rozwiązywania kostki metodą "brutal force" - są wprawdzie algorytmy rozwiązujące, ale nie podają najkrótszych rozwiązań, a operują na kilku popularnych schematach [layer by layer, corner first, etc], A mnie interesują wyłącznie najkrótsze rozwiązania - ale żeby się za to zabrać muszę najpierw wiedzieć czy mnie nie zje złożoność obliczeniowa - czyli ile jest poprawnych mechanicznie układów)
Z góry dzięki za pomoc!
Ł
