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+.
|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:
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:
Notice that all the p matrices are essentially column permuted versions of each other. The results are:
|Solution with Minizinc/Gecode|
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'
Reference  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.
- 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