I'm interested in solving a certain type of puzzle game that's exemplified by Sokoban, 15-puzzles, peg solitaire, Towers of Hanoi, Rush Hour, Puzzle Dimension, Stardust, and various subgames of System's Twilight. This type of game is single-player and has deterministic rules, discrete moves, perfect information about the state of the game, and guaranteed existence of a solution (possibly several).
Can you recommend any programming libraries (particularly in Python) or existing programs to help with finding solutions to such games, even if only with brute force? To be specific, I only care about finding a solution, not enumerating all solutions. It need not even be a particularly quick solution.
These games have natural representations as classical planning problems. However, in my limited experience, planners, such as Fast Downward, have trouble with these games, probably in part because they don't allow a way to provide a user-defined heuristic function. This said, I still suspect the best general-purpose algorithm for these games is searching state space (not just the game board) with generic tree-search algorithms such as A*.
