Math
Variables

A boolean variable $\text{cell}_{i,j}$ per cells of the grid, set to true when the cell is shaded, false oterhwise.
$$\forall i,j \in [1,15]^2, \text{cell}_{i,j} = \{0,1\}$$
And that’s enough !
Constraints
Any column and row should respect its sequence in BLOCKS
. To do so,
each sequence of BLOCKS
is turned into a Deterministic Finite
Automaton (DFA). There is a gap between two consecutive blocks, before
the first block and after the last block of a sequence there can be a
gap. The length of each block is injected in the DFA. Any gap is encoded
with a ‘0’s and any block by ‘1’s.
The constraint needed here is named regular. It takes a finite sequence variables and a DFA as input. With the help of a vocabulary (available values, in our case 0 and 1) and a grammar (the allowed sequence), the constraint constructs only valid words of a given size (the variables length). It ensures a very good level of filtering (AC), but the major difficulty relies on building the DFA.
There are two ways to create it: based on a regular expression or describing all states and transitions.
Objective
The objective is to find a solution that satisfies each constraint.
Feedback
Was this page helpful?
Glad to hear it! Please tell us how we can improve.
Sorry to hear that. Please tell us how we can improve.