#### Problem

Puzzle description: The player is given an empty game board (varying size) that they must fill withn-colors, using clue patterns for the rows and columns. Each clue pattern is the sequence of colors in that row/col but with consecutive duplicates removed.

We can also write the hints using

**regular expressions**. E.g. the first row would have

**r+g+b+**.

#### Constraint programming

Constraint solvers like Minizinc/Gecode has a

This is what a regular expression algorithm will do in the background: execute a state machine.

**regular constraint**[2]. Not for the fainthearted:Regular Constraint in Minizinc |

Let's see how we can model the first row with this. Obviously the pattern

**rgb**allows for the following solutions: "

*rrgb"*, "

*rggb"*, "

*rgbb"*. We encode the colors with integers. The decisions variables \(x\) are now just an array of integers between \(1 \le x_i \le nc\) where \(nc\) is the number of colors. This small problem can be encoded in Minizinc as:

include "globals.mzn"; int: n = 4; % length of row int: nc = 3; % number of colors array[1..n] of var 1..nc: x; int: q = 4; % number of states int: q0 = 1; % initial state set of int: q1 = {4}; % final state array[1..q,1..nc] of int: p = [| % r g b 2, 0, 0 | % 1: accept r 2, 3, 0 | % 2: accept r or g 0, 3, 4 | % 3: accept g or b 0, 0, 4 | % 4: accept b |]; constraint regular(x, q, nc, p, q0, q1); solve satisfy; output [show(x)];

The state transition table

**p**is often depicted as a graph. In this case it is very simple:

The solution with Minizinc/Gecode looks like:

Possible solutions for first row |

where \(1=r, 2=g, 3=b\).

This can be repeated for each row and column with non-trivial patterns. There must be a better way to do this, but here is my attempt:

include "globals.mzn"; int: m = 4; % number of rows int: n = 4; % length of columns int: nc = 3; % number of colors % r = 1 % g = 2 % b = 3 array[1..m,1..n] of var 1..nc: x; int: q = 4; % number of states int: q0 = 1; % initial state set of int: q1 = {4}; % final state array[1..q,1..nc] of int: p_rgb = [| % r g b 2, 0, 0 | % 1: accept r 2, 3, 0 | % 2: accept r or g 0, 3, 4 | % 3: accept g or b 0, 0, 4 | % 4: accept b |]; array[1..q,1..nc] of int: p_brg = [| % r g b 0, 0, 2 | % 1: accept b 3, 0, 2 | % 2: accept b or r 3, 4, 0 | % 3: accept r or g 0, 4, 0 | % 4: accept g |]; array[1..q,1..nc] of int: p_rbg = [| % r g b 2, 0, 0 | % 1: accept r 2, 0, 3 | % 2: accept r or b 0, 4, 3 | % 3: accept b or g 0, 4, 0 | % 4: accept g |]; array[1..q,1..nc] of int: p_rbr = [| % r g b 2, 0, 0 | % 1: accept r 2, 0, 3 | % 2: accept r or b 4, 0, 3 | % 3: accept b or r 4, 0, 0 | % 4: accept r |]; array[1..q,1..nc] of int: p_grb = [| % r g b 0, 2, 0 | % 1: accept g 3, 2, 0 | % 2: accept g or r 3, 0, 4 | % 3: accept r or b 0, 0, 4 | % 4: accept b |]; %---- row 1 constraint regular(row(x, 1), q, nc, p_rgb, q0, q1); %---- row 2 constraint regular(row(x, 2), q, nc, p_brg, q0, q1); %---- row 3 constraint row(x, 3) = [3,3,3,3]; %---- row 4 constraint row(x, 4) = [2,1,3,2]; %---- col 1 constraint regular(col(x, 1), q, nc, p_rbg, q0, q1); %---- col 2 constraint regular(col(x, 2), q, nc, p_rbr, q0, q1); %---- col 3 constraint regular(col(x, 3), q, nc, p_grb, q0, q1); %---- col 4 constraint col(x, 4) = [3,2,3,2]; solve satisfy; output [show(x)];

Notice that all the

**p**matrices are essentially column permuted versions of each other. The results are:

Solution with Minizinc/Gecode |

#### MIP Formulation

Inside a MIP we only have linear equations to our disposal. One way to attack the above problem is to generate all possible "strings". I.e. we would have:

- Row 1 is "
*rrgb"*, "*rggb"*or "*rgbb"* - Row 2 is "
*bbrg"*, "*brrg"*or "*brgg"* - Row 3 is '
*bbbb*' - Row 4 is '
*grbg*' - Etc.

The model equations can look like:

Here

**rows(i,k,j,c)=true**if the k-th version of row i has color c in column position j. The sets**ik(i,k)**and**jk(j,k)**contain the valid elements**k**for each row or column (rows and columns have different numbers of allowed patterns, e.g. row 3 has only one allowed pattern: '*bbbb*').
After adding a cut to forbid previously found solutions and looping until the model becomes infeasible we get the two solutions:

---- 104 PARAMETER sols solutions INDEX 1 = iter1 R G B i1.j1 1.000 i1.j2 1.000 i1.j3 1.000 i1.j4 1.000 i2.j1 1.000 i2.j2 1.000 i2.j3 1.000 i2.j4 1.000 i3.j1 1.000 i3.j2 1.000 i3.j3 1.000 i3.j4 1.000 i4.j1 1.000 i4.j2 1.000 i4.j3 1.000 i4.j4 1.000 INDEX 1 = iter2 R G B i1.j1 1.000 i1.j2 1.000 i1.j3 1.000 i1.j4 1.000 i2.j1 1.000 i2.j2 1.000 i2.j3 1.000 i2.j4 1.000 i3.j1 1.000 i3.j2 1.000 i3.j3 1.000 i3.j4 1.000 i4.j1 1.000 i4.j2 1.000 i4.j3 1.000 i4.j4 1.000

Reference [3] gives a direct approach to represent the regular constraint in a MIP. I think this will be somewhat messy because we have multiple regular expressions in our model.

#### References

- Constraint programming; Fill grid with colors following pattern rules, https://stackoverflow.com/questions/49101990/constraint-programming-fill-grid-with-colors-following-pattern-rules
- Minizinc Documentation - Standard Library. Extensional constraints (table, regular etc.), http://www.minizinc.org/doc-lib/doc-globals-extensional.html
- Côté MC., Gendron B., Rousseau LM. (2007)
*Modeling the Regular Constraint with Integer Programming*. In: Van Hentenryck P., Wolsey L. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2007. Lecture Notes in Computer Science, vol 4510. Springer, Berlin, Heidelberg

## No comments:

## Post a Comment