ปัญหาทางเดินม้าหมากรุก
ปัญหาทางเดินม้าหมากรุก (อังกฤษ: Knight's tour) เป็นปัญหาทางคณิตศาสตร์เกี่ยวกับการเดินม้าในกระดานหมากรุก โดยม้าจะต้องเดินผ่านช่องทุกช่องบนกระดานหมากรุกเพียงช่องละหนึ่งครั้งเท่านั้นและเป็นไปตามกฎกติกาของเกมหมากรุก ถ้าการเดินม้ามีจุดเริ่มต้นเป็นช่องเดียวกับจุดสิ้นสุดจะเรียกการเดินม้านั้นว่า ”การเดินม้าแบบปิด” แต่ถ้าหากเป็นคนละช่องกันจะเรียกการเดินม้านั้นว่า “การเดินม้าแบบเปิด” ซึ่งในปัจจุบันยังไม่ทราบจำนวนวิธีในการเดินม้าแบบเปิดที่แน่ชัด ขนาดของตารางหมากรุกที่ใช้ในปัญหานี้มีหลายขนาด โดยขนาดที่ใช้โดยทั่วไปจะเป็นขนาด 8 x 8 ช่อง
ทฤษฎีบท
ปัญหาทางเดินหมากรุกเป็นตัวอย่างหนึ่งของ ปัญหาทางเดินแบบแฮมิลตันในเรื่องทฤษฎีกราฟ และปัญหาในการหาการเดินม้าหมากรุกแบบปิดนับเป็นตัวอย่างที่คล้ายคลึงกับปัญหาวัฏจักรแบบแฮมิลตัน โดยจะมีความแตกต่างจากปัญหาทางเดินแบบแฮมิลตัน คือ ปัญหาการเดินม้าหมากรุกแบบปิดนั้นมีฟังก์ชันของเวลาการทำงานเป็นเชิงเส้น หรือ สามารถบรรยายความสัมพันธ์ของฟังก์ชันในแง่ของอัตราการเติบโตได้ด้วยสัญกรณ์เชิงเส้นกำกับ O(n)
ประวัติ
ปัญหาทางเดินม้าหมากรุกได้ถูกค้นพบในศตวรรษที่ 9 โดยกวีชาวอินเดียชื่อว่า รุถถะ เขาได้เขียนบทกวีเกี่ยวกับศิลปะ แบบแผนในการเล่นม้าหมากรุกแบบครึ่งกระดานในภาษาสันสกฤต ซึ่งแตกต่างจากกวีอื่นๆที่เขียนไว้
- ลีออนฮาร์ด ออยเลอร์ เป็นหนึ่งในนักคณิตศาสตร์กลุ่มแรกที่สามารถจับเทคนิคปัญหาทางเดินม้าหมากรุกได้ ซึ่งกล่าวได้ว่าเป็นเทคนิคแรกที่สมบูรณ์แบบ เทคนิคนี้ได้ถูกเขียนเป็นกฎของวานดรอฟและได้รับการเผยแพร่ครั้งแรกในปี ค.ศ.1823
- ในศตวรรษที่ 20 กลุ่มของนักเขียน นามว่า อูลิโป ได้ใช้กฎนี้ในหลายๆรูปแบบ หนึ่งในบทความที่มีชื่อเสียงคือการเดินม้าหมากรุกบนขนาดตาราง 10x10 ช่อง ซึ่งอยู่ในหนังสือรางวัลโนเวลจอเจิส เพรก และในเกมการแข่งขันหมากรุก ระหว่าง วิสวันทาน เอนาน กับ วีสลิน โทเพลอฟ ในปี ค.ศ.2010 ซึ่งในเกมนี้ วิสวันทาน เอนาน ได้ทำการเดินม้าหมากรุกทั้ง 2 ตัว 13 ครั้งติดต่อกัน ซึ่งผู้บรรยายคิดว่า วิสวันทาน เอนาน นั้นพยายามจะพิสูจน์หรือค้นหาเทคนิคการเดินม้าหมากรุก
ทางเดินม้าหมากรุกปิด
ในตารางหมากรุกขนาด 8 × 8 ช่อง มีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ระบุทิศทาง แน่นอน จำนวน 26,534,728,821,064 วิธี และมีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ไม่ระบุทิศทาง จำนวน 13,267,364,410,532 วิธี ซึ่งมีจำนวนเป็นครึ่งหนึ่งของแบบระบุทิศทาง และในตารางหมากรุกขนาด 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. คืนค่าตารางหมากรุกที่ได้รับการทำเครื่องหมายแล้ว โดยแต่ละช่องจะถูกทำเครื่องหมายด้วยเลขกำกับการเคลื่อนที่ที่มันถูกเยี่ยม
ตัวอย่างโปรแกรมในภาษาซี
อ้างอิง
- Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3
- http://books.google.com/books?id=-DZjVz9E4f8C&pg=PA369&dq=532&hl=en#v=onepage&q=532&f=false