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*.

  • I doubt that there is one library that fits all. Do you expect that a asingle person knows 8 different libraries, one for solving each particular problem? Dec 11, 2017 at 19:14
  • @ThomasWeller No, I am indeed thinking of a generic library that could be used for any game of this sort. Dec 11, 2017 at 19:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.