เดินม้าหมากรุก 64 ตา

    จำได้ว่าเมื่อสมัยที่ผมอยู่มัธยม 1 ผมชอบเล่นหมากรุกมาก ขนาดอาหารกลางวันไม่มีตกถึงท้อง ทุกเที่ยงต้องไปขลุกอยู่ที่โรงยิมชั้นสองซึ่งเป็นห้องหมากรุก เล่นกันมันเพลินจนลืมเวลาอยู่บ่อยๆ ใครจะไปเตะบอลหรือเล่นบาสอยู่ตรงไหนผมไม่สนมุ่งหมากรุกอย่างเดียว เที่ยงวันนั้นก็เหมือนกับวันปกติทุกวัน ผมมาเล่นเหมือนเดิม วันนั้นไอ้อีที(ชื่ออาจตั้งผิด แต่ฉายาไม่มีวัน) ซึ่งชื่อเสียงด้านโม้ชองมันลือเลื่อง มันมาบอกในก๊วนว่า "พวกมึงลองดูสิ เอาม้านี้ตั้งตรงไหนก็ได้ แล้วลองเดินดู จะเดินไปไหนก็ได้แต่ห้ามซ้ำตาที่เคยเดิน ลองเดินดูให้ครบ 64 ตา พวกมึงแน่จริงลองทำดู ปู่กูนะโว้ยเคยทำได้มาแล้ว"

    ก็คงไม่ต้องบอกเป็นรอบสอง เรามันพวกชอบเล่นหมากกลจำพวก พระรามเข้าโกศฐ์ หรือ ศรพรหมมาศ อยู่แล้ว พวกเรารู้ซึ้งถึงลูกเล่นของม้าจากหมากกลเหล่านี้ นับประสาอะไรกับแค่เดินม้า 64 ตา ไม่น่าจะยาก แต่เชื่อรึเปล่าครับ เราลองกันอยู่นาน จนยอมแพ้ทำยังไงมันก็ไม่ยอมถึง 64 ซักที จนพวกเราพูดเป็นเสียงเดียวกันไอ้อีทีมันโม้แน่นอนว่าปู่มันทำได้ แล้วผมก็ลืมมัน จนกระทั่ง

    เมื่อวันตรุษจีนที่ผ่านมา เป็นวันหยุดของบริษัทที่ผมทำงานอยู่ ผมเลยมีเวลาว่าง วันนั้นผมเอา web ขึ้นเรื่องสอนเขียน C# ไปจนเกือบจบส่วนแรกแล้ว ผมเลยคิด ว่าน่าจะมีการนำเอาสิ่งที่ผมสอนทั้งหมด มาเขียนเป็นโปรแกรมเล็กๆ ซักตัว ผมเลยนึกถึงเรื่องม้าหมากรุก ตอนนั้นผมตื่นเต้นมากครับ เพราะจะได้พิสูจน์ซักทีว่าไอ้อีทีมันขัวร์หรือมั่วนิ่ม ผมใช้เวลาอยู่วันหนึ่ง ป้ำกับมัน และแล้วในที่สุดผมก็ได้โปรแกรม แต่ก่อนอื่นที่ผมจะพูดถึงโปรแกรม ผมขอใช้พื้นที่ซักหน่อยอธิบายว่า ม้าหมากรุกมันเดินอย่างไร คุณจะได้รู้ว่าโปรแกรมมันทำอะไรบ้าง

ตารางหมากรุกปกติอมีขนาด 8x8 ช่อง ซื่งก็คือ 64 ช่องนั้นเอง ผมต้องเอาม้ามาเดินจากจุดหนึ่งไปยังอีกจุดหนึ่ง ซึ่งม้ามีลักษณะการเดินแบบนี้ครับ

     
     
       
     
     

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

ผมเริ่ม Run โปรแกรม แต่เวลาผ่านไปหนึ่งชั่วโมง โปรแกรมก็ยังเงียบไม่แสดงผลออกมาว่า ไอ้อีทีมันพูดจริงหรือโกหก ผมก็นึกในใจแล้วว่า C# มันคงทำงานช้า ไม่ไหวไม่สมราคาคุย ขอไปนอนก่อน ตื่นเช้ามา มาดูอีกที ก็ยังเงียบอยู่ ไม่เป็นไรผมไปทำธุระข้างนอกก่อน กลับมานะคงได้คำตอบ พอกลับมาสองทุ่ม ก็เหมือนเดิมครับ คือเงียบ เวลาผ่านไป 26 ชั่วโมงมันยังเงียบอยู่ ผมเลยใช้คณิตศาสตร์คำนวนดูว่า ผมจะต้องใช้เวลากี่ชั่วโมง ถ้าไงจะได้หาเรื่องเขียนบทต่อไปเกี่ยวกัน Network ซะเลยให้หลายเครื่องช่วยกันหา

ผมเริ่มจากคำนวณจำนวนรอบต่อหนึ่งวินาที เครื่องผม ผมว่าก็ไม่ช้านะครับ Intel PIII 733Mhz Memory ก็ตั้ง 256 MB เห็นว่า Harddisk ไม่มีการทำงานเลยตลอดการ Run แสดงว่า Memory พอ ผมปรับโปรแกรมให้มันลองจับเวลาดู ปรากฏว่าตัวเลขความเร็วอยู่ในเกณฑ์ดีเยี่ยมครับ คือ 6 ล้าน moves หนึ่งวินาที (แต่ละ moves คือการเคลื่อนที่ม้าจากข่องหนึ่งไปยังอีกช่องหนึ่ง) ที่เหลือก็คือต้องคำนวณออกมาให้ได้ว่า กรณีแย่ที่สุด(worst case)คือไม่มีคำตอบนั้น ต้องทดลองทั้งหมดกี่ moves แล้วผมก็จะเอาตัวเลขจำนวน moves ต่อวินาทีมาหาร จะได้รู้กันว่าถ้าใช้เครื่องเดียวต้องใช้เวลากี่วัน

หลักการในการคำนวณหากรณีที่แย่ที่สุดคือ การดูความเป็นไปได้ในแต่ละช่องที่จะไปช่องอื่น เต็มที่ได้ 8 ตามรูปแบบการเคลื่อนที่ข้างบน แต่ช่องที่ชิดด้านข้างมากก็จะต่ำกว่า 8 เอาค่าแต่ละช่อง แล้วลบด้วยหนึ่ง เพราะว่ากลับไปทางเดิมไม่ได้ เอาค่าเหล่านี้มาคุณกัน ทีแรกผม modify โปรแกรมให้ทำการคำนวณ การคูณทั้งหมดเข้าด้วยกัน ผลลัพธ์เป็นศูยน์ตลอด การที่ทำให้ค่าเป็น 0 ได้มันต้องมีตัวใดตัวหนึ่งเป็นศูยน์ทำให้ผลคูณเป็นศูยน์ ผมหาอยู่เป็นชั่วโมงก็หาไม่เจอ จนกระทั่งผมต้องนั่งไล่ดูทีละ step จนเจอคำตอบครับมัน Overflow มันเลยได้ค่าเป็น 0 ผมก็ยังงงนะครับ ผมใช้ตัวแปรชนิด ulong ซึ่งสามารถรองรับตัวเลขได้ถึง 18,446,744,073,709,551,615 แต่แล้วผมก็ถึงบางอ้อครับ

เมื่อตอนเป็นเด็ก ผมเคยอ่านหนังสือประเภทเลขคณิตคิดสนุกอะไรทำนองนั้น มีโจทย์อยู่ข้อหนึ่งครับ ว่ามีชายคนหนึ่งทำความดีความชอบมาก จนพระราชาอินเดียโบราณประทานรางวัลให้ขออะไรก็ได้ ชายคนนั้นขอข้าวสารครับ แต่มีเงื่อนไขว่า ใน 64 ช่องหมากรุก ช่องแรกให้ใส่เมล็ดข้าวเข้าไปหนึ่งเมล็ด และช่องที่สองเป็นสองเท่าของช่องแรกคือ 2 เมล็ด และช่องที่สามเป็นสองเท่าของช่องที่สองซึ่งก็คือสี่ ทำอย่างนี้ไปจนครบช่องที่ 64 พระราชาก็ตรัสว่าทำไมเจ้าช่างมักน้อยขนาดนี้ แต่แล้วก็ต้องตกพระทัยครับ เมื่อข้าวทั้งท้องพระคลังเอามาใช้ทั้งหมด ยังไม่ได้ครึ่งของตารางหมากรุกเลย ผมไม่เคยรู้หรอกว่า ถ้าเติมให้เต็มช่องหมากรุกจริงๆ แล้วมันเท่าไหร่ แต่ในหนังสือบอกว่า ถ้าเอาเมล็ดข้าวมาเรียงกัน มันจะได้ระยะทางจากโลกไปถึงดาวอังคาร แล้ววนกลับมายังโลกได้สองรอบ เอ! แล้วจริงๆ มันเท่าไหร่กันนะ

ผมติดไว้ให้คุณคิดเป็นการบ้านเอาเองสำหรับปัญหาเรื่องข้าว ส่วนผม จะแสดงให้คุณดูว่า ตัวคูณทั้ง 64 ตัวมันมีอะไรบ้าง ดังนี้ครับ

1*2*3*3*3*3*2*1
2*3*5*5*5*5*3*2
3*5*7*7*7*7*5*3
3*5*7*7*7*7*5*3
3*5*7*7*7*7*5*3
3*5*7*7*7*7*5*3
2*3*5*5*5*5*3*2
1*2*3*3*3*3*2*1

ซึ่งถ้านำมาคูณกันทั้งหมดจะได้

452,640,874,646,878,170,289,066,4062,500,000,000

ซึ่ง ถ้าวินาทีหนึ่ง เครื่องผมทำได้ 10 ล้าน moves ต่อหนึ่งวินาที  ดังนั้นผมต้องใช้

8,611,888,787,041,061,078

หน่วยเป็นปีครับ!

ซึ่งผมยอมแพ้แล้วครับ ต่อให้ใช้เครื่องคอมพิวเตอร์ทั่วโลกมาช่วยกันก็ไม่มีทางครับ น่าเสียดาย ปริศนายังคงเป็นปริศนาอยู่ ถ้าคุณคิดว่าคุณมีวิธีใดๆ ที่คิดว่าดีกว่านี้ เร็วก็นี้ก็ email มาคุยกันได้ครับ

Note เกี่ยวกับ Algorithm

    หลักการที่โปรแกรมนี้ใช้คือ การทำ Deep First Search โดยการพยายามให้วางตัวม้าให้ได้มากที่สุด ถ้าไปต่อไม่ได้ ก็ทำการ backtracking กลับไปช่องก่อนหน้า แต่ละครั้งที่ move ก่อน move แต่ละช่องนั้นจะทำการบันทึกว่าไปทิศใด ถ้ากลับมาที่ช่องนั้นแสดงว่าไม่สำเร็จให้พยายามลองทิศอื่น แต่ถ้าทุกทิศแล้วไม่สำเร็จก็กลับไปช่องก่อนหน้า ดังนั้นโปรแกรมจึงมีสองสถานะคือไปถึง 64 ช่อง หรือกลับมาเป็น 0 เท่านั้น

    โปรแกรมนี้ผมสามารถใช้ Recursive ได้ แต่ผมเลือกที่จะไม่ใช้ เพราะถ้าเรา implement เองมันจะได้ความเร็วที่สูงกว่า ตัวแปรผมพยายามใช้ให้เหมาะสมกับสิ่งที่เก็บ

Source Code

    Source Code C#    horse.cs

    Source Code Java   Start.java   Horse.java

ผลลัพธ์จากการ Run Program

     ในเมื่อผมไม่สามารถหา 64 ตาได้ ผมจึงปรับโปรแกรมจาก 64 เป็น 63 ตา ผลลัพธ์ก็ได้ตามข้างล่างครับ โปรแกรมที่ link ข้างขนนั้นปรับเป็น ุ63 ตาเรียบร้อยแล้ว (ถ้าต้องการ 64 ให้ run จนโลกถล่ม ก็ลองหาเลข 63 ในโปรแกรม แล้วแก้เป็น 64) นอกจากเวลาเริ่มต้นและจบแล้ว ผมยังแสดงผลลัพธ์ให้ดูอีก ผมเริ่มตาแรกที่มุมซ้ายบนครับ จากนั้นคุณลองไล่ดูนะครับว่ามันได้ 63 ตา ตามก็การเดินม้าจริงหรือเปล่า จะสังเกตได้ว่าที่มุมขวาล่างมีเลข 63 และเหนือขึ้นไปจะมีเลข 00 ซึ่งนั่นก็คือตาที่ 64 แต่โปรแกรมทำไม่สำเร็จครับ ไม่สามารถเดินแบบม้าจากตาที่ 63 ไปยัง 00 ได้

DOS Prompt

C:\horse>csc /o /debug- horse.cs
Microsoft (R) Visual C# Compiler Version 7.00.9030 [CLR version 1.00.2204.21]
Copyright (C) Microsoft Corp 2000. All rights reserved.


C:\horse>horse
Start Time: 2001-02-08T10:56:38
End Time : 2001-02-08T10:57:14
Total Move: 236290480


Result:
01 22 53 20 03 18 09 16
54 43 02 23 08 15 04 13
41 46 21 52 19 12 17 10
44 55 42 47 24 07 14 05
59 40 45 32 51 28 11 26
56 33 58 37 48 25 06 29
39 60 35 50 31 62 27 00
34 57 38 61 36 49 30 63

C:\horse>

 ใช้ไป 36 วินาที ดังนั้นความเร็วที่ทำได้คือ 6,563,624.4 moves ต่อหนึ่งวินาที 

DOS Prompt

C:\horse>javac -O Start.java Horse.java

C:\horse>java Start
Start Time: Thu Feb 08 11:13:22 GMT+07:00 2001
End Time : Thu Feb 08 11:14:11 GMT+07:00 2001
Total Move: 236290480


Result:
01 22 53 20 03 18 09 16
54 43 02 23 08 15 04 13
41 46 21 52 19 12 17 10
44 55 42 47 24 07 14 05
59 40 45 32 51 28 11 26
56 33 58 37 48 25 06 29
39 60 35 50 31 62 27 00
34 57 38 61 36 49 30 63

C:\horse>

ใช้ไป 49 วินาที ดังนั้นความเร็วที่ทำได้คือ 4,822,254.6 moves ต่อหนึ่งวินาที

Java ที่ใช้เป็นรุ่น 1.3 Standard Edition

Update 30 เมษายน 2001

    ผมได้รับ email มาจากคุณ Raptor ว่ามีคนแก้ปัญหานี้ได้แล้วโดยคุณ Natjira Honda ปรากฏว่าได้จริงๆ ครับ โดยที่กำหนด จุดเริ่มต้นให้ต่างออกไปและกำหนดทิศทางก่อนหลังให้เปลี่ยนไปดังนี้ครับ

ลำดับในการทดลอง เปลี่ยนจาก
    private static sbyte[,] cabytNextXY = { {0,0}, {-1, -2}, {+1, -2}, {+2, -1}, 
    {+2, +1}, {+1, +2}, {-1, +2}, {-2, +1}, {-2, -1}};

เป็น
    private static sbyte[,] cabytNextXY = {  {0,0}, {-1, -2}, {-2, -1}, {+1, -2}, 
    {+2, -1}, {-1, +2}, {-2, +1}, {+1, +2}, {+2, +1} };

และเปลี่ยนจุดเริ่มจาก 1,1   
   
CurrentHorse = aHorseBoard[1, 1];
มาเป็น 
    CurrentHorse = aHorseBoard[2, 3];

DOS Prompt

C:\cs>csc /o /debug- chess.cs
Microsoft (R) Visual C# Compiler Version 7.00.9030 [CLR version 1.00.2204.21]
Copyright (C) Microsoft Corp 2000. All rights reserved.


C:\cs>chess
Start Time: 2001-04-30T17:12:53
End Time : 2001-04-30T17:13:09
Total Move: 103940395


Result:
02 15 06 13 04 23 20 29
07 12 03 22 19 28 25 64
16 01 14 05 24 21 30 27
11 08 37 18 43 26 63 32
38 17 10 59 36 31 42 53
09 58 47 44 41 52 33 62
46 39 56 49 60 35 54 51
57 48 45 40 55 50 61 34

C:\cs>

    ใช้เวลาไปเพียง 16 วินาที การเลือกตำแหน่งที่ถูกต้องและลำดับในการทดลองมีผลมากครับ ดีครับช่วยกันคิด วันนี้ผมชักรู้สึกดีๆ กับเพื่อนเก่าของผมคือไอ้อีทีว่าปู่ของมันแน่จริงๆ 

    เด็กยุคใหม่นี่มีเก่งๆ เยอะนะครับ

Introduction to .Net Framework |.Net Framework Based Class Library | C# Tutorial | Windows Apps with C# |Why We Are Here | Who We Are | Download  | Playground's Main Page