undefined | Better HN

0 pointsmzl2y ago0 comments

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). 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.

0 comments

polivier2y 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-cons...

It turns out that there are many weird complexities to take into account when the black square positions are unknown.

2 more replies

j / k navigate · click thread line to collapse