หมาป่า แกะ กะหล่ำปลี

เกมพาคนสัตว์สิ่งของข้ามแม่น้ำนี่มีหลายเวอร์ชั่นมาก เกมนึงที่น่าจะเคยเล่นกันคือ “เกมพาหมาป่า แกะ และกะหล่ำปีข้ามแม่น้ำ” ในเกมนี้ เราต้องพาของทั้งสามอย่างข้ามฝั่งแม่น้ำโดยมีกฎอยู่ว่า

  • พาของข้ามแม่น้ำได้ทีละ 1 อย่าง
  • ถ้าอยู่กันสองต่อสอง หมาป่าจะกินแกะ และ แกะจะกินกะหล่ำ

อ่านกฎ อ่านกติกาเข้าใจยาก… คลิกที่รูปเพื่อลองเล่นเลยดีกว่าครับ

 

wolf-sheep-cabbage-300x179
เกมหมาป่า แกะ กะหล่ำ

เล่นเกมด่านแรกผ่านแล้วสินะครับ สำหรับ level 2 ในเว็บเมื่อกี้ เป็นเกมพามิชชันนารีกับยักษ์กินคนข้ามแม่น้ำ มีกฎกติกาคือ

  • ต้องมีคนอยู่ในเรืออย่างน้อย 1 คน ถึงจะพายเรือข้ามฝั่งได้ (เรือเปล่าๆ วิ่งข้ามฝั่งเองไม่ได้ครับ)
  • ถ้ายักษ์กินคนมีจำนวนมากกว่ามิชชันนารี ยักษ์จะจับมิชชันนารีกิน -> game over

 

มิชชันนารี
มิชชันนารี

ตอนเรียนวิชา Programming Language ผมมีโอกาสได้ลองเขียนโปรแกรมแก้ puzzle นี้ (มิชชันนารีและยักษ์กินคน) ด้วยภาษา Haskell ครับ

โปรแกรมนี้จะให้ลำดับของสถานะที่ทำให้ชนะเกมนี้ครับ

--h = number of humans on the left
--g = number of giants on the left
--s = side (left/right)

left = 0
right = 1

valid_state (h, g, s) =
    if (h >= 0) && (h = 0) && (g  h) && (h>0)) || ((3-g > 3-h) && (3-h > 0)))    --num of giant <= num of human
    else False

change (h, g, s) (hd, gd) =         -- create a new state based on hd (human diff), gd (giant diff)
    if s == left 
    then (h-hd, g-gd, right)
    else (h+hd, g+gd, left)

possible_states (h, g, s) = filter valid_state [change(h,g,s) (x,y) |
                            (x,y)  0        --if child got answer
            then [(h,g,s)]++z   
            else solve xs depth    --otherise return siblings' answer

iter_dpn depth =                --Iterative deepening depth-first search
    let ans = solve [(3,3,left)] depth
    in if length ans > 0
       then ans
       else iter_dpn (depth+1)

-- run "iter_dpn 0" to find answer

สถานะ = 3-tuple (จำนวนมิชชันนารีฝั่งซ้าย, จำนวนยักษ์ฝั่งซ้าย, ฝั่งที่เรือจอดอยู่)
สถานะเริ่มต้น = (3, 3, left) มิชชันนารี ยักษ์ และเรืออยู่ฝั่งซ้ายทั้งหมด
สถานะจบเกม = (0, 0, right) มิชชันนารี ยักษ์ และเรือข้ามมาอยู่ฝั่งขวาหมดแล้ว

วิธีแก้ปัญหานี้ผมใช้ depth-first search เริ่มค้นจากสถานะเริ่มต้นไปหาสถานะจบเกม โดยไม่ท่องไปในกิ่งที่ทำให้แพ้ (มีคนน้อยกว่ายักษ์ ยักษ์เลยจับคนกิน)

บางคนอาจสงสัยว่า ถ้าใช้ depth-first search แล้วเราจะได้คำตอบที่สั้นที่สุดมั้ย (พายเรือน้อยครั้งที่สุด) คำตอบคือผมใช้ Iterative deepening depth-first search ครับ

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s