Filling Crosswords is Very Hard

Laurent Gourvès, Ararat Harutyunyan, Michael Lampis +1

We revisit a classical crossword filling puzzle which already appeared in Garey\&Jonhson's book. We are given a grid with $n$ vertical and horizontal slots and a dictionary with $m…