ผลต่างระหว่างรุ่นของ "ปัญหาทางเดินม้าหมากรุก"

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
OctraBot (คุย | ส่วนร่วม)
autoCategory
Nullzerobot (คุย | ส่วนร่วม)
โรบอต: แทนที่คำ
บรรทัด 9:
==ประวัติความเป็นมา==
ปัญหาทางเดินม้าหมากรุกได้ถูกค้นพบในศตวรรษที่ 9 โดยกวีชาวอินเดียชื่อว่า รุถถะ เขาได้เขียนบทกวีเกี่ยวกับศิลปะ แบบแผนในการเล่นม้าหมากรุกแบบครึ่งกระดานในภาษาสันสกฤต ซึ่งแตกต่างจากกวีอื่นๆที่เขียนไว้ <br />
: ลีออนฮาร์ด ออยเลอร์ เป็นหนึ่งในนักคณิตศาสตร์กลุ่มแรกที่สามารถจับเทคนิคปัญหาทางเดินม้าหมากรุกได้ ซึ่งกล่าวได้ว่าเป็นเทคนิคแรกที่สมบูรณ์แบบ เทคนิคนี้ได้ถูกเขียนเป็นกฏกฎของวานดรอฟและได้รับการเผยแพร่ครั้งแรกในปี ค.ศ.1823 <br />
: ในศตวรรษที่ 20 กลุ่มของนักเขียน นามว่า อูลิโป ได้ใช้กฏกฎนี้ในหลายๆรูปแบบ หนึ่งในบทความที่มีชื่อเสียงคือการเดินม้าหมากรุกบนขนาดตาราง 10x10 ช่อง ซึ่งอยู่ในหนังสือรางวัลโนเวลจอเจิส เพรก และในเกมการแข่งขันหมากรุก ระหว่าง วิสวันทาน เอนาน กับ วีสลิน โทเพลอฟ ในปี ค.ศ.2010 ซึ่งในเกมนี้ วิสวันทาน เอนาน ได้ทำการเดินม้าหมากรุกทั้ง 2 ตัว 13 ครั้งติดต่อกัน ซึ่งผู้บรรยายคิดว่า วิสวันทาน เอนาน นั้นพยายามจะพิสูจน์หรือค้นหาเทคนิคการเดินม้าหมากรุก <br />
 
==ทางเดินม้าหมากรุกปิด==
บรรทัด 29:
 
:เมื่อกระดานข้างที่สั้นกว่ามีความกว้างเป็น 1,2 หรือ 4 จะไม่สามารถการเดินแบบปิดได้ และเมื่อ m=1 หรือ 2 จะไม่สามารถเดินแบบปิดได้ เนื่องจากม้าจะไม่สามารถเดินไปในทุกๆช่องได้ (ยกเว้นตารางหมากรุกขนาด 1x1) และเมื่อ m=4 ก็ไม่สามารถเกิดการเดินแบบปิดได้เช่นกัน โดยการพิสูจน์จากสีในตารางหมากรุก<br />
:เริ่มพิสูจน์โดยการสมมุติให้ตาราง 4xn สามารถเดินม้าแบบปิดได้ และให้ A1 เป็นเช็ตของช่องสีดำและ A2 เป็นเช็ตของช่องสีขาว แล้วถ้ามีช่องสีขาวและช่องสีดำ สลับกันบนกระดานหมากรุก พิจารณาจากรูปทางด้านขวา กำหนดให้ B1 เป็นเช็ตของช่องสีเขียวและ B2 เป็นเช็ตของช่องสีแดง จากรูปทางด้านขวาจะสังเกตุสังเกตได้ว่าจำนวนของช่องสีเขียวและสีแดงมีจำนวนเท่ากัน และสมมุติให้ม้าเดินจากช่องใน B1 ม้าจะต้องเดินไปช่องใน B2 และม้าจะต้องเดินบนทุกๆช่อง โดยจะเดินไม่ซ้ำช่องกัน และเมื่อม้าอยู่บนช่อง B2 ม้าจะต้องเดินไปในช่องของ B1 ต่อไป (ในทางกลับกัน ม้าต้องเดินไปบนช่อง B1 สองครั้งในภายหลัง)
:ถ้าเราปฏิบัติตามการสมมุติข้างต้นเราจะพบข้อขัดแย้งดังนี้
:
บรรทัด 56:
[[Image:Warnsdorff.gif|left|thumb|240px|รูปภาพตาราง แสดงวิธีการเดินม้าหมากรุกตามกฎของวานส์ดอล์ฟ]]
กฎของวานดอล์ฟเป็นวิธีการแบบ[[ฮิวริสติก]]สำหรับการหาวิธีการเดินม้าหมากรุก กล่าวโดยสรุปคือในการเดินม้าแต่ละครั้งนั้นจะต้องเป็นไปตามกฎ กล่าวคือ
กำหนดให้ ในทุกช่องที่สามารถเดินไปจากช่องปัจจุบัน(ซึ่งไม่นับรวมถึงช่องที่เคยเดินผ่านไปแล้ว) จะมีค่าเท่ากับจำนวนช่องที่ช่องดังกล่าวสามารถเดินต่อไปได้ตามกฏกฎของการเดินม้าหมากรุก(ซึ่งไม่นับรวมถึงช่องที่เคยเดินผ่านไปแล้ว)
การเลือกช่องต่อไปสำหรับการเดินม้าจะพิจารณาเลือกช่องที่มีค่าน้อยที่สุด ซึ่งหากมีหลายช่องที่มีค่าน้อยที่สุดเท่ากันก็อาจมีทางเลือกได้หลายทาง
นอกจากกลวิธีดังกล่าวในการแก้ปัญหานี้ยังมีกลวิธีอื่นๆอีกหลายหลายวิธี เช่น กลวิธีของโพ และกลวิธีของสไควเออร์และคูล
บรรทัด 63:
 
====วิธีดำเนินการเพื่อประยุกต์กับกฎดังกล่าว====
กฏกฎของวานดอล์ฟสามารถใช้ได้กับจุดเริ่มต้นที่ช่องใดก็ได้ของตารางหมากรุก จำนวนครั้งที่เดินได้ก็คือจำนวนตัวเลขที่บรรจุในแต่ละช่อง ซึ่งตามกฎแล้ว จะต้องเดินไปยังช่องที่มีตัวเลขน้อยที่สุดนั่นเอง จากนั้นก็เลือกเดินตามกฎต่อไปจนกว่าจะเดินได้ครบทุกช่อง
 
<br />