Cara menghitung total putaran tetrad kubus rubik
Saya sedang mengerjakan implementasi algoritma Thistlewaite untuk memecahkan kubus Rubik dan saya sekarang menghadapi masalah tikungan tetrad. Berkat jawaban ini , saya mengerti apa itu dan bagaimana mereka mengurangi jumlah keadaan di fase 3, tetapi masalah yang saya hadapi adalah menemukan cara untuk menghitung total putaran tetrad kubus dari keadaannya saja.
Cara saya mengimplementasikan algoritme ini bukan dengan pencarian luas pertama dan oleh karena itu saya tidak bisa begitu saja menggunakan kondisi yang lebih kuat yang ditemukan di sini dan di sini untuk mengetahui apakah saya sudah selesai dengan tahap 3 karena itu tidak berguna bagi saya. Cara saya melakukannya adalah dengan menghitung sebelumnya tabel pencarian dan melihat di dalamnya untuk mengetahui cara menyelesaikan status tertentu. Untuk alasan itu saya perlu sepenuhnya mengkarakterisasi informasi yang diperlukan untuk membedakan status tahap 3 yang berbeda. Saya sudah memiliki tetrad sudut, irisan tepi, dan paritas selesai, hal terakhir yang saya butuhkan adalah cara untuk mengekspresikan putaran tetrad suatu keadaan (atau info yang setara). Hal terbaik adalah dengan memberikan nilai antara 0, 1 atau 2 dan menggunakannya untuk mendeskripsikan putaran total.
Saya harap pertanyaan saya jelas, dan jika tidak, silakan ajukan pertanyaan di komentar, saya akan melakukan yang terbaik untuk menjelaskannya lebih lanjut.
Jawaban
Agak sulit untuk mengekstrak informasi ini secara langsung dari lokasi potongan sudut saat ini. Sejauh ini, cara termudah adalah dengan mencoba menyelesaikan kepingan sudut hanya dengan menggunakan setengah putaran (sambil mengabaikan kepingan tepi), dan lihat seberapa jauh Anda melaju.
Untuk saat ini saya akan berasumsi bahwa potongan sudut sudah berada di orbit tetrad yang benar {UFR, UBL, DFL, DBR} dan {UFL, UBR, DFR, DBL}. Anda dapat menyelesaikan kepingan satu tetrad dengan sangat mudah, tidak lebih dari satu setengah putaran untuk setiap bidak, maksimal total 3 gerakan. Misalnya, selesaikan DBR menggunakan paling banyak salah satu dari {D2, B2, R2}, lalu DFL menggunakan paling banyak salah satu dari {F2, L2}, dan terakhir UBL menggunakan {U2} jika perlu, yang juga membuat UFR terpecahkan.
Anda kemudian menyelesaikan satu bagian dari tetrad kedua, misalnya DBL, menggunakan salah satu urutan langkah {F2 L2 F2 U2, U2 F2 U2 L2, L2 U2 L2 F2}. Urutan langkah ini melakukan pertukaran ganda pada empat bagian dari tetrad kedua, dan merupakan satu-satunya permutasi yang memungkinkan yang membuat tetrad pertama tetap.
Ini menyisakan tiga bagian yang belum terpecahkan, {UFL, UBR, DFR}. Ini bisa di salah satu dari 3! = 6 permutasi. 6 kemungkinan ini mewakili putaran tetrad dalam kombinasi dengan paritas permutasi, jadi jika Anda memetakan permutasi ini ke angka dari 0 hingga 5, Anda telah menyandikan kedua paritas permutasi dan putaran tetrad menjadi satu angka.
Untuk algoritme Thistlethwaite, Anda mungkin ingin menyandikan posisi sembarang dari tahap ketiga algoritme. Hal ini harus dilakukan secara konsisten, maksud saya jika dua posisi berbeda dibawa ke tahap keempat dengan urutan gerakan yang sama (yaitu setelah menerapkan urutan gerakan ke posisi tersebut, keduanya menjadi dapat diselesaikan hanya dengan menggunakan setengah putaran) maka kedua posisi tersebut harus memiliki pengkodean yang sama untuk tahap 3.
Agaknya program Anda mencantumkan lokasi sudut kubus dalam urutan tetap tertentu. Misalnya, Anda mungkin memiliki larik dengan panjang 8 yang mewakili lokasi dalam urutan
UFR , UFL, UBL , UBR, DFR, DFL , DBL, DBR .
Saya telah menebalkan lokasi yang mewakili salah satu tetrad, yang berada di indeks 0, 2, 5, 7 dalam array. Anda mungkin telah memilih konvensi pengurutan yang berbeda dalam program Anda, tetapi metodenya sama.
Misalkan Anda sekarang memiliki posisi kubus tahap 3 sewenang-wenang, beberapa permutasi acak dari 8 sudut tersebut, misalnya:
UBR, UBL , DBR , DFR, DFL , UFR , UFL, DBL.
Cara konsisten sederhana untuk memisahkan potongan-potongan menjadi dua tetrad adalah dengan benar-benar memisahkan dua jenis potongan tanpa mengubah urutan relatifnya:
UBL , DBR , DFL , UFR
UBR, DFR, UFL, DBL.
Dan kemudian memasukkannya ke dalam larik penyimpanan, secara berurutan, masing-masing ke dalam lokasi tetrad yang benar. Jadi set pertama masuk ke indeks 0,2,5,7, yang lainnya di indeks 1,3,4,6.
UBL , UBR, DBR, DFR, UFL, DFL , DBL, UFR .
Sekarang Anda dapat menerapkan teknik penyelesaian yang saya jelaskan di awal, untuk berakhir dengan pengkodean yang konsisten dari posisi tetrad twist dan paritas.
Di atas mengasumsikan Anda menggunakan satu cara standar untuk merepresentasikan kubus, dan Anda menerapkan pemindahan ke sana. Sebagai gantinya, Anda mungkin ingin menyimpan dua daftar terpisah dari potongan tetrad sebagai representasi yang disederhanakan dari posisi ini, dan mengaktifkannya secara langsung saat Anda menyelesaikannya untuk mengekstrak pengkodean twist + paritas.
Anda dapat melihat beberapa program di kontes pemrograman kubus lama ini , meskipun saya tidak yakin program tersebut akan sangat membantu karena ditulis untuk ringkas, bukan untuk kejelasan.