CSP กับ คำถามของไอน์สไตน์

ช่วงนี้หันกลับมาเรียนรู้ Constraint programming ใหม่
กะจะเอาจริงมากขึ้น
คราวก่อนพลาดไปตรงที่
ดันไปใช้ constraint programming library บน Oz
ทำให้เปิดศึกสองด้าน เพราะต้องเรียนรู้ Oz ไปด้วย

มาคราวนี้เลยเลือกใช้ choco
ซึ่ง base อยู่บน java
(จริงๆอยากลองใช้ chr บน prolog นะ
แต่จะเข้าข่ายเดิมอีก ก็คือ ไปไม่ถึงไหน)

ลองโจทย์แรกก่อน Zebra Puzzle
(หรือที่นิยมเรียก "คำถามของไอน์สไตน์")

modeling ของเราก็คือ
มีบ้าน 5 หลัง
เรากำหนดให้แต่ละหลังแทนด้วยตัวเลข 1 ถึง 5

จากนั้นเราก็จะกำหนด variable มาเพื่อระบุว่า
คุณสมบัติที่ variable นั้น represent นั้น, มันตรงกับบ้านหลังใด เช่น
var colors[GREEN] = 3 (บ้านหลังที่ 3 เป็นสีเขียว)
แน่นอนว่า ในเบื้องต้น เราไม่รู้หรอกว่าบ้านสีเขียวจะตรงกับหลังไหน
ดังนั้น เราจะกำหนดแบบนี้แทน
var colors[GREEN] = 1..5
นั่นคือ บ้านที่เป็นสีเขียวเป็นไปได้ตั้งแต่หลังที่ 1 ถึงหลังที่ 5

ว่าแล้วก็ลองเขียนโปรแกรมดู
เริ่มจากสร้าง problem ขึ้นมาก่อน

Problem pb = new Problem();

จากนั้นก็สร้างตัวแปร Domain variable

IntDomainVar[] colors = pb.makeEnumIntVarArray("colors", 5, 1, 5);
IntDomainVar[] nationals = pb.makeEnumIntVarArray("nationals", 5, 1, 5);
IntDomainVar[] pets = pb.makeEnumIntVarArray("pets", 5, 1, 5);
IntDomainVar[] professions = pb.makeEnumIntVarArray("professions", 5, 1, 5);
IntDomainVar[] drinks = pb.makeEnumIntVarArray("drinks", 5, 1, 5);

parameter ตัวที่ 2 คือ ขนาด ของ array ที่ต้องการสร้าง
ส่วนความหมายของ parameter 1, 5 ที่อยู่ด้านหลัง ก็คือ range ของ domain value
ซึ่งหมายความว่ามี ค่าที่เป็นไปได้คือ 1,2,3,4 หรือ 5

เมื่อมี variable พร้อมแล้ว
ก็มาถึงขั้นที่ต้องกำหนด constraint
เริ่มด้วย constraint แรก
"The Englishman lives in the red house."
เขียนได้ดังนี้

pb.post(pb.eq(nationals[ENGLISH], colors[RED]));

pb.post คือคำสั่งที่สั่ง post constraint เข้าสู่ problem space.

พวกเงื่อนไขหลักๆยังง่ายอยู่ ก็ลอกๆตามไป

// The Spaniard has a dog:
pb.post(pb.eq(nationals[SPANISH], pets[DOG]));          
// The Japanese is a painter
pb.post(pb.eq(nationals[JAPANESE], professions[PAINTER]));              
// The Italian drinks tea
pb.post(pb.eq(nationals[ITALIAN], drinks[TEA]));
// The Norwegian lives in the first house on the left
pb.post(pb.eq(nationals[NORVEGIAN], 1));                
// The owner of the green house drinks coffee:
pb.post(pb.eq(colors[GREEN], drinks[COFFEE]));
// The green house is on the right of the white house
pb.post(pb.eq(colors[GREEN], pb.plus(colors[WHITE], 1)));
// The sculptor breeds snails
pb.post(pb.eq(professions[SCULPTOR], pets[SNAILS]));
// The diplomat lives in the yellow house
pb.post(pb.eq(professions[DIPLOMAT], colors[YELLOW]));
// They drink milk in the middle house
pb.post(pb.eq(drinks[MILK], 3));
// The violinist drinks fruit juice
pb.post(pb.eq(professions[VIOLINIST], drinks[JUICE]));

ตัวที่เริ่มยาก (ยากตรงจะใช้ syntax ของ choco อันไหนดี)
ก็คือ "The Norwegian lives next door to the blue house"
ความหมายก็คือ |Norwegian - Blue| = 1
แต่ absolute ใน choco มันรับ parameter แปลกๆ ก็เลยหันไปใช้พวก Or แทน
ได้ออกมาอย่างนี้

// The Norwegian lives next door to the blue house
pb.post(
        pb.makeDisjunction(new Constraint[] {
                pb.eq(pb.minus(nationals[NORVEGIAN], colors[BLUE]), 1),
                pb.eq(pb.minus(nationals[NORVEGIAN], colors[BLUE]), -1)
}));
// The fox is in the house next to the doctor’s
pb.post(
        pb.makeDisjunction(new Constraint[] {
                pb.eq(pb.minus(pets[FOX], professions[DOCTOR]), 1),
                pb.eq(pb.minus(pets[FOX], professions[DOCTOR]), -1)
}));
                
// The horse is in the house next to the diplomat’s:
pb.post(
        pb.makeDisjunction(new Constraint[] {
                pb.eq(pb.minus(pets[HORSE], professions[DIPLOMAT]), 1),
                pb.eq(pb.minus(pets[HORSE], professions[DIPLOMAT]), -1)
}));

สุดท้ายก็กฎพื้นฐานที่ว่า บ้านของแต่ละคุณสมบัติ ต้องไม่ซ้ำกัน
เช่นบ้านแต่ละหลังต้องสีไม่ซ้ำกับบ้านหลังอื่นๆ

pb.post(pb.allDifferent(colors));
pb.post(pb.allDifferent(nationals));
pb.post(pb.allDifferent(pets));
pb.post(pb.allDifferent(professions));
pb.post(pb.allDifferent(drinks));

เมื่อ define constraint เสร็จ ก็สั่งให้มันค้นหาคำตอบให้เราได้
โดยเราสามารถใช้ method getVal เพื่อดึงค่าคำตอบจาก Domain variable ได้เลย

pb.solve();
pb.getSolver().getSearchSolver().restoreBestSolution();
                
// who drink waters
for (int i = 0; i < 5; i++) {
        if (nationals[i].getVal() == drinks[WATER].getVal()) { // found
                System.out.println(map.get(i) + " drink waters");
        }
}
// who has zebra
for (int i = 0; i < 5; i++) {
        if (nationals[i].getVal() == pets[ZEBRA].getVal()) {
                System.out.println(map.get(i) + " has zebra");
        }
}

Note: ใช้ java เขียนพวก declarative นี่ช่างเยิ่นเย้อจริงๆ
ให้สั้นลงอีกหน่อย ก็คงต้องใช้ groovy (ตัวอย่าง Groovy ที่เรียกใช้ choco)