I've been wondering if the book "Mazes for Programmers" might also contain some useful advice. Or maybe the algorithms can be found elsewhere, too.

It describes various strategies for proceduarly creating mazes. Perhaps many puzzles can be mapped to a maze, as the search tree for solving them would essentially be a maze?