Tags:
Forums: 

อ.สั่งงานให้ผม แล้วให้แก้ปัญหา Zebra Puzzle ที่ว่า
มีคน 5 คน แต่ละคน ทำงานต่างกัน ดื่มเครื่องดื่มต่างกัน มีสัตว์เลี้ยงต่างกัน มีสัญชาติต่างกัน แล้วมีบ้านสีต่างกัน
แล้วให้หาว่า ใครเลี้ยงม้าลาย แล้วใครดื่มน้ำเปล่า จากเงื่อนไขต่อไปนี้
{syntaxhighlighter brush: python}
colors = "red white green yellow blue"
nationalities = "English Spanish Japanese Italian Norwegian"
pets = "dog snails fox horse zebra"
drinks = "tea, orange juice, milk, coffe, water"
jobs = "painter diplomat photographer violinist physician"

The English man lives in the red house.

The Spanish owns a dog.

The Japanese man is a painter.

The Italians drinks tea.

The Norwegian lives in the first house on the left.

The green house is immediately to the right of the white one.

The photographer breeds snails.

The diplomat lives in the yellow house.

Milk is drunk in the middle house.

The owner of the green house drinks coffe.

The Norwegians's house is next ot the blue one.

The violinist drinks orange juice.

The fox is in the house next to that of the physician.

The horse is in a house next to that diplomat.

{/syntaxhighlighter}
ผมได้ลองค้นหาหลายวิธีมาก แต่ส่วนใหญ่เป็น ai ทำให้ผมต้อง import module มาใช้ แต่ อ.ไม่ให้ import และไม่ได้สอนเรื่อง ai เลย แม้แต่น้อย ผมกำลังเรียนวิชา Discrete Mathematics ครับ ท่านใดทราบวิธีแก้ปัญหานี้ ช่วยแสดงความคิดเห็นหน่อยครับ
{syntaxhighlighter brush: python}
from constraint import AllDifferentConstraint, InSetConstraint, Problem

variables

colors = "red white green yellow blue".split()
nationalities = "English Spanish Japanese Italian Norwegian".split()
pets = "dog snails fox horse zebra".split()
drinks = "tea, orange juice, milk, coffe, water".split(", ")
jobs = "painter diplomat photographer violinist physician".split(" ")

minn, maxn = 1, 5
problem = Problem()
variables = colors + nationalities + pets + drinks + jobs
problem.addVariables(variables, [1, 2, 3, 4, 5])

Five men with different nationalities and with different jobs lives in consecutive houses on a street.

These houses are painted different colors.

The men have have different pets and drink different drinks.

for vars_ in (colors, nationalities, pets, drinks, jobs):
problem.addConstraint(AllDifferentConstraint(), vars_)

The English man lives in the red house.

The Spanish owns a dog.

The Japanese man is a painter.

The Italians drinks tea.

The Norwegian lives in the first house on the left.

The green house is immediately to the right of the white one.

The photographer breeds snails.

The diplomat lives in the yellow house.

Milk is drunk in the middle house.

The owner of the green house drinks coffe.

The Norwegians's house is next ot the blue one.

The violinist drinks orange juice.

The fox is in the house next to that of the physician.

The horse is in a house next to that diplomat.

Milk is drunk in the middle house.

problem.addConstraint(InSetConstraint([3]), ["milk"])

The Norwegian lives in the first house on the left.

problem.addConstraint(InSetConstraint([1]), ["Norwegian"])

The green house is on the right side of the white house.

problem.addConstraint(lambda a,b: a+1 == b, ["white", "green"])

def add_constraints(constraint, statements, variables=variables, problem=problem):
for stmt in (line for line in statements if line.strip()):
problem.addConstraint(constraint, [v for v in variables if v in stmt])

_statements = """
The owner of the green house drinks coffe.
The photographer breeds snails.
The English man lives in the red house.
The Italian drinks tea.
The diplomat lives in the yellow house.
The violinist drinks orange juice.
The Japanese man is a painter.
The Spanish owns a dog.
""".split("\n")
add_constraints(lambda a,b: a == b, _statements)

nextto_statements = """
The Norwegian house is next to the right the blue one.
The fox is in the house next to that of the physician.
The horse is in a house next to that diplomat.
""".split("\n")
add_constraints(lambda a,b: abs(a - b) == 1, nextto_statements) #abs = absolute

def solve(variables=variables, problem=problem):
from itertools import groupby
from operator import itemgetter

# find & print solutions
for solution in problem.getSolutionIter():
    for key, group in groupby(sorted(solution.iteritems(), key=itemgetter(1)), key=itemgetter(1)):
        print (key)
        for v in sorted(dict(group).keys(), key=variables.index):
            print (v.ljust(9))
        print

if name == 'main':
solve()
{/syntaxhighlighter}

Get latest news from Blognone
By: JavaDevil
iPhoneUbuntuIn Love
on 26 June 2011 - 23:54 #304269

ถ้าไม่ใช้อะไรเลยน่าจะทำได้ครับ
1 รวมกลุ่มของคำให้เป็น 5 กลุ่มโดย แต่ละประโยค จะมีคำสองคำ ที่สัมพันกัน เสมอ แสดงว่า เราสามารถใช้เงื่อนใขเหล่านี้ในการกำหนดกลุ่มได้
2 ถ้าอยากรู้ว่าใครดื่มน้ำเปล่า ก็ หากลุ่มที่มีน้ำเปล่า แล้วเอากลุ่มนั้นไป match กับ nationlity ก็ได้ว่าตรงกับคำใด

ไม่น่าจะต้อง AI ก็ได้นะครับ

By: niineww
Blackberry
on 27 June 2011 - 00:07 #304275

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

By: JavaDevil
iPhoneUbuntuIn Love
on 27 June 2011 - 10:46 #304340

จากที่ผมอ่าน คือ
ทุกๆประโยค จะมี Key word 2 ตัวเสมอ
ทั้งสองตัวจะอยู่กลุ่มเดียวกัน เสมอ
ถูกต้องไหมครับ

By: JavaDevil
iPhoneUbuntuIn Love
on 27 June 2011 - 14:07 #304388

โอ้ว ยากได้อยู่แหะ น่าสนุกดี ^^

By: THXiLL
iPhoneAndroidUbuntuWindows
on 28 June 2011 - 12:26 #304626

ผมว่าที่นี่น่าจะช่วยได้นะ http://en.wikipedia.org/wiki/Zebra_Puzzle ลองดูส่วนของ Solution ครับ

By: Thaina
Windows
on 28 June 2011 - 12:41 #304630

ไม่ต้องใช้ AI เลยครับ

ทำเปนตาราง รึไม่ก็ Flags แล้ว Fill gap ตามที่เขาบอกไปเรื่อยๆ
มันอารมณ์แนวเดียวกับ Sudoku น่ะ

หนังสือเกมสมัยก่อนมีเกมอย่างงี้เยอะนะ เมื่อก่อนผมชอบเล่น สนุกดี


My Blog

By: EThaiZone
ContributorAndroidUbuntuWindows
on 1 July 2011 - 10:29 #306126
EThaiZone's picture

ผมว่างานนี้มันเหมือนว่าต้องทำ array 2 มิติ นะครับ แล้วเขียน text processing มาแยก แล้วจับยัดใส่เป็นช่องๆ ไป แต่มองไปก็เหมือน AI นิดๆ คือให้โปรแกรมตัดสินใจว่าประโยคนี้เป็นประโยคแบบไหน

น่าสนใจแฮะ ผมเคยเล่นเกมส์นี้บนกระดาษ แต่ไม่เคยคิดว่าลองเขียนเป็นโปรแกรมดู


มันไม่ง่ายเลยที่จะทำ GIF ให้มีขนาดน้อยกว่า 20kB

By: xerra on 2 July 2011 - 02:18 #306560

เคยอ่านเจอในหนังสือเค้าบอกว่าคำถามนี้ไอน์สไตน์เป็นคนคิดขึ้นมาตอนหนุ่มๆ ว่ากันว่ามี2%ในโลกเท่านั้นที่คิดออก
ไม่รู้จริงป่าว
วิธีทำก็ให้ทำเป็น logic table ที่เป็นตารางแนวตั้งแนวนอนตามที่ท่านๆข้างบนได้ว่าไว้ครับ

By: m3rlinez on 10 July 2011 - 03:29 #309293

อาจารย์ให้โจทย์ได้น่าสนใจมากครับ ผมเห็นแล้วอยากทำไปด้วยเลย ลองทำดูเล่นๆเป็น Javascript ใช้เวลาไปมากพอสมควร

เวลาทำโจทย์แนวนี้โดยใช้ดินสอกระดาษ เราก็จะพยายามสร้างคำตอบที่เป็นไปได้โดยดูจาก constraints ที่โจทย์บอก ทำผิดก็ลบใหม่แล้วสลับโน่นเปลี่ยนนั่นเปลี่ยนนี่ไปเรื่อยๆให้สอดคล้องกับ constraints จนได้คำตอบ .. แต่สิ่งที่ยากคือจะเอาวิธีที่กล่าวมานี้เปลี่ยนมาเป็น code ได้ยังไง??

สิ่งแรกที่ต้องทำคือ กำหนดรูปแบบของคำตอบที่เราต้องการ ตัวอย่างอันนี้กำหนดให้อยู่ในรูป list ของ list เช่น

[[1,2,3,4,5],
[yellow,blue,red,white,green],
[Norwegian,Italian,English,Spanish,Japanese],
[fox,horse,snails,dog,zebra],
[water,tea,milk,orange juice,coffe],
[diplomat,physician,photographer,violinist,painter]]

list ย่อยตัวแรกจะบอกตำแหน่งของบ้าน ตัวต่อมาบอกสีบ้าน ตัวต่อมาบอกสัญชาติ และอื่นๆ ตามลำดับ จากตัวอย่างจะบอกว่าบ้านหลังแรกสีเหลือง มีชาว Norwegian บ้านหลังที่ 3 มีชาว Italian เลี้ยงหอยทาก เป็นต้น
จากรูปแบบคำตอบแบบนี้และข้อมูลที่โจทย์ให้มา เราจะต้องหาคำตอบที่ถูกต้องจากคำตอบที่เป็นไปได้ทั้งหมด (5!)^5 = 24,883,200,000 แบบ (ไม่ต้องยกกำลัง 6 เพราะจริงๆแล้ว list ย่อยตัวแรกคือตำแหน่งนั้น เรา fixed ไว้เลย)

ทำแบบตรงไปตรงมา .. เราก็ generate คำตอบที่เป็นไปได้ทั้งหมดออกมา แล้วเอามาตรวจสอบกับ constraints ว่าผ่านทุก constraints หรือไม่ หลังจากตรวจสอบแล้วก็จะเหลือแค่คำตอบที่สอดคล้องกับ constraints ทั้งหมด ถ้าลองทำกับโจทย์ข้อนี้จะพบว่ามันเหลือแค่คำตอบเดียว (จากทั้งหมด 25,000 ล้านแบบ) ถ้าลองเอา constraint ออกซักตัวจะเห็นได้ว่ามีตำตอบออกมาเพิ่มหลายคำตอบ

วิธี generate คำตอบทำได้ด้วยการหา permutation ทั้งหมดที่เป็นไปได้ ยกตัวอย่างเช่น [1,2,3] มี permutation 3! =6 แบบ คือ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] .. อัลกอริทึมสำหรับการทำดูได้ใน http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations

แต่ถ้าเราจะ generate คำตอบที่เป็นได้ไปได้ออกมาทั้ง 25,000 ล้านแบบแล้ว ตรวจสอบทุกแบบอาจจะใช้เวลามาก จริงๆแล้วเราสามารถตัดคำตอบที่เป็นไปไม่ได้ออกได้ตั้งแต่ตอน generate เลย เช่นมี constraint ตัวนึงบอกว่าบ้านหลังสีเขียวอยู่ถัดจากบ้านหลังสีขาว ดังนั้นระหว่างเรา generate สีบ้าน เราก็ตัดเคสอื่นๆที่ไม่สอดคล้องกับ constraint ตัวนี้ออกไปซะ ก็จะลดเวลาที่ใช้ลงไปได้มาก (pruning)

ที่ผม implement เป็น Javascript ลองเข้าไปดู (view source) ได้ที่ http://www.solidskill.net/ZebraPuzzle.htm ถ้าเข้าใจหลักการแล้วจะ implement เป็น Python หรือภาษาอื่นก็ไม่น่าจะลำบาก

ผมเข้าใจว่าถ้าเป็นวิชา Discrete Mathematics อาจารย์คงอยากให้หัดทำ permutation แหละ คงไม่ได้ต้องการให้ใช้เทคนิคยากๆจาก AI หรืออย่างอื่น