I wonder if anyone used some AI state search helper programs for designing puzzle games.

This wouldn't apply to games like TIM or Return of the Lost Wikings, because the number of possible game states is too large. For a game like Sokoban or Dweep however, where all the game entities have a small set of predetermined positions, and the number of performed actions is limited, it should be fairly easy (depending on the game) to write a program that solves the puzzle by expanding all the possible game states. I also believe it is possible to calculate the game difficulty using such a program (chance of solving the game by playing random moves, ratio of solvable game states to total states, etc.).

Actually, i do remember TIM having a hint system,
but that was made by the level creator, not the AI.

The closest thing i saw was the "Solve to mate" in
Chessmaster - AI that goes over a few option that
can lead you to a win.

other solvers do depend on the game - it's a function
of the possible states.

I created a game called Prism several years ago that had a random solution for each level and could solve it for the player dynamically. Prism was a game where you had to reconstruct a "shattered" image by pulling together colored pieces of glass. The rules were light-color-based, so if you dragged a red piece onto a green piece you'd make a yellow piece. Drag the yellow onto a blue and it'd make white. Anyhow I generated each puzzle by shattering the image using backwards rules, and then remembering the order in which I did it. This meant that the solution wasn't necessarily the BEST solution, but it would solve it. A backward rule, for instance, was "white can spit out a yellow and turn blue," which is the opposite of the player rule "drag yellow onto blue to create white." By playing these backward rules forward again, I'd have a solution. This kind of automatic solver relies on random levels generated by a set of rules.