RCube

Rcube

Pemecah kubus Rubik untuk kubus yang sangat besar.

Memecahkan kubus apa pun dengan ukuran berapa pun dari 1 hingga 65536. Kode ini dapat dengan mudah dimodifikasi untuk menangani kubus yang lebih besar. Namun batasan utama adalah jumlah memori pada suatu sistem dan lamanya waktu yang diperlukan untuk dipecahkan. Selesaikan waktu tumbuh ~ n^2 yang berarti dibutuhkan 4-5 kali lebih lama untuk menyelesaikan kubus yang 2x lebih besar di setiap dimensi.

Kubus 1024 berlapis dapat diselesaikan dalam waktu sekitar 1,5 detik. Kubus berlapis 16384 dapat diselesaikan dalam waktu sekitar 20 menit.

YouTube: Memecahkan 65536 Lapisan YouTube: Memecahkan 32768 Lapisan

Gambar wajah depan kubus 32768

Menyelesaikan metode

Selesaikan pusat lalu sudut lalu tepi

Pusat

Pusat -pusat diselesaikan dalam 15 tahap di mana setiap tahap menggerakkan semua potongan warna tertentu dari satu wajah ke wajah yang diinginkan. Misalnya: panggung menggerakkan semua potongan hijau di wajah putih ke wajah hijau. Ulangi ini untuk semua warna dan wajah.

Pemecah menggunakan komutator yang dijelaskan di sini yang dapat melakukan perjalanan tengah dari satu kuadran wajah ke kesulitan di wajah lain. Properti yang sangat penting dari komutator ini adalah yang dapat dimodifikasi untuk memindahkan banyak potongan dalam satu baris pada saat yang sama. Untuk kubus yang sangat besar ini berarti dapat menggerakkan ratusan jika tidak ribuan keping dalam satu operasi. Jumlah rata -rata gerakan k = (2 * p + 5) / p di mana p adalah jumlah potongan yang dapat dipindahkan per operasi. K dengan cepat mendekati 2 saat ukuran kubus meningkat.

Sudut

The corners are solved using a basic brute force method of moving the corner into place and then rotating until the faces were oriented correctly. Will Smith dapat menjelaskan: https://www.youtube.com/watch?v=wbzkdrc9vqs

Tepi

Tepi diselesaikan dengan menggerakkan setiap pasangan tepi ke wajah depan, lalu bertukar potongan yang diinginkan dari tepi kiri ke tepi kanan. Sejumlah fungsi jika diperlukan untuk memperbaiki atau mencegah masalah paritas.

Optomisasi rotasi wajah

Rotasi wajah pada dasarnya gratis. Alih -alih memindahkan semua bagian pada wajah yang diberikan (n^2 potongan) untuk melakukan rotasi, pemecah hanya mengubah sistem koordinat yang digunakan untuk membaca/menulis ke wajah. Ini menghemat banyak pertukaran data.

 // Virtually rotate this face by q * 90 degrees 
inline void Face::RotatefaceCW ( const int q)
{
	orientation = (orientation + q) & 3 ;
}
// Gets the value of this face at coordinates r = row, c = column
inline const byte Face::GetRC ( const uint r, const uint c) const
{
	switch (orientation) {
	case 0 :
		return data[(r << BS) + c];
	case 1 :
		return data[(c << BS) + (R1 - r)];
	case 2 :
		return data[((R1 - r) << BS) + (R1 - c)];
	case 3 :
		return data[((R1 - c) << BS) + r];
	default :
		return 0 ;
	}
}

Ekspor Gambar

Kode ini mencakup eksportir gambar sederhana yang digunakan membuat setiap wajah menjadi gambar.

https://www.nayuki.io/page/tiny-png-output

https://github.com/nayuki/nayuki-web-published-code

Output PNG kecil adalah perpustakaan mandiri kecil, tersedia di C dan C ++, yang mengambil RGB8.8.8 piksel dan menulis file PNG.

Total Estimasi Pindah

Jumlah total gerakan dapat diperkirakan menggunakan formula sederhana. Dengan asumsi kubus cukup acak, kita dapat mengharapkan wajah pertama menjadi 1/6 diselesaikan dan oleh karena itu 5/6 dari potongan harus dipindahkan. Wajah kedua akan diselesaikan 1/5 dan membutuhkan 4/5 potongan untuk dipindahkan. Wajah ketiga 3/4, Wajah Keempat 2/3, Wajah Kelima 1/2 dan Wajah Terakhir akan sepenuhnya terpecahkan. Jumlah rata -rata gerakan (k) untuk memindahkan satu bagian dapat diperkirakan secara eksperimental sebagai ~ 2.1. Nilai K berkurang seiring dengan meningkatnya ukuran kubus. Nilainya tidak akan pernah kurang dari 2 karena komutator mengharuskan masing -masing bagian dipindahkan setidaknya 2 kali.

Efisiensi

Algoritma ini dioptimalkan untuk kubus yang sangat besar. Namun mengerikan untuk kubus kecil. Optimalisasi utama difokuskan pada pemecahan pusat secepat mungkin dan tidak ada pertimbangan yang diberikan untuk memecahkan tepi. Namun ukuran tepi tidak signifikan dibandingkan dengan pusat seiring dengan meningkatnya ukuran kubus. Grafik di bawah ini menunjukkan bagaimana jumlah rata -rata gerakan per bagian berkurang dengan kubus yang lebih besar. Catatan: Ini bukan grafik k. Ini adalah grafik (total gerakan) / (jumlah potongan)

Membangun dan menjalankan

• Instal CMake atau IDE dengan dukungan CMake
• Klon Repositori ini dan Direktori Terbuka di Terminal

cmake -B build -S .
cd build
cmake --build .
RCube/RCube