knights exchange
เขียนโดย ศล

คณิตศาสตร์กับหมากรุกมีความสัมพันธ์ใกล้ชิดกัน นักคณิตศาสตร์ชื่อเสียงโด่งดังหลายท่านตั้งแต่อดีตจนถึงปัจจุบันต่างเคยหลงเสน่ห์ปริศนาและความลึกลับลึกล้ำของมัน ครั้งหนึ่งโปรเฟสเซอร์คณิตศาสตร์ประยุกต์ Richard P. Stanley แห่ง MIT ถึงกับสรุปว่ามนุษยชาติไม่มีวันเข้าใจหมากรุกได้อย่างสมบูรณ์ (Human beings will never be able to understand chess completely.) ในบทความตอนนี้ ขอหยิบปัญหาคลาสสิกข้อหนึ่งซึ่งเราสามารถใช้กราฟแก้ปัญหาได้อย่างสวยงาม ย้อนกลับไปในประวัติศาสตร์ยาวนานถึงกว่า 500 ปี ปัญหานี้รู้จักกันในนาม Guarini’s Problem



รูปที่ 1 แสดงม้าหรืออัศวินสีขาว 2 ตัว สีดำ 2 ตัว บนกระดานหมากรุกขนาด 3x3 ช่อง ถ้าเราต้องการสลับฝั่งม้าทั้ง 2 สี เพื่อให้ม้าขาวไปแทนที่ม้าดำ และม้าดำมาแทนที่ม้าขาว ต้องเดินหมากอย่างไร? และเดินน้อยที่สุดกี่ที? ผมเชื่อว่าถ้าคุณรู้ว่าม้าเดินอย่างไร และลองพยายามเดินเล่น ในเวลาไม่นานนักคุณก็สามารถพบคำตอบได้ไม่ยาก ไม่จำเป็นต้องใช้คณิตศาสตร์ช่วยแก้ปัญหา แต่การตีความปัญหาข้อนี้ใหม่ให้กลายเป็นโจทย์คณิตศาสตร์ถือเป็นจุดเริ่มต้นที่ดี เพราะในโจทย์ที่มีความซับซ้อนเพิ่มมากขึ้น กระบวนวิธีลองผิดลองถูก (Trial & Error) คงไม่ใช่วิธีที่ดีสำหรับใช้แก้ปัญหา

เพื่อป้องกันไม่ให้คนที่เล่นหมากรุกไม่เป็นรู้สึกเสียเปรียบ ขอแนะนำวิธีการเดินม้า ดังรูปที่ 2 ม้าดำที่ยืนอยู่บนช่องขาวสามารถเดินไปยังช่องที่มีเครื่องหมายกากบาทได้ รูปร่างการเดินเหมือนตัว L สูง 3 ช่อง ฐานยาว 2 ช่อง ที่พลิกตะแคงในแนวต่างๆ มีข้อสังเกตที่มีประโยชน์มากข้อหนึ่งคือ เราไม่สามารถเดินม้าจำนวนคี่ครั้ง (2n-1 ครั้ง เมื่อ n เป็นจำนวนนับ) ไปยังช่องที่มีสีเหมือนสีช่องเริ่มต้นได้ เพราะเดิน 1 ครั้ง ม้าเปลี่ยนสีช่องที่มันยืนเสมอ

กราฟคืออะไร? กราฟคือเซ็ตของจุด (Vertices) และเส้นเชื่อมจุด (Edges) อาจเขียนแทนด้วยสัญลักษณ์ G = (V,E) ถ้ามีองค์ประกอบครบ 2 อย่างนี้ก็มีกราฟ เราจะแปลงหน้าตาดังรูปที่ 1 ให้เป็นกราฟเส้นทางเดินของม้าได้อย่างไร อาจพิจารณาให้แต่ละช่องคือจุด ดังนั้นเรามีเซ็ตของจุดอยู่แล้ว 9 จุด ต่อมาคือดูว่าแต่ละจุดมีเส้นเชื่อมกับจุดที่เหลือในลักษณะใด ซึ่งเงื่อนไขการเชื่อมจุดสำหรับโจทย์ข้อนี้คือเส้นทางเดินของม้านั่นเอง

รูปที่ 3 แสดงตัวอย่างตำแหน่งม้าขาวมุมล่างซ้ายเชื่อมกับตำแหน่งม้าขาวอีก 2 ตัวที่เหลือ และม้าดำตำแหน่งกลางล่างเชื่อมกับตำแหน่งม้าดำอีก 2 ตัวที่เหลือ เมื่อเชื่อมครบทุกจุดจะได้กราฟดังรูปที่ 4 สังเกตว่าจุดหมายเลข 5 ไม่ได้อยู่ในกราฟ หรือ V = {1, 2, 3, 4, 6, 7, 8, 9} และ E = {1-6, 1-8, 2-7, 2-9, 3-4, 3-8, 4-9, 6-7} เมื่อ i-j แทนเส้นเชื่อมจุด i กับจุด j ซึ่ง i-j = j-i จากกราฟรูปที่ 4 ดูค่อนข้างวุ่นวาย แต่เราสามารถคลี่ให้มันดูง่ายขึ้นได้ดังรูปที่ 5 และตัดจุด 5 ซึ่งไม่อยู่ในกราฟทิ้งไป



เราเห็นได้ชัดเจนจากรูปที่ 5 ม้าขาว 7 และม้าขาว 9 กับม้าดำ 1 และม้าดำ 3 จะสลับตำแหน่งกันได้มีหนทางอยู่เพียง 2 วิธี คือเดินเป็นวงหมุนตามเข็มนาฬิกา หรือทวนเข็มนาฬิกาเท่านั้น (เมื่อมาถึงจุดนี้ เราไม่จำเป็นต้องเป็นผู้เชี่ยวชาญด้านการเดินม้า เราก็หาคำตอบได้ เพราะรูปแบบการเดินม้าไม่สำคัญอีกต่อไป) เช่นม้าดำเดินจาก 1 ไป 8 ม้าดำเดินจาก 3 ไป 4 ม้าขาวเดินจาก 9 ไป 2 ม้าขาวเดินจาก 7 ไป 6 และวนตามเข็มนาฬิกาเช่นนี้ไปเรื่อยๆ จนกระทั่งม้าขาวซึ่งเดิมเริ่มที่ 7 ไปสิ้นสุดที่ 3 ทำให้ม้าแต่ละตัวเดิน 4 ที เมื่อรวมตั้งแต่ต้นจนจบก็เป็น 16 ที โจทย์ลักษณะเดียวกันนี้แต่เพิ่มความยากขึ้นมาอีกนิด เป็นม้าสีละ 3 ตัว บนกระดานขนาด 3x4 ช่อง เคยตั้งคำถามถามผู้อ่านนิตยสาร Scientific American ฉบับเดือนธันวาคม พ.ศ. 2522 แสดงดังรูปที่ 6 ด้วยวิธีการเดียวกันเราสามารถสร้างกราฟอย่างง่ายได้ดังรูปที่ 7 วิธีการสร้างเป็นอย่างไร และตอบคำถามโจทย์ได้เท่าไร ขอฝากคุณผู้อ่านลองค้นหาคิดต่อเป็นการลับสมอง



ปัจจุบันรูปแบบ Guarini’s Problem มีหน้าตาที่ดูยุ่งยากขึ้น เพิ่มเงื่อนไขมากขึ้น ตัวอย่างเช่น G-Knights Exchange ของ Serhiy Grabarchuk ซึ่งจัดช่องบนกระดานให้เป็นรูปตัว G มีม้าสีละ 4 ตัว และช่องว่างอีก 2 ช่อง ดังรูปที่ 8 ม้าสามารถเดินได้ตามปกติ แต่จะไปหยุดยืนอยู่บนช่องที่มีสัตว์ประหลาดไม่ได้



โจทย์ข้อนี้ถ้าเราใช้วิธี Trial & Error ก็ไม่ยาก เพราะช่องว่างที่เหลือมีน้อย ม้าจึงเดินแกมถูกบังคับ เช่นถ้าเราต้องการเดินไปช่องสีดำ มีม้าขาว 2 ตัวกับม้าดำ 1 ตัวเท่านั้นที่สามารถเดินได้ ถ้าเราต้องการเดินไปช่องสีขาว มีม้าดำเพียงตัวเดียวที่สามารถเดินได้ ตัวที่สามารถเดินได้ก่อนจึงมีเพียง 4 ตัว คนคิดโจทย์คงกลัวว่าง่ายเกินไปจึงท้าทายเพิ่มเติมว่า คุณสามารถสลับที่ม้าดำ-ม้าขาวภายในการจับม้า 11 ครั้งได้หรือไม่ คำว่าจับม้า 11 ครั้งของเขาไม่ใช่จำนวนทีที่เดิน 11 ที การเดิน 11 ทีย่อมเป็นไปไม่ได้ เพราะม้า 1 ตัวต้องเดินมากกว่า 1 ทีเพื่อไปแทนที่ม้าสีตรงข้าม แต่ถ้าม้าตัวใดเดิน 1 ที แล้วไปแทนที่ม้าสีตรงข้ามได้ ม้าตำแหน่งที่ถูกแทนที่ต้องเดิน 1 ทีเพื่อหลีกทางและเดินอีกมากกว่า 1 ทีเพื่อไปแทนที่ม้าสีตรงข้าม ดังนั้นจำนวนทีที่น้อยที่สุด (ถ้าเป็นไปได้) คือ 8x2 = 16 ที บอกคุณผู้อ่านก่อนได้เลยครับว่าเป็นไปไม่ได้ เพราะฉะนั้น คำว่าจับม้า 11 ครั้งจึงหมายถึง ถ้าเราจับม้าตัวใดเดิน 1 ที แล้วเดินม้าตัวเดิมต่อไปยังอีกช่องเป็นทีที่ 2 นับเป็นการจับม้า 1 ครั้ง (เราคงไม่สามารถเดินต่อได้อีกเป็นทีที่ 3 ในการจับ 1 ครั้ง เว้นแต่จะเดินถอยหลังกลับ)



รูปที่ 9 ดึงมาเฉพาะตัว G ของรูปที่ 8 เขียนเส้นเชื่อมจุดได้ดังรูปที่ 10 และคลี่เป็นกราฟรูปผีเสื้อที่ดูง่ายขึ้นตามรูปที่ 11 ถ้าเราไม่สนใจจำนวนทีที่เดิน แต่ต้องการความง่าย เราแบ่งกราฟเป็น 2 ซีก ปีกซ้ายกับปีกขวาของผีเสื้อแล้ววนสลับม้าดำ-ม้าขาวปีกใครปีกมันก็ได้ ด้านปีกข้างขวาไม่มีปัญหาในการวน เพราะวนเป็นวง แต่ปีกซ้ายไม่สามารถวนเป็นวง ต้องยืมจุดที่ 7 ของปีกขวามาเป็นที่พักชั่วคราว



ปีกขวาวนได้ดังนี้ (x-y แทนการเดินจากจุด x ไปยังจุด y นับเป็นการเดิน 1 ที)


ปีกซ้ายวนได้ดังนี้


2 ตารางข้างบนนี้แสดงวิธีการสลับอย่างง่าย ทั้งวนปีกซ้ายและปีกขวาต่างเดินปีกละ 12 ที จับม้าปีกละ 6 ครั้ง รวมแล้วเดิน 24 ที จับม้า 12 ครั้ง เราสามารถลดจำนวนทีจำนวนครั้งลงได้ไหม? คำตอบคือได้ครับ ผมจะสร้างกราฟเส้นทางเดินของม้าขาวจุด 3 กับม้าขาวจุด 1 ขอให้คุณผู้อ่านลองสังเกตดู



เส้นสีแดงคือทางเดินของม้าขาวจุด 3 เริ่มจากจุด 3 ไปยังจุด 6 เป็นเส้นทางตรงเดินทั้งหมด 4 ที เส้นสีม่วงคือทางเดินของม้าขาวจุด 1 เริ่มจากจุด 1 ไปยังจุด 9 เดิน 4 ทีเท่ากัน แต่มีการเดินย้อนทางเดิมคือ จากจุด 5 ไปจุด 7 แล้วจากจุด 7 กลับมาจุด 5 เนื่องจากม้าทั้ง 2 ตัวเป็นม้าสีขาวเหมือนกัน ดังนั้นเราสามารถสลับให้ม้าขาวจุด 1 เดินไปยังจุด 6 แทน และให้ม้าขาวจุด 3 เดินไปจุด 9 ลดจำนวนทีที่เดินลง 2 ที คือ 1-5-7-10-6 เดิน 4 ที และ 3-5-9 เดิน 2 ที สรุปผลการปรับปรุงเส้นทางดังตารางต่อไปนี้



x-y-z แทน เดินจากจุด x ไปยังจุด y แล้วเดินม้าตัวเดิมจากจุด y ต่อไปยังจุด z นับเป็นการจับ 1 ครั้ง ซึ่งเราทำรวมได้ จับ 11 ครั้ง เดิน 22 ที ตรงตามวัตถุประสงค์โจทย์ สำหรับข้อนี้ถ้าใครสามารถใช้วิธี Trial & Error แล้วประสบผลสำเร็จ 22 ที ตั้งแต่ trial แรก เราก็คงต้องยอมรับว่าเขาหรือเธอคนนั้นเป็นนักสลับรางชั้นเซียน







[บทความนี้ตีพิมพ์ใน MY MATHS ฉบับที่ 38 ประจำเดือน มีนาคม พ.ศ. 2551]





Create Date : 29 พฤศจิกายน 2550
Last Update : 10 มีนาคม 2551 10:16:57 น.
Counter : 1739 Pageviews.

0 comments
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

ศล
Location :
กรุงเทพ  Thailand

[ดู Profile ทั้งหมด]
 ผู้ติดตามบล็อก : 85 คน [?]

บทความทั้งหมด