Crosswords Insider

You have an insider at the New York Times who sends you a list of the answers for the crossword puzzle, but his list does not say which answer goes with which clue. His list occasionally contains errors or omissions, but is usually correct. Given the list of answers and the shape of the crossword puzzle, figure out a valid assignment.

The input will consist of one or more problem sets.

Each problem set begins with a line containing two integers M and N. Zero values for these will indicate the end of the problem sets. M denotes the number of words to be placed into the puzzle and will be in the range 1 . . . 150. N denotes the number of rows in the puzzle and will be in the range 1...16.

This is followed by M lines, each containing a single word, left-justified on the line. A word will contain only alphabetic characters and words will not be duplicated within any problem set. Words will be 2 . . . 16 characters in length.

This is followed by N lines denoting a puzzle template as a series of ’.’ and ’#’ characters, left-justified and followed immediately by the end of line. Each line will contain the same number of these characters. That number may range from 1 . . . 16. A ’.’ indicates a position in the puzzle where a character may be written. A ’#’ indicates a position at which a character may not appear.

Your program should determine if all the given words can be arranged into the puzzle template in such a way as to leave no ’.’ positions unfilled and without filling any ’#’ positions. Vertical and horizontal words may intersect at a common letter, but two horizontal or two vertical words may neither intersect nor be adjacent to one another without at least one intervening ’#’.

Your program should print the string “Problem ” followed by the problem set number. If no solution is possible, it should then print, on the remainder of that output line, the string “: No layout is possible.”.

If a solution is possible, then the program should, beginning on the next line after the problem set number, print the N lines of the crossword puzzle as presented in the input but with the appropriate characters substituted for the ’.’ positions.

If multiple solutions are possible, you may print any solution.