Bloggang.com : Duke! - ปริศนาอัศวินเปลี่ยนฝั่ง

Bloggang.com : weblog for you and your gang

ปริศนาอัศวินเปลี่ยนฝั่ง

จากกระทู้ //www.pantip.com/cafe/wahkor/topic/X4828234/X4828234.html

ปริศนาอัศวินเปลี่ยนฝั่ง (Switch the knights)

เดือนธันวาคม ปีพุทธศักราช 2522 นิตยสาร Scientific American ได้ตั้งปริศนาท้าทายสมองผู้อ่าน

กระดานหมากรุกขนาด 3x4
มี อัศวินดำ 3 อัศวินขาว 3
ดังรูปข้างล่างนี้

ถ้าต้องการให้อัศวินดำและอัศวินขาว สลับตำแหน่งกัน ต้องขยับหมากเดินน้อยที่สุดกี่ที

(อย่าตอบว่าหมุนกระดาน 180 องศามานะครับ ---น่ารักเกินไป)

จากคุณ : ศล - [ 27 ต.ค. 49 13:37:29 ]

ความคิดเห็นที่ 1

สรุปความจาก Across the Board โดย John J. Watkins สำนักพิมพ์ Princeton Univerity Press

ว่ากันว่าปริศนากระดานหมากรุกเริ่มตั้งแต่ปี 1512 รู้จักกันในนาม Guarini's Problem
กระดานหมากรุกขนาด 3x3
มีอัศวินดำ 2 อัศวินขาว 2
ถ้าต้องการสลับตำแหน่งขาวกับดำ ต้องเดินทั้งหมดกี่ครั้ง

(ลองทำดูได้ครับ ง่าย)

จากคุณ : ศล - [ 27 ต.ค. 49 13:38:25 ]

ความคิดเห็นที่ 2

โจทย์ข้อนี้สามารถนำกราฟมาช่วยได้ครับ
และเปลี่ยนให้ปริศนาหมากรุก กลายเป็นปัญหาคณิตศาสตร์

รูปด้านล่างทางซ้ายมือ
เราลากเส้นเชื่อมโยงจุดที่อัศวินสามารถเดินได้เข้าด้วยกัน
อาจจะดูเป็นรูปซับซ้อน
แต่เมื่อเราคลี่มันออกมา จะเป็นดังรูปขวามือ

ได้กราฟ 1 วง
จากกราฟเห็นชัดเจนว่า
ในการเคลื่อนย้ายอัศวินนั้นเราไม่มีทางเลือกเลย
ถ้าไม่หมุนทวนเข็มนาฬิกา ก็ต้องหมุนตามเข็มนาฬิกา
จนกว่าอัศวินทั้ง 2 ฝ่ายจะสลับตำแหน่งกัน

กราฟแก้ปัญหาหมากรุกข้อนี้ได้อย่างสวยงาม!

จากคุณ : ศล - [ 27 ต.ค. 49 13:39:10 ]

ความคิดเห็นที่ 7

ใช้แนวทางเดียวกับ #2 ครับ
แทนช่องแต่ละช่อง ด้วย A, B, C, ..., L
อัศวินดำอยู่ที่ช่อง A, B, C
อัศวินขาวอยู่ที่ช่อง J, K, L
ลากเส้นเชื่อมช่องที่เดินถึงกันได้ ตามรูปซ้าย
แล้วนำมาเขียนใหม่ให้ดูง่ายขึ้น โดยยังคงการเชื่อมโยงไว้เหมือนเดิม ตามรูปขวา

จากคุณ : Duke! - [ 27 ต.ค. 49 21:59:52 ]

ความคิดเห็นที่ 8

จากนั้น ก็เดินตามลูกศรในรูปข้างล่าง
(เดินตามลำดับลูกศรด้วยนะครับ)

ถ้ายึดระบบอ้างอิงตามรูปใน #7 ขวา ก็จะได้ว่า
ขั้นที่ 1 อัศวินดำที่อยู่ช่อง C เดินจาก C -> D -> I
ขั้นที่ 2 อัศวินขาวที่อยู่ช่อง K เดินจาก K -> D -> C
ขั้นที่ 3 อัศวินดำที่อยู่ช่อง A เดินจาก A -> F -> K
ขั้นที่ 4 อัศวินขาวที่อยู่ช่อง L เดินจาก L -> G -> F -> A
...
ทำไปจนถึงขั้นที่ 8 ก็จะได้อัศวินดำมาแทนที่อัศวินขาว อัศวินขาวไปแทนที่อัศวินดำ

รวมแล้ว ต้องเดิน 16 ครั้ง ซึ่งเป็นจำนวนการเดินที่น้อยที่สุดเท่าที่จะทำได้แล้ว
ถ้าถามว่าพิสูจน์ยังไง ก็ขอตอบว่า พิสูจน์ด้วยโปรแกรมคอมพิวเตอร์ครับ อิอิ