การแสวงหาของโปรแกรมเมอร์คนหนึ่งเพื่อสร้างการสลับ Rubik's Cube ที่สมบูรณ์แบบได้เปิดเผยความจริงทางคณิตศาสตร์ที่น่าทึ่ง: จากความเป็นไปได้มากกว่า 43 ควินทิลเลียนแบบ มีเพียงหนึ่งเดียวที่เป็นคำตอบเฉพาะที่ตรงตามเกณฑ์ทั้งหมดสำหรับการสลับที่สมบูรณ์แบบ การค้นพบนี้ได้จุดประกายการอภิปรายที่น่าสนใจในชุมชนผู้แก้ปริศนาเกี่ยวกับความสุ่ม ข้อจำกัดทางการคำนวณ และสิ่งที่ทำให้การสลับเป็นแบบสมบูรณ์แบบอย่างแท้จริง
ความท้าทายเริ่มต้นขึ้นเมื่อโปรแกรมเมอร์พยายามสร้างการสลับที่ไม่มีสี่เหลี่ยมสองอันที่มีสีเดียวกันแตะต้องกัน - งานที่พิสูจน์แล้วว่ายากอย่างน่าประหลาดใจผ่านการพยายามด้วยมือ สิ่งที่เริ่มต้นเป็นเป้าหมายง่ายๆ ได้พัฒนาเป็นปัญหาการคำนวณที่ซับซ้อนพร้อมข้อกำหนดที่เข้มงวดหกข้อ รวมถึงการมีทุกสีบนทุกหน้า และการให้แน่ใจว่าแต่ละหน้าแสดงรูปแบบที่แตกต่างกัน
ข้อกำหนดการสลับแบบสมบูรณ์แบบ:
- ทุกสีต้องปรากฏบนทุกหน้า
- ไม่เกินสองช่องของสีเดียวกันต่อหน้า
- ไม่มีช่องสีเดียวกันสัมผัสกันแบบเคียงข้าง
- ไม่มีช่องสีเดียวกันสัมผัสกันแบบทแยงมุมบนหน้าใดๆ
- ไม่มีช่องสีเดียวกันสัมผัสกันแบบทแยงมุมข้ามหน้า
- ทุกหน้าต้องมีรูปแบบที่แตกต่างกัน
ความท้าทายทางการคำนวณเปิดเผยข้อจำกัดที่น่าประหลาดใจ
การค้นหาต้องการการตรวจสอบการจัดเรียงอย่างเป็นระบบมากกว่าการบังคับตรวจสอบความเป็นไปได้ทั้งหมด แม้จะประเมินหนึ่งล้านครั้งต่อวินาที การตรวจสอบการจัดเรียงทุกแบบจะใช้เวลามากกว่า 1.3 ล้านปี โปรแกรมเมอร์ได้พัฒนาแนวทางการสำรวจแบบต้นไม้ที่สง่างาม โดยตัดกิ่งที่เป็นไปไม่ได้ออกตั้งแต่เนื่อนๆ เพื่อลดการจัดเรียงมุม 88 ล้านแบบให้เหลือเพียง 130,632 ตัวเลือกในเวลาไม่ถึงวินาทีเดียว
สมาชิกในชุมชนได้สังเกตเห็นความขัดแย้งในผลลัพธ์เหล่านี้ ข้อจำกัดที่ออกแบบมาเพื่อให้ลูกบาศก์ดูสุ่มกลับผลิตผลลัพธ์ที่มีข้อจำกัดมากที่สุดเท่าที่เป็นไปได้ - คำตอบเดียวที่มีเพียง 48 การวางแนวที่เป็นเอกลักษณ์ สิ่งนี้เน้นให้เห็นว่าการรับรู้ความสุ่มของมนุษย์มักขัดแย้งกับความสุ่มทางคณิตศาสตร์ คล้ายกับที่ Spotify ต้องทำให้ฟีเจอร์สับเปลี่ยนของพวกเขาสุ่มน้อยลงเพื่อให้ดูสุ่มมากขึ้นสำหรับผู้ใช้
สถิติสำคัญ:
- จำนวนการจัดเรียง Rubik's Cube ที่เป็นไปได้ทั้งหมด: 43,252,003,274,489,856,000
- โซลูชันการสลับแบบสมบูรณ์แบบที่พบ: 1 โซลูชันเฉพาะ (48 การหมุน)
- เวลาในการคำนวณ: 3 วัน
- การจัดเรียงมุมที่ลดลง: 88,179,840 → 130,632 ตัวเลือก
- จำนวนการเคลื่อนไหวเพื่อแก้การสลับแบบสมบูรณ์แบบ: 18 การเคลื่อนไหว (เทียบกับ 20 การเคลื่อนไหวสูงสุดที่เป็นไปได้)
God's Number และการอภิปรายเรื่องการสลับที่สมบูรณ์แบบ
การสลับที่สมบูรณ์แบบที่ค้นพบสามารถแก้ได้ในเพียง 18 ตา ซึ่งต่ำกว่าค่าสูงสุดที่พิสูจน์แล้วคือ 20 ตาที่จำเป็นสำหรับการจัดเรียง Rubik's Cube ใดๆ (เรียกว่า God's Number) สิ่งนี้ได้นำไปสู่การอภิปรายที่น่าสนใจเกี่ยวกับสิ่งที่ถือว่าเป็นการสลับที่สมบูรณ์แบบอย่างแท้จริง
สมาชิกในชุมชนบางคนโต้แย้งว่าการสลับที่สมบูรณ์แบบควรต้องการ 20 ตาเต็มในการแก้ ซึ่งแสดงถึงความยากสูงสุดที่เป็นไปได้ การวิจัยจากปี 2010 ระบุตำแหน่งประมาณ 490 ล้านตำแหน่งดังกล่าว แม้ว่าพวกมันจะคิดเป็นน้อยกว่าหนึ่งในพันล้านของการจัดเรียงที่เป็นไปได้ทั้งหมด คนอื่นๆ แนะนำว่าการสลับที่สมบูรณ์แบบควรไม่มีชิ้นส่วนใดอยู่ในตำแหน่งเดิม ซึ่งคำตอบปัจจุบันไม่ตรงตามเงื่อนไขนี้
ลำดับการเคลื่อนไหว:
- การสร้างการสลับแบบสมบูรณ์แบบ:
U' L2 F' D' U' R' F' D2 R B2 D2 U' L2 U - การแก้การสลับแบบสมบูรณ์แบบ:
U' L2 F2 D2 U' F B2 R' D2 F' R U D L2 U - หมายเลขของพระเจ้า (จำนวนการเคลื่อนไหวสูงสุดที่จำเป็น): 20 การเคลื่อนไหว
- ตำแหน่งระยะทาง-20: ประมาณ 490 ล้านตำแหน่ง (น้อยกว่า 1 ในพันล้าน)
คณิตศาสตร์เบื้องหลังความมหัศจรรย์
กระบวนการหาคำตอบเปิดเผยข้อมูลเชิงลึกที่น่าสนใจเกี่ยวกับคณิตศาสตร์ของลูกบาศก์ โปรแกรมเมอร์ต้องคำนึงถึงข้อจำกัดสำคัญสามข้อ: การวางแนวของชิ้นส่วนมุมมีความสัมพันธ์กัน (การวางแนวของมุมสุดท้ายถูกกำหนดโดยเจ็ดมุมแรก) การวางแนวของชิ้นส่วนขอบเป็นไปตามกฎคล้ายกัน และจำนวนการสลับทั้งหมดต้องเป็นเลขคู่เพื่อให้ลูกบาศก์ยังคงแก้ได้
การอภิปรายในชุมชนยังได้สัมผัสกับการประยุกต์ใช้ในวงกว้าง ตั้งแต่การเข้ารหัสข้อมูลลงในตำแหน่งของลูกบาศก์ (แม้ว่าจะไม่ปลอดภัยพอสำหรับการเข้ารหัสสมัยใหม่) ไปจนถึงคำถามเชิงปรัชญาว่าอะไรทำให้บางสิ่งดูสุ่มเทียบกับการเป็นสุ่มทางคณิตศาสตร์
บทสรุป
ความสำเร็จทางการคำนวณนี้แสดงให้เห็นว่าข้อจำกัดทางคณิตศาสตร์สามารถผลิตผลลัพธ์ที่เป็นเอกลักษณ์อย่างไม่คาดคิด แม้ว่าการสลับที่สมบูรณ์แบบอาจไม่ดูสุ่มเท่ากับการสลับทั่วไป แต่มันแสดงถึงจุดตัดที่น่าทึ่งของการเขียนโปรแกรม คณิตศาสตร์ และทฤษฎีปริศนา ข้อเท็จจริงที่ว่าชุดข้อกำหนดเฉพาะดังกล่าวให้ผลลัพธ์เป็นคำตอบเดียวในบรรดาความเป็นไปได้ควินทิลเลียนแบบ แสดงให้เห็นถึงความเป็นระเบียบที่ซ่อนอยู่ภายในความโกลาหลที่ปรากฏ - เป็นการเตือนใจว่าในคณิตศาสตร์ ความสมบูรณ์แบบมักมาพร้อมกับข้อจำกัดที่น่าประหลาดใจ
อ้างอิง: The Rubik's Cube Perfect Scramble