Fill grid with colors following pattern rules

Question

I'm trying to solve this problem. Unfortunately I don't have a name for this kind of puzzle so I'm not sure what to search for. The closest examples I can find are Nonogram and Tomography puzzles.

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.

Here is an example easy small 4x4 grid with 3 colors:

rbg,rbr,grb,bgbg       <- (top-to-bottom column constraints)

    _,_,_,_     rgb    <- (row constraints)
    _,_,_,_     brg 
    _,_,_,_     b
    _,_,_,_     grbg

Solutions (2):

    r,r,g,b
    b,?,r,g     
    b,b,b,b     
    g,r,b,g 

? Can be either red or blue but not green.

Pattern examples below. Examples given 6-length sequences to pattern:

aaaaaa -> a
aabbcc -> abc
abbbbc -> abc
cabbbc -> cabc
bbbaac -> bac
abbaab -> abab
abcabc -> abcabc

Examples given pattern to potential solution sequences:

abc -> abc (3 length solution)
abc -> abcc, abbc, aabc (4 length solutions)
abc -> abccc, abbcc, abbbc, aabbc, aaabc (5 length solutions)

I've tried to solve it in C# or-tools and MiniZinc but the biggest problem I have is building the constraints. I can generate the patterns from a sequence (in c# imperative way) but then how to turn that into a constraint?

How I'm thinking about it: generate all potential sequences from each clue pattern. Then make a constraint for the corresponding row/col that says it must be one of those sequences.

Example from top row in above puzzle: rgb to [4-length sequences] -> rgbb, rggb, rrgb, and then add a constraint for that row: must equal one of these sequences.

Am I thinking about this right? Any smarter ways to do it?

=====================================

Edit after some progress:

This MiniZinc correctly solves the top row for the pattern abc which has 3 solutions of 4 length: aabc, abbc, abcc.

include "globals.mzn";

array [1..4, 1..4] of var 1..3: colors;

constraint regular(row(colors, 1), 4, 3, 
[|
  % a, b, c
    2,0,0| % accept 'a'
    2,3,0| % accept 'a' or 'b' ?
    0,3,4| % accept 'b' or 'c' ?
    0,0,4| % accept 'c'
|], 1, {4}); 

% Don't care about rest of grid for now.
constraint forall(i,j in 1..4 where i > 1) (row(colors, i)[j] = 1);

solve satisfy;

output [show(colors)]; 

However I'm not sure how to handle larger grids with many patterns other than hardcoding everything like this. I will experiment a bit more.

Answer 1

The constraints you are talking about seem to be easily represented as regular expressions. For example your abc example with varying length can be caught using the regular expression abc.*, which requires one a then one b, and then one c, it will accept anything else afterwards.

In MiniZinc these kinds of constraints are expressed using the regular predicate. The regular predicate simulates an automaton with accepting states. By providing the allowed state-transitions the model is constraint.

The example expression abc.* would be enforced by the following constraint item:

% variables considered, nr states, input values
constraint regular(VARS, 4, 1..3, [|
    % a, b, c
    2,0,0| % accept 'a'
    0,3,0| % accept 'b'
    0,0,4| % accept 'c'
    4,4,4| % accept all
|], 1, {4}); % initial state, accepting states