Generating puzzles for a Four-by-Four Word Game

While attempting to populate a word game (http://osric.com/chris/wordgame/) with puzzles, I found a way to generate the puzzles with a computer program. The program ran slowly, until I found a way to reduce the running time by a factor of 10.