Rubik's Cube Solver สำหรับก้อนใหญ่มาก
แก้ลูกบาศก์ใด ๆ ทุกขนาดตั้งแต่ 1 ถึง 65536 รหัสสามารถแก้ไขได้อย่างง่ายดายเพื่อจัดการลูกบาศก์ที่ใหญ่กว่า อย่างไรก็ตามข้อ จำกัด หลักคือปริมาณของหน่วยความจำในระบบและระยะเวลาที่ใช้ในการแก้ปัญหา แก้เวลาเพิ่มขึ้น ~ n^2 ซึ่งหมายความว่าใช้เวลานานกว่า 4-5 เท่าในการแก้ปัญหาลูกบาศก์ที่ใหญ่กว่า 2x ในแต่ละมิติ
ลูกบาศก์ 1024 ชั้นสามารถแก้ไขได้ในเวลาประมาณ 1.5 วินาที ลูกบาศก์ชั้น 16384 สามารถแก้ไขได้ในเวลาประมาณ 20 นาที
YouTube: การแก้ปัญหา 65536 เลเยอร์ YouTube: การแก้ปัญหา 32768 เลเยอร์
ภาพหน้าด้านหน้าของ 32768 ลูกบาศก์
แก้ไขศูนย์จากนั้นมุมแล้วขอบ
ศูนย์ได้รับการแก้ไขใน 15 ขั้นตอนที่แต่ละขั้นตอนจะเคลื่อนที่ชิ้นส่วนทั้งหมดของสีที่แน่นอนจากใบหน้าหนึ่งไปยังใบหน้าที่ต้องการ ตัวอย่างเช่น: เวทีย้ายชิ้นสีเขียวทั้งหมดบนใบหน้าสีขาวไปยังใบหน้าสีเขียว ทำซ้ำสิ่งนี้สำหรับทุกสีและใบหน้า
ตัวแก้ปัญหาใช้ตัวเลือกที่อธิบายไว้ที่นี่ซึ่งสามารถเดินทางไปตรงกลางชิ้นส่วนจากควอดเรนต์หนึ่งของใบหน้าไปยังความคับแคบบนใบหน้าอื่น ทรัพย์สินที่สำคัญมากของผู้ใช้งานนี้คือสามารถปรับเปลี่ยนเพื่อย้ายหลายชิ้นในแถวเดียวในเวลาเดียวกัน สำหรับลูกบาศก์ที่มีขนาดใหญ่มากนั่นหมายความว่ามันสามารถเคลื่อนไหวได้หลายร้อยถ้าไม่ใช่หลายพันชิ้นในการดำเนินการเดียว จำนวนเฉลี่ยของการเคลื่อนไหว k = (2 * p + 5) / p โดยที่ p คือจำนวนชิ้นที่สามารถเคลื่อนย้ายต่อการทำงาน K เข้าใกล้ 2 อย่างรวดเร็วเมื่อขนาดลูกบาศก์เพิ่มขึ้น
มุมได้รับการแก้ไขโดยใช้วิธีการใช้กำลังเดรัจฉานพื้นฐานในการเคลื่อนย้ายมุมเข้าที่แล้วหมุนจนกว่าใบหน้าจะถูกวางอย่างถูกต้อง Will Smith สามารถอธิบายได้: https://www.youtube.com/watch?v=wbzkdrc9vqs
ขอบได้รับการแก้ไขโดยการขยับขอบทุกคู่ไปที่ใบหน้าด้านหน้าจากนั้นเปลี่ยนชิ้นที่ต้องการจากขอบซ้ายไปยังขอบด้านขวา จำนวนฟังก์ชั่นที่จำเป็นในการแก้ไขหรือป้องกันปัญหาความเท่าเทียมกัน
การหมุนของใบหน้านั้นฟรีเป็นหลัก แทนที่จะเคลื่อนย้ายชิ้นส่วนทั้งหมดบนใบหน้าที่กำหนด (N^2 ชิ้น) เพื่อทำการหมุนตัวแก้ปัญหาเพียงแค่เปลี่ยนระบบพิกัดที่ใช้ในการอ่าน/เขียนบนใบหน้า สิ่งนี้จะช่วยประหยัดการแลกเปลี่ยนข้อมูลจำนวนมหาศาล
// 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 ;
}
}รหัสนี้มีผู้ส่งออกภาพอย่างง่ายที่ใช้แสดงแต่ละใบหน้าลงในภาพ
https://www.nayuki.io/page/tiny-png-utput
https://github.com/nayuki/nayuki-web-pub-published-code
เอาต์พุต PNG ขนาดเล็กเป็นไลบรารีสแตนด์อโลนขนาดเล็กที่มีอยู่ใน C และ C ++ ซึ่งใช้ RGB8.8.8 พิกเซลและเขียนไฟล์ PNG
จำนวนการเคลื่อนไหวทั้งหมดสามารถประเมินได้โดยใช้สูตรง่ายๆ สมมติว่าคิวบ์นั้นสุ่มเพียงพอเราสามารถคาดหวังได้ว่าใบหน้าแรกจะได้รับการแก้ไข 1/6 และดังนั้น 5/6 ชิ้นจะต้องถูกย้าย ใบหน้าที่สองจะได้รับการแก้ไข 1/5 และต้องการ 4/5 ของชิ้นส่วนที่จะย้าย ใบหน้าที่สาม 3/4, ใบหน้าที่สี่ 2/3, ใบหน้าที่ห้า 1/2 และใบหน้าสุดท้ายจะได้รับการแก้ไขอย่างสมบูรณ์ จำนวนเฉลี่ยของการเคลื่อนไหว (k) เพื่อย้ายชิ้นส่วนเดียวสามารถประเมินได้ในการทดลองเป็น ~ 2.1 ค่าของ K ลดลงเมื่อขนาดของลูกบาศก์เพิ่มขึ้น ค่าไม่สามารถน้อยกว่า 2 เนื่องจากผู้ใช้งานต้องการให้แต่ละชิ้นย้ายอย่างน้อย 2 ครั้ง
อัลกอริทึมนี้ได้รับการปรับให้เหมาะสมสำหรับก้อนที่มีขนาดใหญ่มาก อย่างไรก็ตามมันแย่มากสำหรับก้อนเล็ก ๆ การเพิ่มประสิทธิภาพหลักมุ่งเน้นไปที่การแก้ศูนย์ให้เร็วที่สุดเท่าที่จะเป็นไปได้และไม่มีการพิจารณาในการแก้ขอบ อย่างไรก็ตามขนาดของขอบไม่มีนัยสำคัญเมื่อเทียบกับศูนย์เมื่อขนาดลูกบาศก์เพิ่มขึ้น กราฟด้านล่างแสดงให้เห็นว่าจำนวนการเคลื่อนที่เฉลี่ยต่อชิ้นลดลงด้วยก้อนที่ใหญ่กว่า หมายเหตุ: นี่ไม่ใช่กราฟของ K มันเป็นกราฟของ (การเคลื่อนไหวทั้งหมด) / (จำนวนชิ้น)
cmake -B build -S .
cd build
cmake --build .
RCube/RCube
