ABSTRAKSI: Kubus Rubik merupakan puzzle 3 dimensi yang ditemukan oleh pemahat sekaligus Arsitektur Profesor dari Hungaria yang bernama Erno Rubik dan diberi nama Rubik’s Cube. Secara umum, terdapat dua metode untuk mencari solusi dari kubus rubik 3x3x3, yaitu metode konvensional dan metode heuristik.
Untuk metode heuristik digunakan algoritma A*, karena selain algoritma ini pasti dapat menemukan solusi, solusi yang dihasilkan lebih optimal walau solusi tersebut sulit untuk dipahami, sedangkan untuk metode konvensional digunakan algoritma Layer by layer, karena algoritma ini dapat memberikan solusi yang sistematis dan mudah dipahami user. Pada Tugas Akhir ini dilakukan analisis pada algoritma A* untuk kubus Rubik 3x3x3 dan algoritma Layer by Layer, yaitu analisis kompleksitas waktu asimptotik, dan analisis tingkat performansi sistem dengan melakukan perbandingan kecepatan waktu eksekusi sistem dari masing-masing algoritma tersebut.
Berdasarkan observasi yang telah dilakukan, diketahui bahwa kompleksitas waktu asimptotik algoritma Layer by Layer lebih baik dari pada algoritma A* untuk kubus Rubik 3x3x3. Pada analisis kecepatan waktu eksekusi, Algoritma Layer by Layer membutuhkan waktu kurang satu detik untuk menyelesaikan permasalahan kubus Rubik, sedangkan algoritma A* untuk kubus Rubik 3x3x3 membutuhkan waktu eksekusi yang lebih lama apabila jumlah acak pada kubus Rubik semakin banyak. Selain itu, kebutuhan memori Algoritma A* untuk kubus Rubik 3x3x3 adalah sebesar 64 Byte dikali jumlah larik pada ruang pencarian.Kata Kunci : kubus Rubik 3x3x3, A*, Layer by layerABSTRACT: Rubik's Cube is a three-dimensional puzzle invented by Hungarian sculptor and professor of architecture Erno Rubik. Generally, there are two methods to find the solution of the Rubik's Cube 3x3x3, the conventional method and heuristic methods.
For heuristic method, A* algorithm is selected because apart from this algorithm must be able to find a solution, this algorithm can produced a more optimal solution although the solution is difficult to understand. While the conventional method, Layer by Layer algorithm is selected because this algorithm can produce systematic solutions and can be easily understood by users. In this final project, A* algorithm for Rubik’s cube 3x3x3 and Layer by Layer algorithm was analyzed and compared by asymptotic time complexity and system performance which can be seen by system execution time of each algorithm.
Based on the observations that have been done, it is known that the asymptotic time complexity of Layer by Layer algorithm is better than A* algorithm for Rubik’s cube 3x3x3. In the analysis of system execution time, Layer by Layer algorithm takes less than one second to solve Rubik’s cube, whereas the A * algorithm for Rubik’s cube 3x3x3 requires a longer execution time when the number of random at Rubik's cube is increased. In addition, the memory requirement of Algorithm A * for Rubik’s cube 3x3x3 is 64 bytes for each node in the search space.Keyword: Rubik’s cube 3x3x3, A*, Layer by layer.