Najłatwiejszy algorytm kodu dla kostki Rubika?

Question

Jaki byłby stosunkowo łatwy algorytm do kodowania w Javie do rozwiązania kostki Rubika. Wydajność jest również ważna, ale jest kwestią drugorzędną.

Answer 1

Najprostszym nietrywialne algorytm znalazłem jest to jedno:

http://www.chessandpoker.com/rubiks-cube-solution.html

Nie jest trudno napisać kod. Łącze wymienione w Yannick M.'s answer również wygląda dobrze, ale rozwiązanie kroku "the cross" wygląda na nieco bardziej skomplikowane.

Istnieje wiele implementacji rozwiązań open source, które warto przyjrzeć. Oto Python implementation. Ten Java applet zawiera również solver, a kod źródłowy jest dostępny. Jest też Javascript solver, również z pobieralnym kodem źródłowym.

Anthony Gatlin's answer stanowi doskonały punkt na dobre dopasowanie Prolog do tego zadania. Oto szczegółowy artykuł na temat tworzenia własnego Prolog solver. Zastosowane heurystyki są szczególnie interesujące.

Answer 2

Wykonuj losowe operacje, aż uzyskasz właściwe rozwiązanie. Najprostszy algorytm i najmniej efektywny.

Answer 3

chcieć sprawdzić: http://peter.stillhq.com/jasmine/rubikscubesolution.html

Posiada graficzną reprezentację algorytmu do rozwiązania sześcian danej 3x3x3 Rubika

Answer 4

Rozumiem, że twoje pytanie jest związane z Javą, ale z praktycznego punktu widzenia języki takie jak Prolog są znacznie lepiej dopasowane, jak rozwiązywanie kostki Rubika. Zakładam, że jest to prawdopodobnie dla klasy i możesz nie mieć żadnej pewności co do wyboru narzędzia.

Answer 5

Możesz to zrobić, wykonując BFS (ang. "Szerokość-pierwsze wyszukiwanie"). Myślę, że wdrożenie nie jest takie trudne (Jest to jeden z najprostszych algorytmów w kategorii wykresu). Robiąc to ze strukturą danych o nazwie queue, naprawdę będziesz pracować nad budowaniem drzewa BFS i znalezieniem tak zwanej najkrótszej ścieżki od danego warunku do stanu pożądania. Wadą tego algorytmu jest to, że nie jest on wystarczająco wydajny (bez modyfikacji, nawet do rozwiązania kubitu 2x2x2, wymagany czas wynosi ~ 5 minut). Ale zawsze możesz znaleźć kilka sztuczek, aby zwiększyć prędkość.

Szczerze mówiąc, jest to jedno z zadań domowych kursu "Introduction of Algorithm" od MIT. Oto link do pracy domowej: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf. Mają kilka bibliotek, które pomogą ci je zwizualizować i pomogą ci uniknąć niepotrzebnego wysiłku.