Sean Howard
My preferred data structure is a tree with the root node being "win game", and each child being a puzzle that condition is dependent on. You traverse it in reverse, clearing leaf nodes first, then nodes that depend on those lead nodes, and up the tree until you have taken many puzzles and reduced it to a single one.

The reason I prefer a tree is because it becomes trivial to procedurally generate (and also because Puzzle Tree is snazzier than Puzzle Dependency Chart - search your heart, you know this to be true). I also think trees create better graphs, allowing you to spot patterns and potential flaws more easily (the DeathSpank graph gets very confusing in that last section).

Of course, trees don't work when puzzles expand instead of contract. In practice, however, puzzles rarely expand. Much of the time, they simply unlock new "zones" of puzzles, with the entire zone being dependent. Getting to the WWII zone unlocks a bunch of new puzzles - but within the WWII zone, those puzzles should be considered leaf nodes since they have no dependencies other than being in a newly available area ( this is a beneficial way to think of it for procedural generation: ). Puzzle zones becomes an excellent way to break Puzzle Trees up, providing a visually appealing structure to the whole thing.

In the few cases where puzzles expand legitimately, it is usually bad design. You opened the locked box and inside found three random items you needed for three other puzzles that were suspiciously unsolvable until this box was unlocked. There are cases when new goals are given to the player (new puzzles, not new solutions), but that either opens a new puzzle zone or isn't actually a dependency (being told the goals is not the thing which unlocks their ability to be solved, thus it doesn't belong in the tree).