Αλγόριθμοι βέλτιστης επίλυσης για τον κύβο του Ρούμπικ
| datacite.contributor.Supervisor | Σγάρμπας, Κυριάκος | |
| datacite.contributor.Supervisor | Μουστάκας, Κωνσταντίνος | |
| datacite.contributor.Supervisor | Σιντόρης, Χρήστος | |
| dc.contributor.author | Τόσκα, Αλέξανδρος | |
| dc.contributor.other | Toska Alexandros | |
| dc.date.accessioned | 2026-07-07T06:08:36Z | |
| dc.date.available | 2026-07-07T06:08:36Z | |
| dc.date.issued | 2026-07-06 | |
| dc.degree | graduateThesis | |
| dc.description.abstract | Η παρούσα διπλωματική εργασία μελετά αλγορίθμους επίλυσης του κύβου του Rubik 3×3×3 και ειδικά το ζήτημα της βέλτιστης λύσης: πότε μια ακολουθία κινήσεων λύνει απλώς τον κύβο και πότε μπορεί να αποδειχθεί ότι είναι η συντομότερη. Το επίσημο θέμα ζητά την υλοποίηση των αλγορίθμων Thistlethwaite, Kociemba και Korf, τον υπολογισμό της απόστασης μιας κατάστασης από τη λυμένη θέση και την επιλογή ευρετικής συνάρτησης για αναζήτηση τύπου A* ή παραλλαγή της. Η εργασία ακολουθεί αυτούς τους τρεις άξονες. Υλοποιείται μοντέλο του κύβου με βάση τα κυβίδια, με ελέγχους φυσικής εγκυρότητας και ανεξάρτητη επαλήθευση των λύσεων. Πάνω σε αυτό το μοντέλο υλοποιούνται οι τρεις αλγόριθμοι. Ο Korf δίνεται ως αναζήτηση IDA* με παραδεκτές ευρετικές από βάσεις δεδομένων προτύπων, ενώ οι Kociemba και Thistlethwaite χρησιμοποιούνται ως πρακτικοί επιλυτές. Για τον υπολογισμό απόστασης, το πρόγραμμα δίνει ακριβή τιμή μόνο όταν η αναζήτηση ολοκληρώνει την απόδειξη· διαφορετικά αναφέρει κάτω φράγμα, λήξη χρονικού ορίου ή άκυρη κατάσταση. Τα πειράματα παρουσιάζουν τι πετυχαίνει κάθε προσέγγιση στο επιλεγμένο σύνολο δοκιμών. Ο κώδικας της εργασίας αποδεικνύει βελτιστότητα έως απόσταση 14, καθώς και για το superflip (απόσταση 20). Για βαθύτερες ακριβείς περιπτώσεις χρησιμοποιείται εξωτερική μηχανή ως έλεγχος αναφοράς. Το superflip εξετάζεται ως δύσκολη περίπτωση του κύβου 3×3×3, ενώ ο κύβος 2×2×2 (Pocket Cube) χρησιμοποιείται ως μικρότερο παράδειγμα όπου μπορεί να γίνει πλήρης εξαντλητική μελέτη. Τα αποτελέσματα συνοδεύονται από σενάρια αναπαραγωγής, ώστε να φαίνεται ποιες λύσεις είναι απλώς επαληθευμένες, ποιες είναι αποδεδειγμένα βέλτιστες και ποιες αναζητήσεις δεν ολοκληρώθηκαν. Ο κώδικας, μαζί με τα σενάρια αναπαραγωγής των μετρήσεων και τα δεδομένα εισόδου των πειραμάτων, είναι δημόσια διαθέσιμος στη διεύθυνση: https://github.com/AlexTs10/rubik-optimal | |
| dc.description.translatedabstract | This thesis studies algorithms for solving the 3×3×3 Rubik’s Cube, with emphasis on optimal solutions: when a sequence of moves merely solves the cube, and when it can be proved to be shortest possible. The official topic asks for implementations of the Thistlethwaite, Kociemba, and Korf algorithms, distance recognition from the solved state, and a heuristic for A* search or one of its variants. The thesis follows these three goals.The implementation builds a cubie-level cube model, checks whether a state is physically valid, and verifies returned solutions independently. On top of this model, the three requested algorithms are implemented. Korf is implemented as an IDA* search with admissible pattern-database heuristics, while Kociemba and Thistlethwaite are used as practical solvers. Distance recognition returns an exact value only when the search completes the proof; otherwise it reports a lower bound, a timeout, or an invalid state.The experiments show what each approach achieves on the selected test set. The thesis’s own code proves optimality up to distance 14, as well as for the superflip (distance 20). Deeper exact cases are checked with an external engine used as a reference. The superflip is treated as a difficult 3×3×3 case, and the 2×2×2 Pocket Cube is included as a smaller example where a complete exhaustive study is feasible. The results are accompanied by reproduction scripts, so that verified solutions, proven optimal solutions, and unfinished searches remain separate.The code, together with the measurement-reproduction scripts and the experiment input data, is publicly available at: https://github.com/AlexTs10/rubik-optimal | |
| dc.identifier.uri | https://hdl.handle.net/10889/32328 | |
| dc.language.iso | el | |
| dc.rights | Attribution 3.0 Greece | en |
| dc.rights.uri | http://creativecommons.org/licenses/by/3.0/gr/ | |
| dc.subject | Κύβος του Rubik | |
| dc.subject | Βέλτιστη επίλυση | |
| dc.subject | Παραδεκτή ευρετική | |
| dc.subject.alternative | Rubik’s cube | |
| dc.subject.alternative | Pattern databases | |
| dc.subject.alternative | Kociemba | |
| dc.subject.alternative | Thistlethwaite | |
| dc.title | Αλγόριθμοι βέλτιστης επίλυσης για τον κύβο του Ρούμπικ | |
| dc.title.alternative | Optimal solution algorithms for the Rubik's cube |