My Constraint Programming Blog

The model: nonogram_create_automaton2.mzn.

nonogram_regular.mzn

In At last, a Nonogram solver using regular constraint in MiniZinc I wrote about a Nonogram solver in MiniZinc using the regular solver, nonogram_regular.mzn. The drawback of this version is that an external program (make_nonogram_automata.pl) was needed to convert the Nonogram patterns (clues) to an automaton (finite states) for use in the regular constraint.

nonogram_create_automaton.mzn

In an update some hours later in the same blog post, the variant nonogram_create_automaton.mzn was mentioned. This is an "all MiniZinc" solution where the model also calculating the automata. The drawback of this was that the states is var int (decision variables), so it couldn't use the optimized regular constraint that some solvers (e.g. Gecode/FlatZinc) has implemented (this optimized version of regular is in fact the reason that Gecode/FlatZinc is so fast for the nonogram_regular.mzn model.) Instead a tweaked version of MiniZinc's standard regular constrant was used.

nonogram_create_automaton2.mzn

After a short discussion about this with Mikael Lagerkvist (of the Gecode team) the other day, we agreed that it would be nice thing to have the states calculated as "par" variables (i.e. not decision variables), thus the optimized regular could be used.

So I went got back to the drawing board and wondered how to do this. The solution I've found is not pretty, in fact it is hairy, very hairy: nonogram_create_automaton.mzn.

It is now as fast as nonogram_regular.mzn for solvers that use optimized version of regular, especially on the P200 problem.

Problem instances

Here are the problem instances I have tested (they are the same as used before.)

• Bear: nonogram_bear.dzn
• Car: nonogram_car.dzn
• Castle: nonogram_castle.dzn
• Crocodile: nonogram_crocodile.dzn
• Difficult: nonogram_difficult.dzn
• Dragonfly: nonogram_dragonfly.dzn
• Griddler: nonogram_griddler.dzn
• Hard: nonogram_hard.dzn
• Hen: nonogram_hen.dzn
• House: nonogram_house.dzn
• Lambda: nonogram_lambda.dzn
• n2: nonogram_n2.dzn
• n3: nonogram_n3.dzn
• n4: nonogram_n4.dzn
• n5: nonogram_n5.dzn
• n6: nonogram_n6.dzn
• Nonunique: nonogram_nonunique.dzn
• Optima: nonogram_optima.dzn
• P199: nonogram_p199.dzn
• P200: nonogram_p200.dzn
• ps: nonogram_ps.dzn
• Simple: nonogram_simple.dzn
• Simple2: nonogram_simple2.dzn
• Soccer player: nonogram_soccer_player.dzn
• t1: nonogram_t1.dzn
• t3: nonogram_t3.dzn

Comparison of calculating of the states

Now, let's compare the two different versions of calculating the automaton states.

First method: using decision variables

This is the version that is used in nonogram_create_automaton.mzn. The states are represented by the 2-dimensional array states.

states[1,1] = 1
/\ 
states[1,2] = 2
/\
forall(i in 2..len-1) (
   if i in zero_positions then
      states[i,1] = i+1 /\
      states[i,2] = 0 /\
      states[i+1,1] = i+1 /\
      states[i+1,2] = i+2
   else 
      if not(i - 1 in zero_positions) then
        states[i,1] = 0 /\
        states[i,2] = i+1
      else 
        true
      endif
   endif
)
/\
states[len,1] = len
/\
states[len,2] = 0

Quite neat, and relatively easy to understand.

Second method: no decision variables

And this is the non-decision variable version of calculating the finite states used in nonogram_create_automaton2.mzn. Note that states are represented by a 1-dimensional array, which is - as I have understood it - a requirement for this kind of initialisation of an array. It is also the cause of this hairyness.

array[1..2*len] of 0..len*2: states = 
[1, 2] ++
[
   if i div 2 in zero_positions then
       if i mod 2 = 0 then
        0
       else
        (i div 2) + 1
       endif
   elseif (i-1) div 2 in zero_positions then
       if i mod 2 = 0 then
        (i div 2)+1
       else
        (i div 2)+2
       endif
   else
     if not( (((i-1) div 2) - 1) in zero_positions) then
        if i mod 2 = 0 then
           (i div 2) + 1
        else 
          if (i div 2) + 1 in zero_positions then
              (i div 2) + 2
          else 
              0
          endif
        endif
      else
         if i mod 2 = 0 then
             (i div 2) + 1
         else 
            if not((i div 2) + 1 in zero_positions) then
               0
            else 
               (i div 2) + 2 
            endif
         endif
      endif
   endif
| i in 3..2*(len-1)]
++
[len, 0]

It could most probably be done in a more elegant fashion. And maybe I will think more about this later on.