- A) A problem representation for output
where the "_" (a letter to be identified) is represented as a unique number (index in L), and
"*" is represented as 0 (zero):
[
1, 2, 3, 0, 0,
4, 5, 6, 7, 0,
8, 9, 10, 11, 12,
0, 13, 14, 15, 16,
0, 0, 17, 18, 19,
]
- B) the words (segments)
where all non "*" are converted to a unique number
(representing the index in the decision variable L).
All"*" is represented as 0 (zero) as a fillout value:
[
% across
1, 2, 3, 0, 0,
4, 5, 6, 7, 0,
8, 9,10,11,12,
13,14,15,16, 0,
17,18,19, 0, 0,
% down
1, 4, 8, 0, 0,
2, 5, 9,13, 0,
3, 6,10,14,17,
7,11,15,18, 0,
12,16,19, 0, 0,
]);
- C) A bunch of
table constraints for the segments
with the appropriate word size array connected.
constraint
% across
table([L[1], L[2], L[3]], words3)
/\ table([L[4], L[5], L[6], L[7]], words4)
/\ table([L[8], L[9], L[10], L[11], L[12]], words5)
/\ table([L[13], L[14], L[15], L[16]], words4)
/\ table([L[17], L[18], L[19]], words3)
% down
/\ table([L[1], L[4], L[8]], words3)
/\ table([L[2], L[5], L[9], L[13]], words4)
/\ table([L[3], L[6], L[10], L[14], L[17]], words5)
/\ table([L[7], L[11], L[15], L[18]], words4)
/\ table([L[12], L[16], L[19]], words3)
;
L used here is an array of decision variables of length N+1 defined
in crossword3.mzn:
array[0..N] of var 1..num_letters: L;
Note that it has the dimensions 0..N to be able to handle all index in unicity constraint (which is 0 for "*" cells).
- D) The unicity constraint (in crossword3.mzn) then
ensures that each segments (words) are unique:
constraint
forall(I,J in 1..num_segments where I < J) (
% 1-letter words must be able to be the same across and down
if sum(K in 1..max_length) ( bool2int(segments[I,K] > 0 ) ) = 1 /\
segments[I,1] = segments[J,1]
then
true
else
not(forall(K in 1..max_length) (
L[segments[I,K]] = L[segments[J,K]]
))
endif
)
;
Note the exception for 1-letter words which are - of course - the same across
and down.