5 ms·

Crossword puzzles! They make very interesting combinatorial problems (both for solving and creating grids). I recently had a ton of fun writing a constraint pro

Crossword puzzles! They make very interesting combinatorial problems (both for solving and creating grids). I recently had a ton of fun writing a constraint programming model that generates grids, including the automatic placement of black squares (this was the main modeling challenge). This model is useful for creating grids using short word lists (which is the case for e.g. thematic grids).

saulpw 3y ago
Very nice! Have you seen the talk "How a File Format Led to a Crossword Scandal"[0]? Or the largest collection of crossword data on the planet[1]? Source: it me. [0] https://www.youtube.com/watch?v=9aHfK8EUIzg https://www.youtube.com/watch?v=9aHfK8EUIzg [1] https://xd.saul.pw https://xd.saul.pw
- polivier 3y ago
  This is fascinating, I had no idea about the gridgate scandal!
mzl 3y ago
What model did you end up using? And what system did you do it in? My immediate guess on how to model it would be to create reified constraints for the wordlists of different lengths (the constraints in chapter 22 of https://www.gecode.org/doc-latest/MPG.pdf https://www.gecode.org/doc-latest/MPG.pdf). For each square, use standard logical constraints to check if it is the start of a word (previous square a black one, this square not a black one), and how long the word is (using backwards counting of runs). These can be used to trigger the reified constraints above. If the word-lists are short-ish enough, then an alternative for the above model would be to model the whole words using MDD or regular expression constraints, with an added control variable and setting all values as don't-care for the false case.
- polivier 3y ago
  The problem mentioned in the Gecode documentation example is different than the one I solve. In their case, they start with a WxH grid with known black square positions, and their model essentially answers the following question: "Given a crossword grid template and word list, does there exist a feasible assignment of words for the template?" I my case, the black square positions are unknown, so the question instead is: "Given an empty crossword grid and a word list, does there exist a template allowing a feasible assignment of words for the grid?" Your intuition of how I modeled this is mostly correct, I used custom TABLE constraints for the words, that can be triggered on or off depending on the values of boolean variables. I used CP-SAT to model this, and if you're interested in the technical side of things, I've discussed it in great detail here: https://pedtsr.ca/2023/generating-crossword-grids-using-constraint-programming.html https://pedtsr.ca/2023/generating-crossword-grids-using-cons... It turns out that there are many weird complexities to take into account when the black square positions are unknown.
  - mzl 3y ago
    Just saw that it looks like an upcoming release of OR-Tools might include reified tables: https://github.com/google/or-tools/commit/94f3d9b46870e7ea04518c6f52734f0ebed8fb1f https://github.com/google/or-tools/commit/94f3d9b46870e7ea04...
    - polivier 3y ago
      Yes, Laurent was nice enough to add this feature. I'm curious to see the difference in performance this will have over the workaround that I used.
  - mzl 3y ago
    Thanks for the link. I think that your version of getting to a reified extensional constraint (your table method) looks like a reasonable way to do it, and probably works quite well for OR-Tools CP-SAT in particular. Another way to do it directly is to embed the control variable in the table, with a full set of all possible tuples for when the control variable is false. This, however, gives a large blow-up of the table size, especially for wide tables/long words and might be too expensive. Using compressed/smart/cartesian product tables or MDD constraints if the system supports it would solve this (OR-Tools does not, AFAIK). As for the Gecode model, my idea was that the way to model the words using separate element constraint for each letter could reasonably be extended into a model for reified words by changing the element constraints to tables over the triple <control variable, index, letter> in the above way. The benefit is that one would not trigger the combinatorial blow-up one gets for the above with a full table over the whole word since it is only a single letter. In a related case, I used reified extensional constraints specified using regular expressions in https://github.com/zayenz/cp-mod-ref-2019-patchwork https://github.com/zayenz/cp-mod-ref-2019-patchwork to optionally place polyominoes on a grid.

saulpw 3y ago

Very nice! Have you seen the talk "How a File Format Led to a Crossword Scandal"[0]? Or the largest collection of crossword data on the planet[1]? Source: it me. [0] https://www.youtube.com/watch?v=9aHfK8EUIzg https://www.youtube.com/watch?v=9aHfK8EUIzg [1] https://xd.saul.pw https://xd.saul.pw

polivier 3y ago
This is fascinating, I had no idea about the gridgate scandal!

mzl 3y ago

What model did you end up using? And what system did you do it in? My immediate guess on how to model it would be to create reified constraints for the wordlists of different lengths (the constraints in chapter 22 of https://www.gecode.org/doc-latest/MPG.pdf https://www.gecode.org/doc-latest/MPG.pdf). For each square, use standard logical constraints to check if it is the start of a word (previous square a black one, this square not a black one), and how long the word is (using backwards counting of runs). These can be used to trigger the reified constraints above. If the word-lists are short-ish enough, then an alternative for the above model would be to model the whole words using MDD or regular expression constraints, with an added control variable and setting all values as don't-care for the false case.

polivier 3y ago
The problem mentioned in the Gecode documentation example is different than the one I solve. In their case, they start with a WxH grid with known black square positions, and their model essentially answers the following question: "Given a crossword grid template and word list, does there exist a feasible assignment of words for the template?" I my case, the black square positions are unknown, so the question instead is: "Given an empty crossword grid and a word list, does there exist a template allowing a feasible assignment of words for the grid?" Your intuition of how I modeled this is mostly correct, I used custom TABLE constraints for the words, that can be triggered on or off depending on the values of boolean variables. I used CP-SAT to model this, and if you're interested in the technical side of things, I've discussed it in great detail here: https://pedtsr.ca/2023/generating-crossword-grids-using-constraint-programming.html https://pedtsr.ca/2023/generating-crossword-grids-using-cons... It turns out that there are many weird complexities to take into account when the black square positions are unknown.
- mzl 3y ago
  Just saw that it looks like an upcoming release of OR-Tools might include reified tables: https://github.com/google/or-tools/commit/94f3d9b46870e7ea04518c6f52734f0ebed8fb1f https://github.com/google/or-tools/commit/94f3d9b46870e7ea04...
  - polivier 3y ago
    Yes, Laurent was nice enough to add this feature. I'm curious to see the difference in performance this will have over the workaround that I used.
- mzl 3y ago
  Thanks for the link. I think that your version of getting to a reified extensional constraint (your table method) looks like a reasonable way to do it, and probably works quite well for OR-Tools CP-SAT in particular. Another way to do it directly is to embed the control variable in the table, with a full set of all possible tuples for when the control variable is false. This, however, gives a large blow-up of the table size, especially for wide tables/long words and might be too expensive. Using compressed/smart/cartesian product tables or MDD constraints if the system supports it would solve this (OR-Tools does not, AFAIK). As for the Gecode model, my idea was that the way to model the words using separate element constraint for each letter could reasonably be extended into a model for reified words by changing the element constraints to tables over the triple <control variable, index, letter> in the above way. The benefit is that one would not trigger the combinatorial blow-up one gets for the above with a full table over the whole word since it is only a single letter. In a related case, I used reified extensional constraints specified using regular expressions in https://github.com/zayenz/cp-mod-ref-2019-patchwork https://github.com/zayenz/cp-mod-ref-2019-patchwork to optionally place polyominoes on a grid.