A popular past-time is the word search puzzle (if you don't believe me, look in your daily paper and in the news stand in the check-out line at the grocery store). In such a puzzle, a grid of letters is presented which presumably contains words. However, the words are cleverly hidden among the other letters. Their camouflage is aided by them being aligned in many different orientations: horizontal, vertical, diagonal, and sometimes even backwards! The person's goal is to find the words and circle each one. Most often the person is also given a list of the words which should be found:

 apple hananabs pear mpearoap banana npsgrape grape uleapnbm orange aenuraol agrafnel epanqust 

bananais located backwards across the top row. appledrops down from the last ain banana. pearis forwards from the first pin apple. grapeis on the line below this. orangeis on a backwards diagonal crossing grapeat the r.

You'd like to write a program to create such puzzles and let people play the game "virtually". (No, I'm not implying polymorphism...) You've got a file with plenty of words to choose from and you're fairly certain you can randomly choose words from the list and place them with other random characters in a grid.

What's that? Not sure how to place them in a grid with random characters? Well, the most obvious way to place the words in the grid is to simply choose a position and orientation at random, checking to see that any crosses occur at the same letter. If they do, place it. If not, select a new random position/orientation. Continue until you've placed the word or MAX_TRIESplacement attempts have failed (if you don't cap it, you may never end). So, given the word list (apple, pear, banana, grape, and orange), you might place things like this:

 apple ananab pear pearo banana p grape grape l a orange en g e 

bananawas chosen for a backwards, sideways orientation and there was enough room. applewas chosen for a forwards, down orientation and happened to cross bananaat an a. pearwas chosen for forwards, sideways and crossed appleat a p. orangewas chosen for a backwards, back-diagonal and didn't cross anything (at the time). Finally, grapewas chosen for forwards, sideways and crossedorangeat the r.

Then just fill in the rest of the grid with random letters (don't worry if they happen to spell other words, that's what the word list is there for -- to limit what the player is searching for). Be careful of not only single crosses, but double and higher crosses: see how applecrosses with both bananaand pearabove.

Now the only confusing part is how the user will circle the words they've found!..*eww*

Since it would be hard for the program to detect the user drawing circles on the screen, perhaps the user could merely enter the coordinates of the beginning character and indicate a direction/length/ending coordinate and the program would simply remove the word from their to find list (perhaps giving them points or something...).

But then it can be confusing for the user to ignore that word if it isn't highlighted in some way. The simplest way would be to have everything begin in lowercase and then uppercase words which have been found. ...yeah, that's probably good enough.

So, in the above grid, after the user found the word orange, the program would display:

 apple hananabs pear mpearOap banana npsgRape grape uleApnbm aeNuraol aGrafnel Epanqust 

See how the found word now stands out from the surroundings? *sigh* Squint, then!