3.7.132. Logigraphe

A constraint which can be used for modelling the logigraphe problem. The logigraphe problem, see FigureΒ 3.7.29 for an instance taken fromΒ [Pitrat08], consists of colouring a board of squares in black or white, so that each row and each column contains a specific number of sequences of black squares of given size. A sequence of integers s 1 ,s 2 ,...,s m (pβ‰₯1) enforces:

  • a first block of s 1 consecutive black squares,

  • a second block of s 2 consecutive black squares,

  • .............................................,

  • a last block of s p consecutive black squares.

Each block of consecutive black squares must be separated by at least one white square. Finally, white squares may eventually precede (respectively follow) the first (respectively the last) block of black squares. The logigraphe problem is NP -completeΒ [UedaNagao96].

Figure 3.7.29. PartΒ (A):Β an instance of a logigraphe and the initial deductions achieved after posting the constraints, PartΒ (B):Β the corresponding unique solution.
ctrs/logigraphe

PartΒ (A) of FigureΒ 3.7.29 shows an instance of a logigraphe and the corresponding initial deductions achieved after posting the πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraints associated with each row and each column. We assume that each constraint achieves arc-consistency, which is actually the case when the πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraint is represented as a counter free automaton. A white or black square indicates an initial deduction (i.e.,Β setting a variable to 0 or to 1). PartΒ (B) of FigureΒ 3.7.29 provides the unique solution found after developing three choices,Each time we try to assign a value to a not yet fixed variable, the number of choices is incremented by 1 just before making the assignment. assuming that variables are assigned from the uppermost to the lowermost row. Within a given row, variables are assigned from the leftmost to the rightmost column. Value 0 is tried first before value 1. Seven additional choices are required for proving that this solution is unique. FigureΒ 3.7.30 displays the corresponding search tree. Within this figure, a variable V i,j (1≀i,j≀10) denotes the 0-1 variable associated with the i th row and the j th column of the board.

Figure 3.7.30. Search tree developed for the logigraphe instance of FigureΒ 3.7.29 (variables that are fixed by propagation were removed from the search tree)
ctrs/logigraphe_tree