Cara merepresentasikan Rubik's Cube dalam struktur data

58

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
Mel
sumber
2
Pekerjaan rumah? Atau masalah dunia nyata ...
sdg
4
Anda mungkin tertarik pada kode sumber Rubik's Cube Solver itu .
mouviciel
22
Saya cukup yakin bahwa jumlah sisi kubus harus 6
Simon Bergot
3
Saya ingin tahu melihat model Rubik's Cube diratakan sehingga saya bisa melihat semua sisi secara bersamaan. Hmm, saya tergoda untuk menulis itu sekarang. Itu bisa berupa T atau bahkan tanpa henti jika memungkinkan (saya belum memikirkan yang terakhir).
Lee Kowalkowski
6
Saya merasa tergoda untuk mengutip Eric Evans, "Model tidak benar, juga tidak salah. Mereka hanya lebih atau kurang bermanfaat" (kutipan mungkin tidak 100% benar karena dikutip dari memori)
Pete

Jawaban:

37

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!

dasblinkenlight
sumber
31
bahkan kubus Rubik yang asli tidak memiliki mini-cubes dalam
jk.
8
Ini akan berfungsi tetapi algoritme Anda mungkin akan sangat rumit untuk mengakomodasi struktur data sederhana tersebut.
maple_shaft
6
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; )
maple_shaft
7
@maple_shaft "Persis seperti apa struktur data yang lebih kuat akan memberi Anda." Saya tidak tahu tentang itu: struktur data dengan lebih banyak "struktur" untuk itu tentu akan menambah kerumitan insidental terkait dengan pengaturan, pemeliharaan, dan mengakses bagian individu dari struktur itu. Sulit untuk mengatakan apa yang akan lebih kompleks - menerapkan pergeseran jelek pada array sederhana dengan beberapa kasus sudut ditambah "perjalanan gratis" dalam mengakses sel-sel individual, atau struktur dengan pergeseran yang sedikit kurang kompleks dan bacaan yang agak lebih kompleks.
dasblinkenlight
16
Sebagai seseorang yang benar-benar menulis program untuk memanipulasi Rubik's Cube, saya mengambil pendekatan sederhana dengan menggunakan enam array dua dimensi, satu per wajah. Memang benar bahwa Anda harus menerapkan beberapa operasi mendasar pada kubus yang sedikit mengganggu, tetapi setelah itu Anda bebas untuk melupakan representasi. Itu tidak pernah menjadi masalah bagi saya. Saya sering bertanya-tanya bagaimana representasi lain akan bekerja dari perspektif kinerja, tetapi tidak pernah merasa terbebani dari perspektif pengkodean.
PeterAllenWebb
39

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:

  1. Corner Block - Ini memiliki tiga wajah warna dan tiga bagian yang berdekatan yang akan dibagikan setiap saat.

  2. 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.

  3. 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.

maple_shaft
sumber
setuju bahwa setiap blok harus memiliki properti unik. tetapi transformasi tidak akan membosankan karena Anda harus memperbarui referensi ke blok yang berdekatan dan Anda 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?
Mel
@Mel Mungkin saja melakukannya, tetapi setelah berbicara dengan dasblinkenlight, saya benar-benar berpikir bahwa pendekatannya akan kurang kompleks. Saya berharap jawabannya memiliki lebih banyak suara daripada jawaban saya. Saya tidak begitu baik dengan algoritma dan yang paling efisien, saya hanya sangat suka rubiks kubus dan mengumpulkannya (lebih dari 40 jenis berbeda dari seluruh dunia).
maple_shaft
Meskipun dasblinknenlight menjawab solusi paling sederhana, saya menghadiahkan Anda hadiah karena saya menyukai kenyataan bahwa jawaban Anda mencakup beberapa logika yang akan diperlukan untuk struktur data seperti itu, dan atribut blok yang berbeda
Rachel
Model data ini lebih benar dengan kenyataan tetapi membuat beberapa operasi sederhana yang ingin Anda lakukan lebih sulit dari yang seharusnya - Hanya mendapatkan keadaan kubus akan membutuhkan perjalanan secara rekursif melalui daftar kubus yang rumit.
Ziv
@ Ziv Benar, namun pertanyaannya adalah bertanya tentang struktur data dan belum tentu tentang algoritma.
maple_shaft
13

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.

Menggunakan struktur data, bagaimana saya bisa tahu jika kubus tertentu dalam keadaan tertentu dapat dipecahkan? Saya sendiri telah berjuang dengan pertanyaan ini dan belum menemukan jawabannya.

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.

Matthew Vines
sumber
1
Nasihat klasik "Anda tidak ingin memulai dari sini"!
Ergwun
8

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 nilai cxdan cy.

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. Posisi objek Piece akan berubah, tetapi warnanya tidak. Ini berarti Anda dapat meminta bagian merah-hijau, bertahan pada objek, melakukan beberapa rotasi, dan memeriksa objek yang sama untuk melihat di mana bagian merah-hijau berakhir.
  2. Setiap jenis Piece (tepi, tengah, sudut) memiliki pola koordinat yang unik. Untuk kubus 3x3, potongan sudut tidak memiliki nol pada vektor posisinya ( (-1, 1, 1)), tepi memiliki tepat satu nol ( (1, 0, -1)), dan potongan tengah memiliki dua nol ( (-1, 0, 0)).
  3. Matriks rotasi yang bekerja untuk kubus 3x3 akan bekerja untuk kubus NxN.

Kerugian:

  1. Multiplikasi matriks-vektor lebih lambat daripada nilai swapping dalam array.
  2. Pencarian linier untuk Potongan berdasarkan posisi. Anda harus menyimpan Potongan dalam struktur data eksternal dan memperbarui itu selama rotasi untuk pencarian waktu-konstan berdasarkan posisi. Ini mengalahkan beberapa keanggunan menggunakan matriks rotasi, dan kebocoran logika rotasi ke dalam kelas Cube Anda. Jika saya menerapkan segala jenis penyelesaian algo berbasis pencarian, saya akan menggunakan implementasi lain.
  3. Analisis pola (selama penyelesaian) tidak sebaik yang seharusnya. Sepotong tidak memiliki pengetahuan Sepotong yang berdekatan, dan analisis akan lambat karena masalah kinerja di atas.
pengguna156217
sumber
3
Saya telah menemukan bahwa implementasi semacam ini bekerja paling baik untuk mewakili kubus dalam program grafis 3D. Penggandaan matriks memungkinkan untuk menghidupkan rotasi lapisan. Lihat repo github ini untuk contoh implementasi dari pendekatan ini. Saya mempertimbangkan untuk menambahkan solver ke kubus 3D saya, saya akan membutuhkan algoritma dan struktur data dari salah satu jawaban lain.
Jonathan Wilson
5

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

ratchet freak
sumber
1
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.
jimhark
3

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).

Angelo
sumber
1
Untuk poin 2, alih-alih memulai dengan kubus acak dan memeriksa apakah itu dapat dipecahkan. Saya akan mulai dengan kubus yang dipecahkan, dan melakukan n tindakan acak pada kubus untuk membuatnya menjadi keadaan acak.
Matthew Vines
Ya, tentu saja, itu adalah cara paling sederhana untuk menghasilkan konfigurasi yang secara fisik mungkin untuk dipecahkan. Dimulai dengan konfigurasi yang sewenang-wenang dan menentukan apakah itu dapat dipecahkan jelas merupakan masalah yang terpisah tetapi terkait.
Angelo
2
Anda menduga bahwa mungkin ada "teknik mewah" untuk menentukan apakah kubus adalah salah satu yang dapat dipecahkan; sebenarnya ada. Jika Anda membongkar kubus tetapi tetap menggunakan stiker, dan kemudian memasang kembali kubus, Anda tidak harus mendapatkan kubus yang dapat dipecahkan; pada kenyataannya, peluang adalah satu hingga dua belas melawan bahwa Anda memiliki kubus yang dapat dipecahkan. Anda dapat menentukan apakah Anda berada dalam kondisi terpecahkan melalui analisis paritas tepi dan sudut; Anda sebenarnya tidak harus mencoba memecahkan kubus.
Eric Lippert
1
Berikut ini ikhtisar singkat dari tiga jenis properti pasangan kubus yang harus dipertahankan agar kubus dapat dipecahkan. ryanheise.com/cube/cube_laws.html .
Eric Lippert
1
Saya memposting pertanyaan itu di situs pertandingan stackexchange dan mendapat jawaban yang sangat bagus: math.stackexchange.com/questions/127577/…
Mel
3

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 cycleLeftdalam kode Haskell ini . Ini adalah fungsi generik yang secara siklikal mengizinkan daftar panjang 4. Kode untuk melakukan gerakan L terlihat seperti ini:

moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW

Jadi cycleLeftberoperasi pada pandangan yang diberikan oleh leftCols . Demikian pula, rotateSideCWyang merupakan fungsi generik yang memihak versi yang diputar, beroperasi pada tampilan yang diberikan oleh leftSide. Langkah lain dapat diimplementasikan dengan cara yang serupa.

Tujuan dari perpustakaan Haskell adalah untuk membuat gambar-gambar cantik. Saya pikir itu berhasil: Pustaka diagram-rubiks-kubus beraksi

Ingo Blechschmidt
sumber
2

Anda sepertinya mengajukan dua pertanyaan terpisah.

  1. Bagaimana cara mewakili kubus dengan jumlah sisi X?

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":

  • DEPAN: wajah menghadap pemecah
  • KEMBALI
  • BAIK
  • KIRI
  • NAIK
  • TURUN

Setiap sisi adalah array 2-D X oleh X.

B Tujuh
sumber
Anda dapat membeli kubus 17x17 ! Itu memang memiliki beberapa kompromi mekanis, tetapi isomorfis dengan hal yang nyata.
RBerteig
1

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).

  • Menemukan potongan-potongan milik sebuah tepi itu sepele.
  • Menemukan potongan milik wajah itu sepele.
  • Menemukan wajah yang diarahkan ke wajah tertentu, atau wajah yang berlawanan, sedang melintasi 2 atau 3 tautan yang terdefinisi dengan baik.
  • Untuk memutar wajah, perbarui koneksi semua bagian yang terhubung ke bagian tengah wajah.

Deteksi kondisi yang jelas tidak dapat diatasi (bertukar / membalik tepi, bertukar sudut) mudah-mudahan mudah juga, karena menemukan potongan tipe tertentu dan orientasinya sederhana.

9000
sumber
1

Bagaimana dengan node dan pointer?

Dengan asumsi selalu ada 6 wajah, dan 1 simpul mewakili 1 persegi pada 1 wajah:

r , g , b
r , g , b
r , g , b
|   |   |
r , g , b - r , g , b
r , g , b - r , g , b
r , g , b - r , g , b

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 rotatefungsi. 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.

Spencer Rathbun
sumber
-1

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.

martyn kuat
sumber
ini tampaknya tidak menawarkan sesuatu yang substansial atas poin yang dibuat dan dijelaskan dalam 11 jawaban sebelumnya
nyamuk