ปัญหาทางเดินม้าหมากรุก

ปัญหาทางเดินม้าหมากรุก () เป็นปัญหาทางคณิตศาสตร์เกี่ยวกับการเดินม้าในกระดานหมากรุก โดยม้าจะต้องเดินผ่านช่องทุกช่องบนกระดานหมากรุกเพียงช่องละหนึ่งครั้งเท่านั้นและเป็นไปตามกฎกติกาของเกมหมากรุก ถ้าการเดินม้ามีจุดเริ่มต้นเป็นช่องเดียวกับจุดสิ้นสุดจะเรียกการเดินม้านั้นว่า ”การเดินม้าแบบปิด” แต่ถ้าหากเป็นคนละช่องกันจะเรียกการเดินม้านั้นว่า “การเดินม้าแบบเปิด” ซึ่งในปัจจุบันยังไม่ทราบจำนวนวิธีในการเดินม้าแบบเปิดที่แน่ชัด ขนาดของตารางหมากรุกที่ใช้ในปัญหานี้มีหลายขนาด โดยขนาดที่ใช้โดยทั่วไปจะเป็นขนาด 8 x 8 ช่อง

ทฤษฎีบท
ปัญหาทางเดินหมากรุกเป็นตัวอย่างหนึ่งของ ปัญหาทางเดินแบบแฮมิลตันในเรื่องทฤษฎีกราฟ และปัญหาในการหาการเดินม้าหมากรุกแบบปิดนับเป็นตัวอย่างที่คล้ายคลึงกับปัญหาวัฏจักรแบบแฮมิลตัน โดยจะมีความแตกต่างจากปัญหาทางเดินแบบแฮมิลตัน คือ ปัญหาการเดินม้าหมากรุกแบบปิดนั้นมีฟังก์ชันของเวลาการทำงานเป็นเชิงเส้น หรือ สามารถบรรยายความสัมพันธ์ของฟังก์ชันในแง่ของอัตราการเติบโตได้ด้วยสัญกรณ์เชิงเส้นกำกับ O(n)

 ประวัติ 
ปัญหาทางเดินม้าหมากรุกได้ถูกค้นพบในศตวรรษที่ 9 โดยกวีชาวอินเดียชื่อว่า รุถถะ เขาได้เขียนบทกวีเกี่ยวกับศิลปะ แบบแผนในการเล่นม้าหมากรุกแบบครึ่งกระดานในภาษาสันสกฤต ซึ่งแตกต่างจากกวีอื่นๆที่เขียนไว้ 
 ลีออนฮาร์ด ออยเลอร์ เป็นหนึ่งในนักคณิตศาสตร์กลุ่มแรกที่สามารถจับเทคนิคปัญหาทางเดินม้าหมากรุกได้ ซึ่งกล่าวได้ว่าเป็นเทคนิคแรกที่สมบูรณ์แบบ เทคนิคนี้ได้ถูกเขียนเป็นกฎของวานดรอฟและได้รับการเผยแพร่ครั้งแรกในปี ค.ศ.1823 
 ในศตวรรษที่ 20 กลุ่มของนักเขียน นามว่า อูลิโป ได้ใช้กฎนี้ในหลายๆรูปแบบ หนึ่งในบทความที่มีชื่อเสียงคือการเดินม้าหมากรุกบนขนาดตาราง  10x10 ช่อง ซึ่งอยู่ในหนังสือรางวัลโนเวลจอเจิส เพรก และในเกมการแข่งขันหมากรุก ระหว่าง วิสวันทาน เอนาน กับ วีสลิน โทเพลอฟ ในปี ค.ศ.2010 ซึ่งในเกมนี้ วิสวันทาน เอนาน ได้ทำการเดินม้าหมากรุกทั้ง 2 ตัว 13 ครั้งติดต่อกัน ซึ่งผู้บรรยายคิดว่า วิสวันทาน เอนาน นั้นพยายามจะพิสูจน์หรือค้นหาเทคนิคการเดินม้าหมากรุก 

ทางเดินม้าหมากรุกปิด
ในตารางหมากรุกขนาด 8 × 8 ช่อง มีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ระบุทิศทาง แน่นอน จำนวน 26,534,728,821,064 วิธี Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3 และมีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ไม่ระบุทิศทาง จำนวน 13,267,364,410,532 วิธี http://books.google.com/books?id=-DZjVz9E4f8C&pg=PA369&dq=532&hl=en#v=onepage&q=532&f=false ซึ่งมีจำนวนเป็นครึ่งหนึ่งของแบบระบุทิศทาง
และในตารางหมากรุกขนาด 6x6 มี  วิธีการเดินม้าหมากรุกแบบปิดซึ่งไม่ระบุทิศทางจำนวน 9,862 วิธี  การเดินม้าหมากรุแบบปิดมีกรณีที่เล็กที่สุดคือ กรณี 1 × 1 (เป็นทฤษฎีบทแทรกของทฤษฎีนี้)

 ทฤษฎีบทของชเวงค์ 
สำหรับทุกตารางหมากรุกขนาด m × n โดยที่ m น้อยกว่า n แล้วเราจะสามารถหาวิธีการเดินม้าหมากรุกแบบปิดได้ ยกเว้นตารางหมากรุกดังกล่าวจะสอดคล้องกับเงื่อนไขต่อไปนี้อย่างน้อย 1 เงื่อนไข 
 m และ n เป็นจำนวนคี่ทั้งคู่ โดยที่ m≠1 และ n≠1
 m = 1, 2, หรือ 4 โดยที่ m≠1 และ n≠1
 m = 3 และ n = 4, 6, หรือ 8

เงื่อนไขที่1

สาเหตุที่เงื่อนไขนี้ไม่สามารถทำการเดินแบบปิดได้ เนื่องจากจำนวนช่องของสีบนตารางที่ไม่เท่ากัน  กล่าวคือ ตารางหมากรุปแบบมาตรฐานจะมีสี 2 สี  ได้แก่สีดำและสีขาว ซึ่งม้าหมากรุกสามารถเดินได้ทั้ง 2 สี คือ จากช่องสีดำไปช่องสีขาวและจากช่องสีขาวไปช่องสีดำ แต่ในการเดินแบบปิด ม้าจะต้องเดินบนช่องขาวและช่องดำเป็นจำนวนเท่ากัน และถ้าจำนวน m และ n เป็นจำนานคี่ทั้งคู่ จำนวนช่องทั้งหมดบนตารางหมากรุกจะเป็นเลขคี่ ซึ่งจะมีช่องขาวและช่องดำไม่เท่ากัน  ตัวอย่างเช่น ในตารางหมากรุกขนาด 5x5  จะมีสีหนึ่ง 13ช่อง และอีกสีหนึ่ง 12ช่อง สีที่ต่างกันมีจำนวนช่องไม่เท่ากัน ดังนั้นไม่มีวิธีที่จะเดินม้าหมากรุกแบบปิด กรณีนี้จะมีเพียงการเดินม้าแบบเปิดได้เท่านั้น

เงื่อนไขที่ 2

เมื่อกระดานข้างที่สั้นกว่ามีความกว้างเป็น 1,2 หรือ 4 จะไม่สามารถการเดินแบบปิดได้ และเมื่อ m=1 หรือ 2 จะไม่สามารถเดินแบบปิดได้ เนื่องจากม้าจะไม่สามารถเดินไปในทุกๆช่องได้ (ยกเว้นตารางหมากรุกขนาด 1x1) และเมื่อ m=4 ก็ไม่สามารถเกิดการเดินแบบปิดได้เช่นกัน โดยการพิสูจน์จากสีในตารางหมากรุก
เริ่มพิสูจน์โดยการสมมุติให้ตาราง 4xn สามารถเดินม้าแบบปิดได้ และให้ A1  เป็นเช็ตของช่องสีดำและ A2 เป็นเช็ตของช่องสีขาว แล้วถ้ามีช่องสีขาวและช่องสีดำ สลับกันบนกระดานหมากรุก พิจารณาจากรูปทางด้านขวา กำหนดให้ B1  เป็นเช็ตของช่องสีเขียวและ B2 เป็นเช็ตของช่องสีแดง จากรูปทางด้านขวาจะสังเกตได้ว่าจำนวนของช่องสีเขียวและสีแดงมีจำนวนเท่ากัน และสมมุติให้ม้าเดินจากช่องใน B1  ม้าจะต้องเดินไปช่องใน B2 และม้าจะต้องเดินบนทุกๆช่อง โดยจะเดินไม่ซ้ำช่องกัน และเมื่อม้าอยู่บนช่อง B2 ม้าจะต้องเดินไปในช่องของ B1 ต่อไป (ในทางกลับกัน ม้าต้องเดินไปบนช่อง B1 สองครั้งในภายหลัง)
ถ้าเราปฏิบัติตามการสมมุติข้างต้นเราจะพบข้อขัดแย้งดังนี้

 การเดินครั้งแรก ม้าจะเดินไปในช่องของ A1 และ B1 ถ้าไม่ได้เดินแบบนี้ เราสามารถเปลี่ยนเป็น B1 และ B2 ก็จะถูกเช่นเดียวกัน
 การเดินครั้งที่ 2 จะเป็นสมาชิกในเช็ตของ A2 และ B2.
 การเดินครั้งที่ 3 จะเป็นสมาชิกในเช็ตของ A1 และ B1.
 การเดินครั้งที่ 4 จะเป็นสมาชิกในเช็ตของ A2 และ B2.
 และอีกมากมาย
ดังนั้นเช็ต A1  จะมี สมาชิกเหมือนเช็ต B1  และเช็ต A2 มีสมาชิกเหมือนเช็ต B2  แต่ว่า การสรุปข้างต้นนั้นไม่ถูกต้องเสมอไป ถ้าสีแดงและสีเขียวจากรูปด้านบน ไม่เหมือนกระดานหมากรุก เช็ตของสีแดงจะไม่เหมือนเช็ตของสีดำ
ดังนั้นเราสามารถสรุปได้ว่าไม่สามารถเดินม้าแบบปิดในตาราง 4xn ได้ สำหรับ ทุกๆค่าของ n

เงื่อนไขที่ 3

เงื่อนไขนี้สามารถพิสูจน์ได้จากการแตกเป็นหลายๆวิธี และการสร้างการเดินแบบแบบปิด โดยใช้ตารางแบบ 3xn (n=4,6,8) จะไม่สามารถทำได้ ตารางหมากรุกแบบ 3xn โดย n เป็นจำนวนคู่และมีค่ามากกว่า 8 จะสามารถเกิดการเดินแบบปิดได้โดยอุปนัย

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

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

 วิธีการแก้ปัญหาโดยการแบ่งแยกและเอาชนะ 
เริ่มจากการแบ่งส่วนของตารางหมากรุกเป็นส่วนย่อยๆ พิจารณาหาวิธีในแต่ละส่วนย่อย แล้วจึงนำแต่ละส่วนย่อยมาประกอบกัน ซึ่งวิธีการนี้สามารถบรรยายความสัมพันธ์ของฟังก์ชันในแง่ของอัตราการเติบโตได้ด้วยสัญกรณ์เชิงเส้นกำกับ O(n2)

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

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

ข้อตกลง :
 ตำแหน่ง Q จะเข้าถึงจากตัวแหน่ง P ได้ ถ้าหากว่า P สามารถเคลื่อนที่ไปยัง Q ได้ด้วยการเคลื่อนที่เพียงครั้งเดียว และ Q ยังเป็นตำแหน่งที่ยังไม่ได้เยี่ยม
 ความสามารถในการเข้าถึงตำแหน่ง P เท่ากับ จำนวนของตำแหน่งที่สามารถเข้าถึงได้จากตำแหน่ง P

ขั้นตอนวิธี :
1. กำหนดให้ P เป็นจำแหน่งเริ่มต้นของการเดินม้าหมากรุก โดยเลือกจุดเริ่มต้นนี้แบบสุ่ม
2. กำหนดให้จุดเริ่มต้นมีเลขกำกับการเคลื่อนที่เป็น 1
3. สำหรับทุกการเคลื่อนที่ที่มีเลขกำกับการเคลื่อนที่เป็น 2 ขึ้นไป
3.1 กำหนดให้ S เป็นตำแหน่งที่เข้าถึงได้จากตำแหน่งที่ส่งเข้าไป
3.2 กำหนดตำแหน่ง P ให้เป็นตำแหน่ง ที่ตำแหน่ง S มีความสามารถที่จะการเข้าถึงได้น้อยที่สุด
3.3 ทำเครื่องหมายแสดงเลขกำกับการเคลื่อนที่บนตำแหน่ง P
4. คืนค่าตารางหมากรุกที่ได้รับการทำเครื่องหมายแล้ว โดยแต่ละช่องจะถูกทำเครื่องหมายด้วยเลขกำกับการเคลื่อนที่ที่มันถูกเยี่ยม

ตัวอย่างโปรแกรมในภาษาซี
 https://web.archive.org/web/20110912213543/http://chinmaylokesh.wordpress.com/2011/06/20/knights-tour-using-warnsdorffs-algorithm-a-heuristic-approach/ 

อ้างอิง

หมวดหมู่:หมากรุก
หมวดหมู่:ทฤษฎีกราฟ
หมวดหมู่:ปัญหาทางคณิตศาสตร์

 ดูเพิ่ม 
 http://www.wou.edu/~broegb/Cs345/KnightTour.pdf