Dec 23 2007

perl: Word Search Generator

Published by at 11:26 am under Programming

Logic

I started by imagining how I would create a puzzle completely by hand. Imagine a 10×10 grid, and we will conveniently number the columns and rows 0 thru 9. Assume the first word we want to place on the grid is SEARCH. Now since it is our goal to hide words on the grid, we would want to pick a random location to start the word, and pick a random direction to have the word oriented. Let’s pick the cell at column 6, row 7, and consider how we can fit the word in:

Figure 1

Figure 1 – placing our first word

From this starting location, there are 8 possible directions to place the word. It’s easiest to think of these directions like the compass points on a map; N, E, S, W, NE, SE, SW, NW. Not all directions will accommodate our word; only N, NW, and W allow the word to fit (shown in green), the other 5 directions run out of room (shown in orange). So, let’s pick the NW direction and place our word there.

Now let’s pick a second word, PUZZLE, and a random location to start (column 4, row 1), and again look for ways to fit it in. Things are getting tighter, since the first word is already on the grid.

Figure 2

Figure 2 – placing our second word

Now in this case we have 4 directions where we run out of space (orange); and 2 directions where we have to stop because our first word is forcing certain cells to contain certain letters (red). And they’re not the letters we need. But we still have 2 possible ways to fit it in, E and SE, so we can proceed.

So, let’s summarize the steps we would use hide a list of words on a grid:

  1. Pick a random word from the list.
  2. Pick a random cell on the grid.
  3. Pick a random direction to have the word oriented.
  4. See if the word will fit into the grid starting from that cell and running in that direction.
  5. If it fits, place it there. If we have more words to go, start again with step 1).
  6. If it doesn’t fit, go back to step 3) and try another direction.
  7. If we have tried all 8 directions and it still hasn’t fit, then this word will simply not work starting from this location. Go back to step 2) and try another starting location.
  8. If we have tried all possible starting locations and it still hasn’t fit, then this word simply cannot be placing into the puzzle anywhere. We have to give up on this word!

Now we pretty much have all the logic we need to create the program. Let’s move on to see how we will feed the puzzle info into the program.

Pages: 1 2 3 4 5 6 7

3 responses so far

Please do not load this page directly. Thanks!