Crosswords Insider

You have an insider at a newspaper who sends you the list of answer words for its crossword puzzle. Unfortunately the list does not tell you which word goes where, and although it is usually correct it may occasionally contain errors or omissions. Given the list of words and the shape of the crossword grid, determine whether every word can be placed into the grid so that the whole puzzle is filled, and if so output the completed grid.

The input contains one or more problem sets.

Each problem set begins with a line containing two integers $M$ and $N$. A line with $M = 0$ and $N = 0$ marks the end of the input and must not be processed. $M$ is the number of words to place and satisfies $1 \le M \le 150$. $N$ is the number of rows in the grid and satisfies $1 \le N \le 16$.

The next $M$ lines each contain one word, left-justified. Every word consists only of alphabetic characters, has length between $2$ and $16$, and no word is repeated within a problem set.

The next $N$ lines describe the grid template, left-justified, using only the characters . and #. All template lines have the same length, which is between $1$ and $16$. A . marks a cell where a letter may be written; a # marks a cell where no letter may appear.

Each word must be placed either horizontally (left to right) or vertically (top to bottom) so that it exactly fills one maximal straight run of . cells: every . cell must be covered and no # cell may be used. A horizontal word and a vertical word may cross at a shared cell, but two horizontal words (or two vertical words) may never touch or overlap without at least one # between them. Each word from the list is used exactly once.

For each problem set, first output Problem followed by the problem set number (numbered from $1$ in the order they appear).

• If no valid placement exists, append : No layout is possible. on the same line.
• Otherwise, on the following $N$ lines, output the completed grid: the template with every . replaced by the letter placed there, keeping every # unchanged. If more than one valid placement exists, output the lexicographically smallest completed grid. Compare two grids by reading all rows top to bottom and, within each row, left to right (including the # characters), and take the smaller sequence.