undefined | Better HN

0 pointspolivier2y ago0 comments

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.

0 comments

mzl2y 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 to optionally place polyominoes on a grid.

polivierOP2y ago

I'm not too familiar with MDD constraints, but there may indeed be better ways to model this. In particular, I'd be very curious to see if any improvement can be achieved using regular constraints (one for each row/column).

PS: I remember meeting you during the poster display at the CP2019 conference at UCONN. We discussed the difficulty of finding solutions for the Nmbr9 game because there were too many propagators. It's a small world!

mzl2y ago

The key point for all of MDD, smart table, compressed tables, the case constraint, and regular expression and finite automata constraints is the ability to compress don't-care information, which essentially gives one reification for a low cost.

The implementation of a regular constraint can in essence be an MDD propagator (the implementation unfolds the automata into a layered graph, which is mostly isomorphic with an MDD), however it will depend on the implementation how efficient it is. In particular, if the original finite automata is already of an MDD shape with layers, some implementations (including the one in Gecode) will create too many nodes by creating all nodes for all layers.

Fun, didn't make that connection. Yes, it is a small world.

mzl2y ago

Just saw that it looks like an upcoming release of OR-Tools might include reified tables: https://github.com/google/or-tools/commit/94f3d9b46870e7ea04...

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

j / k navigate · click thread line to collapse

0 comments

mzl2y ago

In a related case, I used reified extensional constraints specified using regular expressions in https://github.com/zayenz/cp-mod-ref-2019-patchwork to optionally place polyominoes on a grid.

polivierOP2y ago

mzl2y ago

Fun, didn't make that connection. Yes, it is a small world.

mzl2y ago

Just saw that it looks like an upcoming release of OR-Tools might include reified tables: https://github.com/google/or-tools/commit/94f3d9b46870e7ea04...

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

j / k navigate · click thread line to collapse