Sudoku Solver in Mozart

คราวก่อนเคยเขียนเรื่อง Constraint Programming ไปแล้ว
ครั้งนั้นใช้ java

วันนี้จะลองใช้ Mozart Oz แก้ปัญหา sudoku บ้าง
เนื่องจากยังเขียน Oz ไม่เป็นเลย
ก็เลยไปลอก source code ของคนอื่นมาศึกษา
ต้นฉบับ

  Root = {Map {List.make 9}
          fun {$ Row}
      Row = {List.make 9}
      Row ::: 1#9
      {FD.distinct Row}
      Row
    end
   }

ประโยคข้างบนนี้ จะทำการสร้าง 2 Dimension Array ขนาด 9x9
ผลลัพท์ที่ได้เก็บในตัวแปร Root
fun ก็คือการ declare procedure
ส่วน fun {$ Row} => ตัว $ หมายถึง anonymous procedure

ถ้าลองเทียบเคียงกับ ruby ดู

root = Array.new(9).map {|row|
  row = Array.new(9)
}    

ส่วนที่ ruby ไม่มีก็คือ

• Row ::: 1#9
  หมายความว่า แต่ละ column สามารถเป็นได้ตั้งแต่เลข 1 ถึง 9 (domain)
  
• FD.distinct
  อันนี้เป็นประโยคที่กำหนด Constraint ใน Oz
  ความหมายก็คือ ตัวเลขในแถวเดียวกันห้ามซ้ำกัน
  

  %% All numbers in each column are distinct
  for X in 1;X=<9;X+1 do
     {FD.distinct
      {FoldR Root fun {$ Row Prev} {Nth Row X}|Prev end nil} 
     }
  end

FoldR คืออะไร
ลองเทียบกับ Ruby ดู

x = [[1,2,3],[11,12,13]].inject([]) {|prev, row|    
  prev << row[0] 
  prev 
}
x # => [1, 11]

FoldR น่าจะเทียบได้กับ Ruby Enumerable Inject
Nth ก็คือการ access array ที่ตำแหน่ง index ที่ระบุ
ส่วน | นั้น ก็คงคล้าย << ใน ruby
เพียงแต่ทิศทางจะกลับกัน << เป็นการ insert ต่อท้าย
ส่วน | เป็นการ append ข้างหน้า
Note: ถ้าเป็น lisp แล้ว | ก็คือ procedure cons นั่นเอง
(cons 1 (list 2 3 4)) => (1 2 3 4)

ถัดไปก็คือ constraint ของ 3x3 square

 %% All numbers in each 3x3 square are distinct
 for X in 0;X=<2;X+1 do
     for Y in 0;Y=<2;Y+1 do
        {FD.distinct
         {FoldR 
          {List.filterInd Root fun {$ I Row} I>=1+X*3 andthen I=<3+X*3 end}
          fun {$ Row Prev}
             {Append
              {List.filterInd Row fun {$ I Col} I>=1+Y*3 andthen I=<3+Y*3 end} 
              Prev
              }
          end
          nil
         }
        }
     end
 end

ใน ruby ไม่มี method ที่เทียบเคียงกับ filterInd
แต่ถ้าจะ implement ด้วย ruby ก็จะมีหน้าตาแบบนี้

class Array 
  def filterInd  
    tmp = []
    self.each_with_index {|elm, i|
      tmp << elm if yield i
    }
    tmp
  end
end

| กับ append ต่างกันคือ

{Show {Append [1 2 3] [5 6]}} => [1 2 3 5 6]
{Show [1 2 3] | [5 6]} => [[1 2 3] 5 6]

เทียบกับ Ruby

[1,2,3] << [5,6] # => [1,2,3,[5,6]]
[1,2,3] + [5,6] # => [1,2,3,5,6]

สุดท้าย

  %% Process specs
  {List.forAllInd Spec
   proc {$ Y R}
      Row={Nth Root Y}
   in
      {List.forAllInd R
       proc {$ X I}
          if {Not {IsFree I}} then
             {Nth Row X} :: I 
          end
       end
      }
   end
  }
  %% Search...
  {FD.distribute ff {Flatten Root}}

{Nth Row X} :: I ก็คือการระบุค่าลงไปใน
variable ตัวนั้น ว่าให้มีค่าตามโจทย์ที่ให้มา (default คือ อะไรก็ได้ที่อยู่ระหว่าง 1-9)
ส่วน FD.distribute ff ก็คือระบุให้ใช้
First Faile distribute strategy

จากการทดลอง run ได้ search graph หน้าตาแบบนี้



เวลาที่ใช้ search = 10ms (เร็วกว่าตอนทดลองใน java 8 เท่า)