Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

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 ]

Replies are listed 'Best First'.
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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://433422]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2018-06-23 03:01 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (125 votes). Check out past polls.