Regular Constraints

Here is an interesting problem (1) that can be stated in terms of regular expressions.

Problem

Puzzle description: The player is given an empty game board (varying size) that they must fill with n-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 regular constraint [2]. Not for the fainthearted:

Regular Constraint in Minizinc

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

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

Too bad Minizinc is not printing the matrix in a nicer way, but with some effort we can see this is correct.

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

1. Constraint programming; Fill grid with colors following pattern rules, https://stackoverflow.com/questions/49101990/constraint-programming-fill-grid-with-colors-following-pattern-rules
2. Minizinc Documentation - Standard Library. Extensional constraints (table, regular etc.), http://www.minizinc.org/doc-lib/doc-globals-extensional.html
3. 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