Re: Word Search Builder

[halley]

An interesting sub-problem is to find the smallest possible grid that fits all of the given words.

A naive method would just try over and over at a given size until it hit some threshold: if a thousand attempts can't fit all ten words into the grid, then increase the grid slightly and go over it again. Maybe that's good enough.

The layout of crosswords are a similar problem, except that (1) words are either ACROSS or DOWN, (2) there must be a dead space between two words in the same row or column, and (3) extra letters or nonsense words made from the intersecting direction are not allowed; a dictionary can be consulted to see if intersecting words are actually real words. Often, the dead spaces are dictated beforehand, to arrange them attractively.

[pbeckingham]

It all seems to hinge on the random placement of the first few words. After that, it jams them in wherever it can. But those first few make all the difference.

A challenging crossword algorithm would be one that randomly places a word, then the necessary dead spaces, then replicates the dead space according to some rule of symmetry, ultimately resulting in an "attractive" layout.