Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: Word Search Builder

by halley (Prior)
on Feb 22, 2005 at 17:48 UTC ( #433422=note: print w/ replies, xml ) Need Help??


in reply to Word Search Builder

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.

--
[ e d @ h a l l e y . c c ]


Comment on Re: Word Search Builder
Re^2: Word Search Builder
by pbeckingham (Parson) on Mar 08, 2005 at 16:08 UTC

    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.



    pbeckingham - typist, perishable vertebrate.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://433422]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (6)
As of 2014-11-23 13:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (132 votes), past polls