I got the puzzle generator working well enough to generate the puzzle I needed. I’m done with this project.

It was interesting when I decided to add clumped words to the algorithm. Four words can all come together  in a four-letter clump. It’s a situation that the normal one-word-at-a-time processing can’t find because all four words depend on each other.

solution

Finished Puzzle Generator

The example in the image above has a few clumps. If I was going to work more on this program, I would try to develop some sort of algorithm to find these on the fly instead of testing for the special cases before placing things in the puzzle. It is possible to have a clump of five words coming together in a clump of six letters but it was hard to even make up an example when I wanted to make sure it was possible. I won’t be coding for it anytime soon.

Since this is done, or at leas the current algorithm is finished, I will describe how the generator works. It is not sophisticated.

  1. Create a list of items that can be placed in the puzzle.
  2. Find all combinations of clump-able words and add those clumps to the list.
  3. Shuffle the order of the item list.
  4. Take the first item and stick it in the puzzle. Placing words and clumps requires specific code for each of those types of item.
  5. Make a list of every grid square in the puzzle. Shuffle the order of that list.
  6. Step through the list and try to place each item at the give position in the grid. When placing items at this point in the algorithm, overlap is required. There is also some code to make sure that words are not placed adjacent to other words except where there is an overlap.  Placed words are removed from every item in the list that contains them and the algorithm can stop if it runs out of things to place.
  7. Count how many times an overlap is found. Clumps represent four overlaps plus whatever overlap happens when placed in the puzzle.
  8. If the puzzle has a better score than a previously generated puzzle, save it and display it then go generate a new random puzzle. Continue forever or for billions of tries.

The user can save a “best” puzzle at any time as a set of bitmaps; one with a solution and one with empty squares (except for across and down numbers).

That’s it. The clumps are special cases and the algorithm for building the puzzle tries to place them just like placing a single word. it’s not clever enough t0 handle any other clump scenario but more complicated clumps are not so likely with short words lists of ten or twenty words.

I will add a new post when I make a web version. the only trick there is that the server cannot run a PHP script for a long time and JavaScript and PHP might both be a bit slow. Neither is a very good object oriented language for this type of thing either.

1 Comment