แก้รูบิคด้วยจำนวนการบิดที่น้อยที่สุด (20 God's Numbers)

ความเดิมตอนที่แล้วววว  25 ครั้งก็แก้รูบิคได้ทุกรูปแล้ว

เรื่องสืบต่อมาจากตอนที่แล้ว การตามหาจำนวนครั้งที่น้อยที่สุดที่ Rubik’s Cube ทุกลูกจะสามารถแก้ได้ ในที่สุดคำตอบก็ออกมาแล้วครับ

โดยทีมนักวิจัยกลุ่มหนึ่ง ทำงานเพื่ออธิบายเรื่องนี้ได้ใช้ God’s Algorithm และเรียกจำนวนครั้งปริศนาที่รูบิคทุกลูกจะสามารถแก้ได้ว่าเป็น God’s Number (คงหมายถึงมีพระเจ้าเท่านั้นที่รู้ในตอนนั้น)

ขอเริ่มเล่าแบบเป็นประวัติศาสตร์กันดีกว่า

---

เรื่องราวเริ่มขึ้นในฤดูใบไม้ผลิปี 1974 ที่เมือง Budapest ประเทศ ฮังการี Erno Rubik ได้สร้างของเล่นลูกบาศก์ แบบ 3*3*3 Rubik’s cube และทำให้กลายเป็น ของเล่นที่มียอดขาดดีที่สุดในโลก แต่แล้วแม้แต่คนสร้างเองก็ยังไม่ค่อยเข้าใจวิธีการแก้ของมันเลย

รูบิคคิวบ์ เป็นที่นิยมแพร่ไปยังทั่วโลกประมาณ 350 ล้านลูก ถูกขายไปหรือถ้านำมาต่อกัน เราจะได้ความยาวจากขั้วโลกเหนือ ไปยังขั้วโลกใต้เลยทีเดียว (350 ล้านนี้พอๆ กับหนังสือ Harry Potter ทุกภาคทุกเล่มรวมกันเลย)

เมื่อมีของธรรมดาของคนเราก็ต้องมีข้อสงสัย หลายข้อ และคำถามที่สำคัญนั้นคือ 
1. ไอ้รูบิคนี้มันสลับกันได้กี่หน้ากันแน่      (คำตอบ)
2. จะแก้รูบิคนี้จะต้องใช้การบิดซักกี่ครั้งกันแน่

และปัญหาก็เริ่มมีคนตั้งหน้าตั้งตาหาคำตอบมันครับ

ในปี 1980 มีคนพยายามใช้ God’ Algorithm มาใช้ในการแก้ปัญหาแบบสุ่มรูบิคมาแก้และพบว่ามี รูบิค แบบนึงที่ต้องใช้การบิดที่ 18 เป็นการบิดน้อยสุดในการแก้ปัญหา ส่วนรูปแบบที่เหลือแก้ได้โดยใช้การบิดแค่ 17 หรือต่ำกว่านั้น ทำให้เริ่มมีการจำกับเขตของ God’s Number ว่าน่าจะเป็น 18 หรือมากกว่านั้น

ต่อมาในปี 1981 Morwen Thistlethwaite ได้ทำการพิสูจน์ขอบเขตบน ของจำนวนครั้งการบิด Rubik โดยการใช้วิธีการ แบ่งขั้นตอนการหาวิธีออกเป็น สี่ขั้น และหาวิธีที่น้อยที่สุดของแบบที่ยากที่สุดออกมาเป็น 6+14+12+14 = 46

นั้นทำให้เราสามารถระบุกรอบของ God’s Number ได้เป็น ระหว่าง 18 ถึง 46 นั้นเอง

ในเดือนมกราคมปี 1995 นาย Michael Reid ได้ทำการคำนวณโดยการใช้ Kociemba’s two-phase algorithm ของนาย Herbert Kociemba ใส่คอมพิวเตอร์และคำนวณ ทำให้ได้ตัวเลขที่ดีกว่าวิธีเดิม และสามารถบอกได้ว่า จริงๆแล้ว Rubik’s Cube ทุกลูกใช้การบิดแค่ 29 ครั้งก็แก้ได้แล้ว และยังค้นพบอีกว่ามีรูบิคบางรูปต้องใช้การบิดถึง 20 ครั้งในการแก้  God’s Number จึงถูกจำกัดให้แคบลงกว่าเดิมมากเป็น 20 ถึง 29 ครั้ง

ปัญหามีนักคณิตศาสตร์อีกหลายคนพยายามแก้แต่ก็ด้วยความจำกัดด้านเทคโนโลยี ทำให้ปัญหานี้จางหายไปไม่มีการค้นพบอะไรใหม่เป็นเวลาสิบปี จนในเดือนธันวาคม ปี 2005 Silviu Radu นักคณิตศาสตร์ ใช้เทคโนโลยีที่สูงขึ้นเพื่อจะแก้ปัญหา และทำให้การรอคอยของมนุษยชาติตลอด 10 ปี มีการขยับขึ้นมาตั้งหนึ่งตัวเลข เป็น 20 ถึง 28 ครั้ง 

ต่อมาในปี 2006 เขาก็ได้พยายามอีกครั้งในการแก้ปัญหา และพิสูจน์ทำลายขอบเขตตัวเองเป็น 27 ครั้ง ในงานวิจัยชื่อ “New Upper Bounds on Rubik’s cube”  God’s Number จึงอยู่ระหว่าง 20 ถึง 27

ความพยายามของเขาทำให้มีคนเกิดสนใจในปัญหานี้มากขึ้นและปี 2007 การค้นพบครั้งใหม่ก็มาเมื่อ Dan Dunkle และ Gene Cooperman พิสูจน์ได้ว่าการบิดแค่ 26 ครั้งก็แก้ Rubik’s Cube ได้ทุกรูปแบบแล้ว ในงานวิจัยที่มีชื่อว่า “Twenty-Six Moves Suffice for Rubik’s Cube” ด้วยการใช้ Grop theory สร้าง Algorithm

ถึงปี 2008 Tomas Rokichi โปรแกรมเมอร์ ได้ตัดหน้านักคณิตศาสตร์อีกหลายคนด้วยพิสูจน์ว่าไม่มีรูบิคไหน ต้องไหนต้องใช้การบิดถึง 26 ครั้ง นั้นคือขอบเขตบนกลายเป็น 25 ครั้ง วิธีการของเขาดูได้ที่ http://mathminton.blogspot.com/2010/11/blog-post_14.html 

คอมพิวเตอร์ แห่งประวัติศาสตร์รูบิก

 God’s Number จึงอยู่ระหว่าง 20 ถึง 25 ครั้ง

ในปีเดียวกันนั้นเอง   Tomas ได้ร่วมมือกับ John Welborn เสนอผลงานอีกอันในชื่อว่า “Twenty –Two Moves Suffice for Rubik’s Cube”

โดยการเพิ่ม Algorithm อีกหนึ่งตัว

 

ในที่สุดปี 2010  หลังจากเกิดการต่อสู้แข่งขันกันพิสูจน์มาเป็นเวลาหลายปี แต่มันติดอยู่ที่เทคโนโลยีอย่างเดียว  จึงมีการรวมตัวกันแก้ปัญหาประกอบด้วย 

Tomas Rokicki

-Tomas Rokicki โปรแกรมเมอร์ชาวอเมริกัน ที่ทำงานด้านนี้มากว่าสิบปี พระเอกของงาน เจ้าของการพิสูจน์ข้างต้น

Herbert Kociemba

-Herbert Kociemba ชาวเยอรมัน เจ้าของ Algorithm ที่ใช้ พิสูจน์กันมาหลายสิบปี (พี่แกเป็นเจ้าของแต่ทำไมไม่ได้พิสูจน์ซะที) 

Morley Davidson

-Morley Davidson นักคณิตศาสตร์ แห่ง Kent State University เจ้าของผลงาน Set Cover Work และอีกหลายๆ งานเกี่ยวกับ Rubik's cube

John Dethridge

-John Dethridge วิศวกร แห่ง Google 

ได้เข้าขอความอนุเคราะห์จาก Google ของใช้คอมพิวเตอร์คิดหน่อย

Google ก็ใจดี อนุญาต ให้เข้าใช้ซูเปอร์คอมพิวเตอร์ส่วนหนึ่งได้เป็นเวลาประมาณอาทิตย์กว่าๆ

ผลสรุปก็คือจำนวนครั้งในการบิดรูบิค ที่เรารอคอย God’s Number อยู่ระหว่าง 20 ถึง 20 ครั้ง ความสำเร็จเกิดขึ้นแล้ว เรารู้ตัวเลขนั้นแล้วว สรุปก็คือ ลูกบาศ์กรูบิก ทุกลูกสามารถแก้กลับมาหน้าธรรมดาได้โดยการบิดแค่ 20 ครั้ง หรือน้อยกว่านั้น 

สถานที่มาของทั้งสี่ยอดฝีมือ แห่ง Rubik's Cube

พวกเขาทำกันได้อย่างไร

รูบิคมีจำนวนหน้าถึง 43,252,003,274,489,856,000 เราจะไปตรวจสอบทีละหน้าทีละหน้าก็คงไม่เสร็จซะทีแล้วเขาทำได้ไง

 พวกเขาได้ทำการพิสูจน์ด้วยการแบ่ง เป็นกลุ่มๆ 2,217,093,120 เซต ด้วยความสมมาตร และทำให้หดเหลือเพียง 55,882,296 เซตที่ต้องแก้ (ไม่เข้าใจก็ลองนึกดูว่าถ้าเราบิดรูบิคแบบธรรมทางขวา 90 องศา กับการบิดด้านบน 90 องศา แล้วเปลี่ยนมุมมองดูจะเห็นได้ว่ามันก็หน้าตาเหมือนกันแค่คนละสีเท่านั้นเอง)

และด้วยความใจดีของ Google ให้คอมพิวเตอร์ทำให้การคำนวณเดิมที่คอมพิวเตอร์ธรรมดาต้องใช้เวลาอยู่ที่ 35 ปี (35 CPU years) เหลือเพียงไม่กี่วัน

รูบิคที่ยากที่สุดแก้ได้ด้วยการใช้การบิดแค่ 20 ครั้งแล้วที่เหลือละ

การทำงานได้มีการเปิดเผยตารางนี้ครับ ด้านซ้ายคือ จำนวนครั้งในการบิด ด้านขวาคือรูปแบบที่ใช้การบิดแค่ทางซ้ายก็แก้ได้

อย่างที่อันแรก Distance 0 หรือ ไม่ต้องบิดก็แก้ได้เลย ก็คือรูปแบบธรรมดา แบบเดียว  Distance  1 คือบิดครั้งเดียวแล้วแก้ได้เลยนั้นก็คือ R L U D B F เป็น 6 อย่าง แต่ ละอย่างสามารถบิดได้ 90, 180, 270 องศา รวมเป็น 6*3= 18 แบบ

จากตัวเลขแสดงให้เห็นว่า 0.22870 % ใช้การบิดแค่ 15 ครั้งหรือน้อยกว่านั้นในการแก้ (ซึ่งเรียกได้ว่าเป็นรูปแบบที่ง่าย) 

แก้ได้โดย ใช้การบิด 16 ครั้ง 2.6448 %  

แก้ได้โดย ใช้การบิด 17  ครั้ง  26.7027%

แก้ได้โดย ใช้การบิด 18 ครั้ง  67.0407%

แก้ได้โดย ใช้การบิด 19 ครั้ง   3.386%

ส่วนการแก้ได้โดยใช้การบิด 20 ครั้ง น้อยเกินกว่าจะคิด เป็นเปอร์เซ็นต์

ตรงนี้เป็นส่วนสำคัญครับ ทุกครั้งที่มีการแข่งขันบิดรูบิก ทุกครั้งจะต้องมีคนมามองรูบิค ว่าอย่างให้มันตกไปยัง ส่วนที่เป็น 0.229 % ที่ง่าย หรือ ยากเกินไป แล้วตกในช่วงการบิดที่ 16-19 ครั้ง  ถึงจะยุติธรรม (ซึ่งเอาเข้าจริงคงจะเกินกันทุกคน)

สัตส่วนจำนวนหน้ารูบิคที่สามารถด้วยจำนวนการบิดแต่ละค่า

20 รูบิคที่แก้ได้ยากที่สุดในโลกกกก

ตามหลักแล้ว... พวกเขาก็ไม่ได้แสดงอะไรให้เราเห็นมากนักที่เป็นหลักฐาน มีแค่วิธีการ กับการใช้คอมพิวเตอร์ Google เขาอาจจะรวมหัวกันหลอกเราอยู่ก็ได้ เพราะงั้นถ้ามีใครหาวิธีการแก้ที่ดีกว่าของ รูบิคที่เดิมแก้ด้วยวิธีเดิม 20 ครั้งได้ ทั้งหมด เราก็จะทำลายทฤษฏี เดิมนั้นได้ (ฝันกลางวันป่าวน้อง) โดยเริ่มจากบางส่วนก่อนละกัน

F' R' F' U2 R F2 U B2 D' B R2 F2 U R2 F' D' F2 D2 F2 L2

F' R' F' U2 L U' B' L F2 B2 U L2 D F2 R' B2 L2 D2 B2 R

U F D F' R' L F U2 D2 L2 B D' B' R' F D2 B R' U' B

F R F' U2 B' R2 F2 U F' D2 R' B2 U B' U D' R' U B R

B2 F2 R U2 B2 D2 B' D B U2 L F' D' U' L2 B' F2 U' L2 F2

L U2 R' F2 U2 F2 U2 R D R B' D2 B' D U R' F U' B2 U'

R2 F2 L U2 L2 B R2 F' D2 U2 R F2 D' B U' F' L B2 U' R2

R' U' R' D' L B' R2 B2 U R' D' F U' F2 D' B' U L D B

พวกนี้คือรูบิคที่ยากที่สุดในโลก มีใครหาวิธีแก้ได้โดยการใช้วิธีน้อยกว่า 20 ครั้งละ ก็บอกผมที เดี่ยวผมช่วยแย้งให้ ฮ่าๆๆ จะได้ไหมนี้




ขอขอบคุณข้อมูลจาก
-Kociemba