Constraint Programming

เขียนเรื่อง 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 network

Network 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 ห้ามมีเลขซ้ำกัน
  

  // แต่ละ 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);
  }

  
  
  
• แต่ละแถวห้ามมีเลขซ้ำกัน
  

  // แต่ละ column ห้ามซ้ำกัน
  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 ห้ามมีตัวเลขซ้ำกัน
  

  // ในแต่ละ box 3x3 ห้ามมีตัวเลขซ้ำกัน
  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 ลองเข้าไปดูที่นี่ครับ

• www.constraint.org