อ.สั่งงานให้ผม แล้วให้แก้ปัญหา 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"
{/syntaxhighlighter}
ผมได้ลองค้นหาหลายวิธีมาก แต่ส่วนใหญ่เป็น ai ทำให้ผมต้อง import module มาใช้ แต่ อ.ไม่ให้ import และไม่ได้สอนเรื่อง ai เลย แม้แต่น้อย ผมกำลังเรียนวิชา Discrete Mathematics ครับ ท่านใดทราบวิธีแก้ปัญหานี้ ช่วยแสดงความคิดเห็นหน่อยครับ
{syntaxhighlighter brush: python}
from constraint import AllDifferentConstraint, InSetConstraint, Problem
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])
for vars_ in (colors, nationalities, pets, drinks, jobs):
problem.addConstraint(AllDifferentConstraint(), vars_)
problem.addConstraint(InSetConstraint([3]), ["milk"])
problem.addConstraint(InSetConstraint([1]), ["Norwegian"])
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}
ถ้าไม่ใช้อะไรเลยน่าจะทำได้ครับ
1 รวมกลุ่มของคำให้เป็น 5 กลุ่มโดย แต่ละประโยค จะมีคำสองคำ ที่สัมพันกัน เสมอ แสดงว่า เราสามารถใช้เงื่อนใขเหล่านี้ในการกำหนดกลุ่มได้
2 ถ้าอยากรู้ว่าใครดื่มน้ำเปล่า ก็ หากลุ่มที่มีน้ำเปล่า แล้วเอากลุ่มนั้นไป match กับ nationlity ก็ได้ว่าตรงกับคำใด
ไม่น่าจะต้อง AI ก็ได้นะครับ
คือจากโจทย์นะครับ ไม่มีข้อกำหนดใดๆ ที่กล่าวถึงน้ำเปล่า หรือบางตัวแปรก็ไม่มีการพูดถึง วิธีหาคำตอบคือ ทำทั้งหมดเลยครับ ว่าอะไรอยู่ในตำแน่งไหน แต่ผมมีปัญหากับการจัดกลุ่มอ่ะครับ คือผมไม่รู้ว่าโปรแกรมจะใช้เงื่นไขอะไรในการตัดสินใจ ว่าตัวแปรอะไรต้องอยู่ที่ไหนอ่ะครับ
จากที่ผมอ่าน คือ
ทุกๆประโยค จะมี Key word 2 ตัวเสมอ
ทั้งสองตัวจะอยู่กลุ่มเดียวกัน เสมอ
ถูกต้องไหมครับ
โอ้ว ยากได้อยู่แหะ น่าสนุกดี ^^
ผมว่าที่นี่น่าจะช่วยได้นะ http://en.wikipedia.org/wiki/Zebra_Puzzle ลองดูส่วนของ Solution ครับ
ไม่ต้องใช้ AI เลยครับ
ทำเปนตาราง รึไม่ก็ Flags แล้ว Fill gap ตามที่เขาบอกไปเรื่อยๆ
มันอารมณ์แนวเดียวกับ Sudoku น่ะ
หนังสือเกมสมัยก่อนมีเกมอย่างงี้เยอะนะ เมื่อก่อนผมชอบเล่น สนุกดี
ผมว่างานนี้มันเหมือนว่าต้องทำ array 2 มิติ นะครับ แล้วเขียน text processing มาแยก แล้วจับยัดใส่เป็นช่องๆ ไป แต่มองไปก็เหมือน AI นิดๆ คือให้โปรแกรมตัดสินใจว่าประโยคนี้เป็นประโยคแบบไหน
น่าสนใจแฮะ ผมเคยเล่นเกมส์นี้บนกระดาษ แต่ไม่เคยคิดว่าลองเขียนเป็นโปรแกรมดู
มันไม่ง่ายเลยที่จะทำ GIF ให้มีขนาดน้อยกว่า 20kB
เคยอ่านเจอในหนังสือเค้าบอกว่าคำถามนี้ไอน์สไตน์เป็นคนคิดขึ้นมาตอนหนุ่มๆ ว่ากันว่ามี2%ในโลกเท่านั้นที่คิดออก
ไม่รู้จริงป่าว
วิธีทำก็ให้ทำเป็น logic table ที่เป็นตารางแนวตั้งแนวนอนตามที่ท่านๆข้างบนได้ว่าไว้ครับ
อาจารย์ให้โจทย์ได้น่าสนใจมากครับ ผมเห็นแล้วอยากทำไปด้วยเลย ลองทำดูเล่นๆเป็น Javascript ใช้เวลาไปมากพอสมควร
เวลาทำโจทย์แนวนี้โดยใช้ดินสอกระดาษ เราก็จะพยายามสร้างคำตอบที่เป็นไปได้โดยดูจาก constraints ที่โจทย์บอก ทำผิดก็ลบใหม่แล้วสลับโน่นเปลี่ยนนั่นเปลี่ยนนี่ไปเรื่อยๆให้สอดคล้องกับ constraints จนได้คำตอบ .. แต่สิ่งที่ยากคือจะเอาวิธีที่กล่าวมานี้เปลี่ยนมาเป็น code ได้ยังไง??
สิ่งแรกที่ต้องทำคือ กำหนดรูปแบบของคำตอบที่เราต้องการ ตัวอย่างอันนี้กำหนดให้อยู่ในรูป list ของ list เช่น
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 หรืออย่างอื่น