เขียนเรื่อง ruby, rails เยอะแล้ว กลับมาที่ java บ้าง
วันก่อนผมอ่านเจอเรื่อง
Solving Sudokus in Javaคนที่ยังไม่รู้จัก sudokus ให้ลองดูคำอธิบายได้ที่
wikipedia on sudokus(อธิบายละเอียดยิบเลยครับ)
ที่สนใจก็คือ ผมยังไม่เคยได้ยินคำว่า Constraint Programming มาก่อน
ใน tutorial ข้างบนเขาใช้ library ที่ชื่อ
Koalog Constraint Solver ซึ่งเป็น commercial product
ผมก็เลยลอง search หา Library ที่เป็น opensource license ดู
เจอเจ้า
Cream: Class Library for Constraint Programming in Java
ผลผลิตจาก Japan (ดีที่ web site เขาเป็นภาษาอังกฤษ)
ลองดูวิธีการใช้ Cream solve Sudokus กัน
(เอกสารของ cream มีไม่เยอะ แต่โชคดีที่เขามีตัวอย่างให้ดู
รวมทั้งมีตัวอย่าง sudokus ด้วย ก็เลยแกะมาเล่าให้ฟังได้)
โดยเราจะใช้โจทย์เดียวกับ tutorial ที่อ้างถึงข้างบน
เริ่มด้วยการ define problem array ก่อน
static int prob[][] = {
{6,0,0,0,5,8,4,9,0},
{0,2,4,0,0,0,0,0,0},
{0,0,0,0,2,0,0,3,6},
{0,0,0,0,0,0,9,0,7},
{7,0,0,3,0,0,8,0,0},
{1,5,0,0,8,9,0,0,0},
{0,3,1,0,0,0,0,0,0},
{0,0,0,0,3,0,5,0,0},
{0,0,8,0,9,5,0,0,0}
};ก่อนที่จะ solve ก็ต้องมีการสร้างตัวแปรให้ cream รับรู้ก่อน
ในกรณีของเรา ก็คือ เราจะมีตัวแปรทั้งหมด 9 * 9 = 81 ตัว
โดยตัวแปรทั้งหมดจะต้องถูกสร้างภายใต้ context
networkNetwork net = new Network();
IntVariable v[][] = new IntVariable[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (prob[i][j] == 0) {
v[i][j] = new IntVariable(net, 1, 9);
} else {
v[i][j] = new IntVariable(net, prob[i][j]);
}
}
}
จะเห็นว่าถ้าค่าใน prob array เป็น 0 เราจะ new variable
ด้วย constructor
new IntVariable(net, 1, 9)ความหมายก็คือ ค่าใน variable นี้ เป็นไปได้ตั้งแต่ 1 ถึง 9
ส่วนกรณีที่มีค่าอยู่แล้ว ก็จะใช้ constructor
new IntVariable(net, x)โดย x ก็คือค่าของ variable นั้นๆเลย
ขั้นถัดไปก็คือการ declare constraint ของปัญหา
เริ่มด้วย
- แต่ละ row ห้ามมีเลขซ้ำกัน
IntVariable tmps[] = new IntVariable[9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
tmps[j] = v[i][j];
}
new NotEquals(net, tmps);
}
- แต่ละแถวห้ามมีเลขซ้ำกัน
for (int j = 0; j < 9; j++) {
for (int i = 0; i < 9; i++) {
tmps[i] = v[i][j];
}
new NotEquals(net, tmps);
}
- ในแต่ละ box 3 * 3 ห้ามมีตัวเลขซ้ำกัน
for (int bi = 0; bi < 3; bi++) {
for (int bj =0; bj < 3; bj++) {
int cnt = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
tmps[cnt++] = v[i+(bi*3)][j+(bj*3)];
}
}
new NotEquals(net, tmps);
}
}
จะเห็นว่า constraint ข้างบนใช้ constructor
NotEquals(net, array_of_variable)สร้างขึ้นมา
ความหมายก็คือ ในตัวแปรที่ผ่านเข้าไปทั้งหมดนั้น ห้ามมีตัวใดตัวหนึ่งซ้ำกันเลย
พอเสร็จจากขั้นการ declare constraint ก็เป็นขั้นการ solve แล้ว
Solver solver = new DefaultSolver(net);
Solution sol = solver.findFirst();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(sol.getIntValue(v[i][j]));
if (j < 8) {
System.out.print(",");
}
}
System.out.println();
}
โดยในการ call เราสามารถเลือก call โดยกำหนด timeout ได้ด้วย
จากการจับเวลาเครื่องผม
กรณีใช้ findFirst จะใช้เวลาประมาณ 76-80 ms
ส่วนกรณี findBest จะใช้เวลาประมาณ 90-100 ms
คนที่สนใจ Constraint Programming ลองเข้าไปดูที่นี่ครับ
