I have a MiniZinc model of placing character sequences, or "words", on a crossword-like grid. This is really a packing problem where the positions and orientations of the "words" must be determined.
The decision variables are the starting position and the orientation (up, down, left, right or diagonal) of each word. These are the the primary unknowns.
I use the entries of the grid cells as secondary unknowns to display the character in each occupied cell.
With the words "grows" and "drop" placed in a 4 by 5 grid, I would like to obtain solutions like
d
grows
o
p
p
grows
r
d
I should add that the letters are coded as their alphabetical position.
In a solution the entries of the occupied cells become fixed, but the unoccupied cells remain unfixed. This results in lots of unwanted solutions which prevent me from focusing on the valid solutions.
How should I handle these unfixed variables?
Thank you.
I have tried a minimization approach by assigning an open space the value 0. This, however, favors solutions with overlaps on higher valued symbols.
Added a day later: Here is my minimal reproducible version using two words. The words 'edge' and 'egg' could overlap on the e's and the g's.
% minrep.mzn
int: mrows = 3 ; int: ncols = 4 ;
int: nwords = 2 ; int: nletters = 7 ;
array[1..nwords] of int: wordstart = [1, 5] ; array[1..nwords] of int: wordlength = [4,3] ;
% only two words: 'edge' and 'egg';
array[1..nletters] of int: wordletternumbers = [e, d, g, e, e, g, g ] ;
int: a = 1; int: b = 2; int: c = 3; int: d = 4; int: e = 5; int: f = 6; int: g = 7;
int: numletters = 8 ; % the length of this truncated "alphabet"
array[1..numletters] of string: letters = ["a", "b", "c", "d", "e", "f", "g", "h" ] ;
% decision variables, the primary unknowns array[1..nwords, 1..2] of var 1..max(mrows,ncols): rowcolofwi ;
% secondary unkowns: letter numbers in the cells array[1..mrows, 1..ncols] of var 1..numletters: letternumberofrc ;
constraint forall (ll in 0..(-1+wordlength[1])) ( letternumberofrc[ rowcolofwi[1,1], rowcolofwi[1,2]+ll] = wordletternumbers[wordstart[1]+ll] ) ;
constraint forall (ll in 0..(-1+wordlength[2])) ( letternumberofrc[ rowcolofwi[2,1]+ll, rowcolofwi[2,2]] = wordletternumbers[wordstart[2]+ll] ) ;
%constraint letternumberofrc[2,1] = e ; % this forces 'edge' into the second row %constraint letternumberofrc[3,1] = e ; % this forces 'edge' into the third row
solve satisfy ;
output [ " " ++ if is_fixed(letternumberofrc[rr,cc]) then letters[fix(letternumberofrc[rr,cc])] else "." endif ++ " " ++ if cc < ncols then "" else "\n" endif | rr in 1..mrows , cc in 1..ncols ]++ ["\n"] ;
}