ผู้ใช้:Algo02/Sandbox/ปัญหาทางเดินม้าหมากรุก

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

ทฤษฎีบท

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

ประวัติความเป็นมา

ปัญหาทางเดินม้าหมากรุกได้ถูกค้นพบในศตวรรษที่ 9 โดยกวีชาวอินเดียชื่อว่า รุถถะ เขาได้เขียนบทกวีเกี่ยวกับศิลปะ แบบแผนในการเล่นม้าหมากรุกแบบครึ่งกระดานในภาษาสันสกฤต ซึ่งแตกต่างจากกวีอื่นๆที่เขียนไว้

ลีออนฮาร์ด ออยเลอร์ เป็นหนึ่งในนักคณิตศาสตร์กลุ่มแรกที่สามารถจับเทคนิคปัญหาทางเดินม้าหมากรุกได้ ซึ่งกล่าวได้ว่าเป็นเทคนิคแรกที่สมบูรณ์แบบ เทคนิคนี้ได้ถูกเขียนเป็นกฏของวานดรอฟและได้รับการเผยแพร่ครั้งแรกในปี ค.ศ.1823

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

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

ในตารางหมากรุกขนาด 8 × 8 ช่อง มีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ระบุทิศทาง แน่นอน จำนวน 26,534,728,821,064 วิธี ^[1] และมีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ไม่ระบุทิศทาง จำนวน 13,267,364,410,532 วิธี ^[2] ซึ่งมีจำนวนเป็นครึ่งหนึ่งของแบบระบุทิศทาง และในตารางหมากรุกขนาด 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(n²)

กฎของวานดอล์ฟ

รูปภาพตาราง แสดงวิธีการเดินม้าหมากรุกตามกฎของวานส์ดอล์ฟ

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

วิธีดำเนินการเพื่อประยุกต์กับกฎดังกล่าว

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

ข้อตกลง :

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

ขั้นตอนวิธี :

1. กำหนดให้ P เป็นจำแหน่งเริ่มต้นของการเดินม้าหมากรุก โดยเลือกจุดเริ่มต้นนี้แบบสุ่ม

2. กำหนดให้จุดเริ่มต้นมีเลขกำกับการเคลื่อนที่เป็น 1

3. สำหรับทุกการเคลื่อนที่ที่มีเลขกำกับการเคลื่อนที่เป็น 2 ขึ้นไป

3.1 กำหนดให้ S เป็นตำแหน่งที่เข้าถึงได้จากตำแหน่งที่ส่งเข้าไป

3.2 กำหนดตำแหน่ง P ให้เป็นตำแหน่ง ที่ตำแหน่ง S มีความสามารถที่จะการเข้าถึงได้น้อยที่สุด

3.3 ทำเครื่องหมายแสดงเลขกำกับการเคลื่อนที่บนตำแหน่ง P</nowiki>

4. คืนค่าตารางหมากรุกที่ได้รับการทำเครื่องหมายแล้ว โดยแต่ละช่องจะถูกทำเครื่องหมายด้วยเลขกำกับการเคลื่อนที่ที่มันถูกเยี่ยม

ตัวอย่างโปรแกรมในภาษาซี

http://chinmaylokesh.wordpress.com/2011/06/20/knights-tour-using-warnsdorffs-algorithm-a-heuristic-approach/

อ้างอิง

↑ 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

หมวดหมู่:หมากรุก หมวดหมู่:ทฤษฎีกราฟ

เพิ่มเติม

http://www.wou.edu/~broegb/Cs345/KnightTour.pdf

[1] Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3

[2] ttp://books.google.com/books?id=-DZjVz9E4f8C&pg=PA369&dq=532&hl=en#v=onepage&q=532&f=false

[1]

[2]