Wordsearch Game: Efficient word insert algorithm

This topic is 4427 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Ok heres the background. I have got a wordsearch grid represented as a multi dimensional array in the format Grid[Row][Column]. I have a list of words that i'd like to insert into the grid, in a mixed up fashion (i.e. some horizontal, some vertical and some diagonal). The current method i am using involved the following;(language isn't really important for this)
for each 'word' in 'wordlist' do
{
while(OK)
{
pick a random orientation //(hoz,vert, diagF(\) diagB(/)) pick a starting position for the insert base upon orientation and word lenght
grab whats already in that grid space
compare the two
if each letter in the
for each 'letter' in word do
{
if (grabbedword.letter != empty space)
{
if (grabbedword.letter != word.letter)
{
then OK = false;
}
}
}
}
}


If the above code executes ok then the position is logged and the word is entered into the position. The problem is that with some combination of words and random positions the gird will get stuck, because it keeps finding a position that the words won’t fit in. Currently I have implemented a timer which checks to see if it takes to long, if it does then it starts again. Basically there seems to me that there must be a more efficient way of doing this. Because as long as the number of words is not to high you can always fit the words in, even if its just putting them all horizontal or vertical. Any help on this would be good, particularly any math-like way. I hope I’ve made it clear but if not please ask what you don’t understand.

Share on other sites
The easiest solution would be to try a random orientation first; if that fails, try each possible orientation in order. This will guarantee that, if a word can be fit, it will be. Try this with random positions on the grid for, say, 4 attempts; if 4 random positionings don't get a fit, try to brute-force find a location. In order to prevent "clumping," have your brute-force search start from different corners and run in different directions each time. For instance, the first word you cram in by brute force, start in the top-left corner and move to the right then down. The second time, start in the bottom-right and move up then left. When you cycle back to the top-left corner, switch directions (go down first, then right) - and so on.

There's probably a more sophisticated way you could arrange the words to try and maximize the "interestingness" of the puzzle, but I have a feeling it'd take a bit of genetic training algorithms and some other cruft that I'm far too tired to suss out at the moment [smile]

Share on other sites
Cheers for the idea, i didn't think of that. Well if u have any ideas once u have got some rest then please let me kno! :D Its kinda annoying because it does seem like there is a bettter way.

1. 1
2. 2
3. 3
Rutin
19
4. 4
JoeJ
14
5. 5

• 14
• 9
• 23
• 9
• 32
• Forum Statistics

• Total Topics
632627
• Total Posts
3007510
• Who's Online (See full list)

There are no registered users currently online

×