Jika saya mencoba mensimulasikan Rubik's Cube , bagaimana Anda membuat struktur data untuk menyimpan status kubus dalam memori, dengan jumlah X ubin per sisi?
Hal yang perlu dipertimbangkan:
- kubus bisa dari berbagai ukuran
- itu adalah kubus Rubik, sehingga lapisan dapat diputar
Jawaban:
Apa yang salah dengan ukuran array yang lama
[6X][X]
? Anda tidak perlu tahu tentang inner mini-batu, karena Anda tidak melihat mereka; mereka bukan bagian dari keadaan kubus. Sembunyikan dua metode jelek di balik antarmuka yang tampak bagus dan mudah digunakan, uji unit itu sampai mati, dan voila, Anda sudah selesai!sumber
As long as you know how the six surfaces are "threaded" together
Persis seperti itulah struktur data yang lebih kuat akan memberi Anda. Saya pikir kita berdebat untuk hal yang sama. Sisi array, dan sisi menjadi array blok, namun ada banyak properti menarik tentang sisi dan blok yang membantu mengetahui bahwa "threading" Tidak terlalu menyukai istilah itu karena dapat dikacaukan dengan multi-threading; )Perlu dicatat bahwa saya adalah cuber kecepatan avid, tetapi saya tidak pernah mencoba untuk secara sistematis mewakili kubus Rubik dalam algoritma atau struktur data.
Saya mungkin akan membuat struktur data terpisah untuk menangkap aspek unik dari setiap blok dalam sebuah kubus.
Ada 3 jenis blok pada kubus:
Corner Block - Ini memiliki tiga wajah warna dan tiga bagian yang berdekatan yang akan dibagikan setiap saat.
Edge Block - Ini memiliki dua wajah warna dan memiliki 4 buah yang berdekatan yang akan dibagikan setiap saat. Dalam blok 3x3 selalu memiliki 2 bagian tengah dan 2 buah sudut.
Blok tengah - Dalam kubus 3x3 bagian ini tidak dapat bergerak, namun dapat diputar. Itu akan selalu memiliki 4 blok tepi yang berdekatan. Di kubus yang lebih besar ada beberapa blok tengah yang bisa dibagikan dengan blok tengah lain atau bagian tepi. Blok tengah tidak pernah berbatasan dengan blok sudut.
Mengetahui hal ini, Blok dapat memiliki daftar referensi ke blok lain yang disentuhnya. Saya akan menyimpan daftar daftar lain, yang akan menjadi daftar blok yang mewakili wajah kubus tunggal dan daftar yang menyimpan referensi ke setiap wajah kubus.
Setiap wajah kubus akan direpresentasikan sebagai wajah yang unik.
Dengan struktur data ini akan sangat mudah untuk menulis sebuah algoritma yang melakukan transformasi rotasi pada setiap wajah, memindahkan blok yang sesuai ke dalam dan keluar dari daftar yang sesuai.
EDIT: Catatan penting, daftar ini harus dipesan tentu saja tetapi saya lupa menyebutkan itu. Misalnya, jika saya membalik sisi kanan, maka blok sudut kanan bergerak ke sudut kanan sisi kanan dan diputar searah jarum jam.
sumber
list of lists
. mungkin lebih baik hanya memiliki daftar blokir yang tidak dapat ditata yang dapat Anda query. dan Anda baru saja memperbarui referensi blok yang berdekatan ketika Anda melakukan transformasi. Jika Anda ingin daftar semua blok di wajah maka Anda bisa meminta daftar untuk semua blok yang berdekatan ke blok tengah, kan?Ketika saya memikirkan masalah ini, saya memikirkan sebuah kubus statis dengan warna yang bergerak melintasinya dalam pola yang dikenal. Begitu....
Objek kubus berisi 6 objek sisi yang tetap diperbaiki diindeks 0-5. Setiap sisi berisi 9 posisi objek yang tetap terindeks tetap 0-8. Setiap posisi mengandung warna.
Untuk kesederhanaan, tangani setiap tindakan secara bertahap seperempat putaran. Ada 3 sumbu rotasi, masing-masing dalam 2 arah yang memungkinkan untuk total 6 tindakan yang mungkin pada kubus. Dengan informasi ini, menjadi tugas yang cukup sederhana untuk memetakan 6 tindakan yang mungkin pada kubus.
Jadi warna hijau di sisi 6, posisi 3, dapat pindah ke sisi 1 posisi 3, atau sisi 2 posisi 7, antara lain, tergantung pada tindakan yang diambil. Saya belum cukup mengeksplorasi ini untuk menemukan terjemahan matematika, tetapi pola mungkin akan muncul yang dapat Anda manfaatkan dalam kode.
Untuk melakukan ini, jangan pernah mulai dengan keadaan kubus acak. Alih-alih, mulailah dengan keadaan terpecahkan, dan lakukan tindakan n secara terprogram untuk membuat kubus menjadi keadaan awal yang acak. Karena Anda hanya mengambil tindakan hukum untuk mencapai kondisi saat ini, kubus harus dipecahkan.
sumber
Saya menemukan sistem koordinat xyz sebagai cara sederhana untuk mengatasi kubus Rubik, dan matriks rotasi merupakan cara sederhana dan umum untuk menerapkan rotasi.
Saya membuat kelas Piece yang berisi vektor posisi
(x, y, z)
. Sepotong dapat diputar dengan menerapkan matriks rotasi ke posisinya (perkalian matriks-vektor). Sepotong juga menyimpan jejak warna dalam tuple(cx, cy, cz)
, memberikan warna yang menghadap sepanjang sumbu. Sejumlah kecil logika memastikan warna-warna ini diperbarui dengan benar selama rotasi: rotasi 90 derajat pada bidang XY berarti kita akan menukar nilaicx
dancy
.Karena semua logika rotasi dienkapsulasi dalam kelas Piece, Cube dapat menyimpan daftar Pieces yang tidak terurut, dan rotasi dapat dilakukan dengan cara yang umum. Untuk melakukan rotasi pada wajah kiri, pilih semua bagian dengan koordinat x -1 dan terapkan matriks rotasi yang sesuai untuk setiap bagian. Untuk melakukan rotasi seluruh kubus, terapkan matriks rotasi yang sama untuk setiap bagian.
Implementasi ini sederhana dan memiliki beberapa keunggulan:
(-1, 1, 1)
), tepi memiliki tepat satu nol ((1, 0, -1)
), dan potongan tengah memiliki dua nol ((-1, 0, 0)
).Kerugian:
sumber
Anda dapat menggunakan larik sederhana (setiap elemen memiliki pemetaan 1 ke 1 ke kotak pada wajah) dan mensimulasikan setiap rotasi dengan permutasi tertentu
Anda dapat pergi dengan hanya 3 permutasi penting: putar irisan dengan sumbu melalui wajah depan, putar kubus di sekitar sumbu vertikal dan putar kubus di atas sumbu horizontal melalui wajah kiri dan kanan. semua gerakan lain dapat diungkapkan oleh beberapa gabungan dari ketiganya.
cara yang paling mudah untuk mengetahui apakah sebuah kubus dapat dipecahkan adalah dengan mengatasinya (temukan serangkaian permutasi yang akan menyelesaikan kubus), jika Anda berakhir dengan 2 tepi yang telah bertukar tempat, satu ujung terbalik, satu sudut terbalik, satu sudut terbalik atau 2 sudut yang ditukar Anda memiliki kubus yang tidak dapat diatasi
sumber
the most straightforward way of know whether a cube is solvable is to solve it
. Nah, menggunakan model yang Anda sarankan saya kira itu benar. Tetapi jika Anda menggunakan model yang lebih dekat dengan @ maple_shaft dan melacak rotasi, Anda dapat dengan cepat menguji apakah kubus 3x3x3 dapat dipecahkan dengan memverifikasi jumlah ujung terbalik mod 2 adalah 0 dan rotasi sudut mod 3 adalah 0. Kemudian periksa paritas permutasi dengan menghitung edge swap dan corner swap (diperlukan untuk kembali ke penyelesaian), jumlah mod 2 mereka harus 0 (total paritas genap). Ini adalah tes yang diperlukan dan cukup untuk membuktikan bahwa kubus dapat dipecahkan.Kondisi pertama yang dapat dipecahkan adalah bahwa setiap bagian ada dan warna pada masing-masing bagian dapat digunakan untuk merakit kubus "sovled". Ini adalah kondisi yang relatif sepele yang kebenarannya dapat ditentukan dengan daftar periksa sederhana. Skema warna pada kubus "standar" didefinisikan , tetapi bahkan jika Anda tidak berurusan dengan kubus standar hanya ada 6! kemungkinan kombinasi wajah yang dipecahkan.
Setelah Anda memiliki semua bagian dan warna yang tepat, maka itu adalah masalah menentukan apakah konfigurasi fisik yang diberikan dapat dipecahkan. Tidak semuanya. Cara yang paling naif untuk memeriksa ini adalah dengan menjalankan algoritma pemecahan kubus dan melihat apakah itu berakhir dengan kubus yang diselesaikan. Saya tidak tahu apakah ada teknik kombinatorial yang bagus untuk menentukan solvabilitas tanpa benar-benar mencoba memecahkan kubus.
Adapun struktur data apa ... itu hampir tidak masalah. Bagian yang sulit adalah mendapatkan transformasi yang benar dan mampu mewakili keadaan kubus dengan cara yang memungkinkan Anda untuk bekerja dengan rapi dengan algoritma yang tersedia dalam literatur. Seperti yang ditunjukkan oleh Maple-shaft, ada tiga jenis keping. Sastra tentang pemecahan kubus rubik selalu merujuk pada potongan menurut tipenya. Transformasi juga direpresentasikan dengan cara yang umum (lihat notasi Singmaster ). Juga, semua solusi yang saya lihat selalu merujuk pada satu bagian sebagai titik referensi (biasanya menempatkan bagian tengah putih di bagian bawah).
sumber
Karena Anda sudah menerima jawaban yang bagus, izinkan saya menambahkan detail saja.
Terlepas dari representasi konkret Anda, perhatikan bahwa lensa adalah alat yang sangat bagus untuk "memperbesar" pada berbagai bagian kubus. Misalnya, lihat fungsi
cycleLeft
dalam kode Haskell ini . Ini adalah fungsi generik yang secara siklikal mengizinkan daftar panjang 4. Kode untuk melakukan gerakan L terlihat seperti ini:Jadi
cycleLeft
beroperasi pada pandangan yang diberikan olehleftCols
. Demikian pula,rotateSideCW
yang merupakan fungsi generik yang memihak versi yang diputar, beroperasi pada tampilan yang diberikan olehleftSide
. Langkah lain dapat diimplementasikan dengan cara yang serupa.Tujuan dari perpustakaan Haskell adalah untuk membuat gambar-gambar cantik. Saya pikir itu berhasil:
sumber
Anda sepertinya mengajukan dua pertanyaan terpisah.
Jika Anda akan mensimulasikan kubus Rubic dunia nyata, maka semua kubus Rubik memiliki 6 sisi. Saya pikir yang Anda maksud adalah "X jumlah ubin per dimensi per sisi". Setiap sisi kubus Rubik asli adalah 3x3. Ukuran lain termasuk 4x4 (Professor's Cube), 5x5, dan 6x6.
Saya akan mewakili data dengan 6 sisi, menggunakan notasi penyelesaian kubus "standar":
Setiap sisi adalah array 2-D X oleh X.
sumber
Saya suka gagasan @maple_shaft untuk mewakili potongan yang berbeda (kubus mini) secara berbeda: bagian tengah, tepi, dan sudut membawa 1, 2, atau 3 warna, masing-masing.
Saya akan mewakili hubungan di antara mereka sebagai grafik (dua arah), dengan ujung-ujungnya menghubungkan potongan-potongan yang berdekatan. Setiap bagian akan memiliki array slot untuk tepi (koneksi): 4 slot di bagian tengah, 4 slot di bagian tepi, 3 slot di bagian sudut. Atau, bagian tengah dapat memiliki 4 koneksi ke bagian tepi dan 4 untuk bagian sudut secara terpisah, dan / atau bagian tepi mungkin memiliki 2 koneksi ke bagian tengah dan 2 ke bagian sudut secara terpisah.
Array ini disusun sedemikian rupa sehingga iterasi pada tepi grafik selalu mewakili rotasi 'yang sama', modulo rotasi kubus. Yaitu, misalnya untuk bagian tengah, jika Anda memutar kubus sehingga wajahnya berada di atas, urutan koneksi selalu searah jarum jam. Demikian pula untuk potongan tepi dan sudut. Properti ini berlaku setelah rotasi wajah (atau begitulah menurut saya sekarang).
Deteksi kondisi yang jelas tidak dapat diatasi (bertukar / membalik tepi, bertukar sudut) mudah-mudahan mudah juga, karena menemukan potongan tipe tertentu dan orientasinya sederhana.
sumber
Bagaimana dengan node dan pointer?
Dengan asumsi selalu ada 6 wajah, dan 1 simpul mewakili 1 persegi pada 1 wajah:
Sebuah node memiliki pointer ke setiap node di sebelahnya. Rotasi lingkaran hanya memigrasikan pointer (Jumlah node / Jumlah wajah) -1 node lebih, dalam hal ini 2. Karena semua rotasi adalah rotasi lingkaran, Anda hanya membangun satu
rotate
fungsi. Itu adalah rekursif, memindahkan setiap node satu spasi, dan memeriksa apakah itu telah memindahkan mereka cukup, karena akan mengumpulkan jumlah node, dan selalu ada empat wajah. Jika tidak, tambah beberapa kali nilai yang dipindahkan dan panggil putar lagi.Jangan lupa itu ditautkan dua kali lipat, jadi perbarui juga simpul yang baru saja ditunjuk. Selalu ada Tinggi * Lebar jumlah node dipindahkan, dengan satu pointer diperbarui per node, sehingga harus ada Tinggi * Lebar * 2 jumlah pointer diperbarui.
Karena semua node menunjuk satu sama lain, hanya berjalan di lingkaran memperbarui setiap node saat Anda datang ke sana.
Ini harus bekerja untuk semua kubus ukuran, tanpa kasus tepi atau logika kompleks. Itu hanya penunjuk jalan / perbarui.
sumber
Dari pengalaman pribadi menggunakan satu set untuk melacak setiap bagian rotasi kubus bekerja dengan baik. Setiap sub kubus ada dalam tiga set tanpa ukuran kubus rubik. Jadi untuk menemukan sub kubus di suatu tempat di kubus rubik Anda hanya mengambil persimpangan tiga set (hasilnya adalah satu sub kubus). Untuk melakukan gerakan, keluarkan anak yang terkena dampak dari himpunan yang terlibat dalam hantaman dan kemudian masukkan kembali ke himpunan yang membawa mereka sebagai hasil dari perpindahan tersebut.
Kubus 4 oleh 4 akan memiliki 12 set. 6 set untuk 6 wajah dan 6 set untuk enam band yang mengelilingi kubus. Wajah masing-masing memiliki 16 sub kubus dan band masing-masing memiliki 12 sub kubus. Ada total 56 sub kubus. Setiap sub kubus menyimpan informasi tentang warna dan arah warna. Rubik cube itu sendiri adalah array 4 dengan 4 oleh 4 dengan setiap elemen memiliki informasi yang terdiri dari 3 set yang mendefinisikan sub kubus di lokasi itu.
Tidak seperti 11 jawaban lainnya, struktur data ini telah Anda gunakan persimpangan set untuk menentukan setiap lokasi sub blok di kubus. Ini menghemat pekerjaan karena harus memperbarui sub blok dekat ketika perubahan dilakukan.
sumber