Solving diagramless crossword puzzles
E. Pershits, Ryan D. Stansifer · 2002
An interesting computational challenge is posed by finding the diagram in diagramless crossword puzzles. We describe two approaches to placing the words in the diagram to form a crossword puzzle, given the "across" and the "down" words. One algorithm systematically tries the possibilities. By discarding partially completed puzzles the solutions for large puzzles can be found in a reasonable amount of time. The second algorithm uses on intelligent search strategy building up the diagram word-by-word. Both methods were programmed in Modula-3, a strongly-typed, object-oriented language. We describe the programs and analyze their performance on a SPARC computer.>