Word Search

[Deucy]

this'll sound a little silly, but if you think about it, it's a tough one..

you know that puzzle in which you have columns and rows of letters, and you have a list of words and you're supposed to find those words within the letters and cross them off? and some words go through other words and so forth.. you know what i'm talkin' about.. (of course i'm not talkin' about cross-word puzzle. no. Word Search, that is)..

i was thinking, if we were to have a two-dimensional array (simple enough), how could we come up with an algorithm in which we give the program a bunch (a lot, actually) of words, and it will make up a Word Search puzzle in that two-dimensional array, with the ability to cross words in each other?

to put simply, how can we compu-generate a Word Puzzle?
is it possible?

again, i'm always curious.. this is no project or anything.. just curiosity..

[Deucy]

on a side-note, notice that if the puzzle that we want to generate does not feature words crossing each other, this is the simplest algorithm.. the key here is to cross words almost endlessly.. i've seen word search puzzles in which it's not only meaningless words to find, no, one had its words list as a famous speech by some president..

[Guv]

I try to take a practical approach to such problems.

First note that the program is not going to choose the words to be used. At least I do not think you intend to have the program choose the words.

Given that a human has to key the words anyway, why not give him an interface which makes it easy for him to put them directly into the character array? I would suggest a VB application with the following controls

• A set of Option Buttons for Horizontal Forward, Horizontal Backward, Vertical Down, vertical Up, and 4 for the diagonal possibilities.
• A tightly spaced array of Text Boxes, each cell to contain one character. When a character is put into a Text Box, the code sets focus to the next Text Box depending on the Option Button in effect.
• A Command Button which causes the program to fill in unused Text Boxes with random characters.
• When user clicks to change focus to a text box, he is starting a new word or re-keying a word he misspelled.
• The code should have logic to shift the word being entered if it intersects a previously entered word which has a letter in common with the word being keyed. This saves the user the trouble of counting when he wants intersecting words.
• The shifting code should have tricky logic for an intersection when there is no common letter. It should shift to avoid the intersection until a matching letter is keyed, assuming that there will be a matching letter.

A control or a menu option to print the final array, and perhaps some other cute gimmicks might be useful, but the above would be my basic approach.

[Deucy]

this is a very good approach for a program that makes an interface for a user to punch in the numbers.. but i'm looking for something that automates this task.. instead of a user finding where the words best fit, the program does it..

on a side-note.. notice that you said we'd have a button that puts a random letter in all unused boxes.. but this would cause a little problem, tho it might be a chance of 1% or less.. those random letters could make up a word that was already inserted.. which makes it possible to find two occurances of one word..

but still.. what i'm looking for is an algorithm that generates a word search automatically.. how?

[opus]

If you consider the double occurence of a word a problem, you would have that even if all spaces have been used for the words placed. They could by chance match in another place (just thake the word "the"). So you would need to check that too, and that'S lots of checking!!!

[RAEsquivelC]

I have such a program, written quite a while ago. I got it from some Internet site, but, unfortunately, I didn't save the link. The proram does have the maker's name, as follows:

WORD SEARCH, COPYRIGHT(C), BY M. J. TICHBORNE

The program is called WORDSRCH.BAS, written in BASIC, with the classical line numbers 10, 20, 30, etc. I opened it and saved it as a text file named WORDSRCH.TXT, so it can be opened and read from almost any program, text editor and word processor. However, it will run only in BASIC. It will run in QuickBASIC, but only if many modifications are made.

Since I don't know how to attach a file to this forum, I can only offer to e-mail it to the interested party that contacts me at [email protected]

[NotLKH]

Originally posted by RAEsquivelC
Since I don't know how to attach a file to this forum...

Would you like to know how?

-Lou

[RAEsquivelC]

Here is the attached QuickBASIC 4.5 file.