Just algorithm!
[C#] Solve Einstein's Puzzle ด้วย LINCON

มี Library ตัวนึงชื่อ LINCON
(Language INtegrated CONstraint programming)
ชื่อมันดูเชย ๆ ใช่ไหมครับ
มันเป็นลูกที่ผมทอดทิ้งไปสักพักละ Smiley

คือมีช่วงนึง ประมาณสองปีที่แล้ว
ผมไปติด web ProjectEuler อย่างหนัก (ถ้าอ่าน Post แรก ๆ ของผมก็รู้)
ถึงขนาดไปศึกษา Algorithm ต่าง ๆ มากมาย เพื่อแก้ปัญหา
แล้วก็นำ Algorithm พวกนั้นไปเขียนเป็น Code C#
(นั่นก็เป็นเหตุผลว่าทำไม Blog ของผมมีแต่แนว Algorithm) Smiley

Library ตัวที่ชื่อ LINCON นี้
เป็น Library ที่ผมชอบมากที่สุด แต่ไม่มีเวลามาเขียนให้เสร็จซะที
แต่ไม่รู้ว่าบุญหรือกรรม อาทิตย์ที่แล้วกลับบ้านเร็ว แถมมีวันหยุดพิเศษเนื่องจากเหตุการณ์ไม่สงบ
พอดีอยากเขียนต่อ ก็เลยต่อจนเสร็จซะที Smiley

LINCON เป็น Backtracker ที่มีความสามารถ LookAhead
และพิเศษไปกว่านั้น มันสามารถเขียนด้วย Linq ได้ Smiley

ก่อนอื่นดูตัวอย่างก่อนเลยครับ
คุณรู้จัก Einstein's Puzzle ไหมครับ
เค้าว่ากันว่ามีคนแค่ 2% ที่สามารถแก้โจทย์นี้ได้

โจทย์มีอยู่ว่า

มีบ้านอยู่ 5 หลัง ที่มีสีต่างกันหมด
ในบ้านแต่ละหลังมีคนอยู่หนึ่งคนที่เป็นชนชาติที่ต่างกัน 5 ชนชาติ
ซึ่งทุกคนจะดื่มน้ำที่แตกต่างกัน สูบบุหรี่ยี่ห้อต่างกัน และสัตว์เลี้ยงต่างกัน

คนที่เป็นชาวอังกฤษอยู่บ้านสีแดง
คนที่เป็นชาวสวีเดนเลี้ยงหมา
คนที่เป็นชาวเดนมาร์กดื่มชา
บ้านสีเขียวอยู่ทางซ้ายของบ้านสีขาว
เจ้าของบ้านสีเขียวดื่มกาแฟ
คนที่สูบบุหรี่ยี่ห้อ Pall Mall เป็นคนเลี้ยงนก
เจ้าของบ้านสีเหลืองสูบบุหรี่ยี่ห้อ Dunhill
คนที่อยู่บ้านหลังกลางดื่มนม
คนที่เป็นชาวนอร์เวย์อยู่บ้านหลังแรก
คนที่สูบบุหรี่ยี่ห้อ Blends อยู่ติดกับคนเลี้ยงแมว
คนที่เลี้ยงม้าอยู่ติดกับคนที่สูบบุหรี่ยี่ห้อ Dunhill
คนที่สูบบุหรี่ยี่ห้อ Bulemaster ดื่มเบียร์
คนที่เป็นชาวเยอรมันสูบบุหรี่ยี่ห้อ Prince
คนที่เป็นชาวนอร์เวย์อยู่ติดกับบ้านสีฟ้า
คนที่สูบบุหรี่ยี่ห้อ Blends เป็นเพื่อนบ้านกับคนที่ดื่มน้ำ

คำถามคือ ใครเป็นคนเลี้ยงปลา ?

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

          //มี 5 ชนชาติ
var sol = from n in ArrayExt.Enum<Nationality>().ToConstraintList(5)
          //5 สีบ้าน
          from c in ArrayExt.Enum<HouseColor>().ToConstraintList(5)
          //5 บุหรี่
          from s in ArrayExt.Enum<Smoke>().ToConstraintList(5)
          //5 เครื่องดื่ม
          from d in ArrayExt.Enum<Drink>().ToConstraintList(5)
          //5 สัตว์เลี้ยง
          from p in ArrayExt.Enum<Pet>().ToConstraintList(5)
          //i จะเป็นเลขใดก็ได้ 0-4
          from i in 0.To(4).ToConstraintIndex()
          //ไม่มีชนชาติเดียวกัน
          where Constraint.AllDifferent(n)
          //ไม่มีสีบ้านเดียวกัน
          where Constraint.AllDifferent(c)
          //ไม่มีบุหรี่ยี่ห้อเดียวกัน
          where Constraint.AllDifferent(s)
          //ไม่มีเครื่องดื่มเดียวกัน
          where Constraint.AllDifferent(d)
          //ไม่มีสัตว์เลี้ยงเดียวกัน
          where Constraint.AllDifferent(p)
          //คนที่เป็นชาวอังกฤษอยู่บ้านสีแดง
          where (n[i] == Nationality.British) == (c[i] == HouseColor.Red)
          //คนที่เป็นชาวสวีเดนเลี้ยงหมา
          where (n[i] == Nationality.Swedish) == (p[i] == Pet.Dog)
          //คนที่เป็นชาวเดนมาร์กดื่มชา
          where (n[i] == Nationality.Danish) == (d[i] == Drink.Tea)
          //บ้านสีเขียวอยู่ทางซ้ายของบ้านสีขาว
          where (c[i] == HouseColor.Green) == (c[i + 1] == HouseColor.White)
          //เจ้าของบ้านสีเขียวดื่มกาแฟ
          where (c[i] == HouseColor.Green) == (d[i] == Drink.Coffee)
          //คนที่สูบบุหรี่ยี่ห้อ Pall Mall เป็นคนเลี้ยงนก
          where (s[i] == Smoke.PallMall) == (p[i] == Pet.Bird)
          //เจ้าของบ้านสีเหลืองสูบบุหรี่ยี่ห้อ Dunhill
          where (c[i] == HouseColor.Yellow) == (s[i] == Smoke.DunHill)
          //คนที่อยู่บ้านหลังกลางดื่มนม
          where d[2] == Drink.Milk
          //คนที่เป็นชาวนอร์เวย์อยู่บ้านหลังแรก
          where n[0] == Nationality.Norwegian
          //คนที่สูบบุหรี่ยี่ห้อ Blends เป็นเพื่อนบ้านกับคนที่ดื่มน้ำ
          where ((s[i] == Smoke.Blend) ?
                (d[i - 1] == Drink.Water || d[i + 1] == Drink.Water) : true)
          //คนที่เลี้ยงม้าอยู่ติดกับคนที่สูบบุหรี่ยี่ห้อ Dunhill
          where ((p[i] == Pet.Horse) ?
                (s[i - 1] == Smoke.DunHill || s[i + 1] == Smoke.DunHill) : true)
          //คนที่สูบบุหรี่ยี่ห้อ Bulemaster ดื่มเบียร์
          where (s[i] == Smoke.BlueMaster) == (d[i] == Drink.Beer)
          //คนที่เป็นชาวเยอรมันสูบบุหรี่ยี่ห้อ Prince
          where (n[i] == Nationality.German) == (s[i] == Smoke.Prince)
          //คนที่เป็นชาวนอร์เวย์อยู่ติดกับบ้านสีฟ้า
          where ((n[i] == Nationality.Norwegian) ?
                (c[i - 1] == HouseColor.Blue || c[i + 1] == HouseColor.Blue) : true)
          //คนที่สูบบุหรี่ยี่ห้อ Blends อยู่ติดกับคนเลี้ยงแมว
          where (p[i] == Pet.Cat) ?
                (s[i - 1] == Smoke.Blend || s[i + 1] == Smoke.Blend) : true
          select 0.To(4).Select(x =>
              new {
                        Nationality = n[x],
                        HouseColor = c[x],
                        Smoke = s[x],
                        Drink = d[x],
                        Pet = p[x]
              });

คราวนี้ก็เรียกคำตอบออกมา

solutions.First().ForEach((man, i) =>
    Console.WriteLine("{0}t{1}t{2}t{3}t{4}t{5}",
        i + 1,
        man.Nationality.ToString().PadRight(12),
        man.HouseColor.ToString().PadRight(12),
        man.Smoke.ToString().PadRight(12),
        man.Drink.ToString().PadRight(12),
        man.Pet.ToString().PadRight(12))
);
//    Nationality       HouseColor      Smoke           Drink           Pet
//--------------------------------------------------------------------------------
//1     Norwegian       Yellow          DunHill         Water           Cat        
//2     Danish          Blue            Blend           Tea             Horse      
//3     British         Red             PallMall        Milk            Bird        
//4     German          Green           Prince          Coffee          Fish        
//5     Swedish         White           BlueMaster      Beer            Dog

เห็นไหมครับว่า LINCON เขียนง่ายเข้าใจง่าย
อะไรเป็น Input ก็ใส่เข้าไปใน Syntax from
อะไรที่เป็น Constraint ก็ใส่เข้าไปใน Syntax where
และสุดท้ายจะ Output ก็ใส่ที่ Syntax select

ถ้าสนใจลอง Download ไปเล่นดูได้ครับ
มี Source code ให้ด้วย
ไปที่ chaow.codeplex.com ครับ Smiley



Create Date : 22 พฤษภาคม 2553
Last Update : 22 พฤษภาคม 2553 18:42:50 น. 1 comments
Counter : 1298 Pageviews.

 
เยี่ยม


โดย: kt IP: 58.137.12.25 วันที่: 9 ธันวาคม 2553 เวลา:10:21:14 น.  

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]





New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.