Menggunakan Python dan Pencarian Pertama Luas 2 sisi untuk menyelesaikan Kubus Rubik 2x2.
Terinspirasi oleh proyek di MIT 6.006. Dibuat dari awal secara unik.
https://youtu.be/ZHxLO6fubaU
Membuat API kubus, Algoritma, dan GUI dari awal. Masing-masing dari 6 sisinya mempunyai 4 kotak berbeda sehingga menghasilkan 24 kotak. Selain itu, terdapat 8 buah sudut yang menyusun kubus tersebut, yang masing-masing mempunyai 3 orientasi sehingga sejajar dengan 24 persegi tersebut.
Saya mendefinisikan masing-masing dari 24 subbagian dari setiap sisi sebagai string dengan 'xyz' sebagai format di mana x adalah warna yang menghadap langsung dan y dan z berada dalam urutan searah jarum jam di sekitar kubus untuk sudut itu.
Saya berkeliling kubus dan menugaskan setiap sisi dengan nomor tetap yang mewakili keadaan terselesaikan. Misal 0, 1, 2, 3 adalah 4 bagian depan menghadap sisi putih dimana 0 di kiri atas dan ohternya searah jarum jam.
Ada 12 gerakan yang bisa dilakukan pada kubus. Kanan, kiri, atas, bawah, depan, belakang. Masing-masing juga memiliki gerakan berlawanan arah jarum jam sehingga 6x2 = 12 gerakan. Masing-masing dari 12 ini memanipulasi setengah kubus menjadi 12 kotak. Untuk melakukan gerakan ini, saya membuat kamus untuk masing-masing dari 6 searah jarum jam yang sub-kotaknya berputar dari posisi asli ke posisi berikutnya. Untuk mengerjakan bilangan prima, saya hanya mengganti kunci dan nilainya.
Menyelesaikan masalah ini sangat rumit karena banyaknya kemungkinan permutasi kubus. Ada 24 subkotak dan hasilnya 24P24 = 24!. Ini berkekuatan 10^23. Jumlahnya kurang dari jumlah tersebut karena situasi tertentu namun jumlahnya masih sangat besar.
Untuk membuat pohon, saya harus menjalankan setiap gerakan dan menjalankan semua gerakan dari gerakan yang menjadi sangat besar. 12^tinggi pohon. Saya dapat membatasi ukuran ini dengan membuat dikte posisi yang dikunjungi sehingga tidak mengulangi tindakan permutasi yang dikunjungi sebelumnya.
Saya mulai dengan membuat BFS 1 sisi tetapi itu akan mencapai batas rekursi karena pohon percabangan menjadi terlalu besar. Untuk memperbaikinya, saya menggunakan BFS 2 sisi dengan membuat cabang secara bergantian dari solusi awal dan akhir. Itu akan membuat pepohonan dan memeriksa apakah pihak lawan sudah menemukan intinya. Jika ya, maka titik penghubung akan dikembalikan.
Selama proses ini, setiap node menyimpan induknya (untuk percabangan depan) atau anaknya (untuk percabangan belakang). Untuk menemukan rute yang diperlukan, saya secara rekursif menemukan induk dari simpul penghubung dan kemudian semua anak dari titik tersebut. Hal ini menghasilkan serangkaian posisi yang diambil dari yang diacak hingga yang terselesaikan.
Proyek ini menerapkan penggunaan teori grafik dan Breadth First Search . Saya meningkatkan kemampuan saya dalam Python dan rekursi. Saya juga secara eksperimental menemukan langkah maksimal untuk menyelesaikan kubus 2x2 menjadi 11 langkah karena saya tidak pernah dapat menemukan solusi yang membutuhkan waktu lebih lama.
Mempelajari cara menggunakan perpustakaan tkinter untuk membuat GUI untuk proyek tersebut
