[dietrichepp]

Nice article! I used similar techniques to find solutions for a game called “DStar”… including the choice to write the solver in Rust. You can play the game and see the optimal solutions on the web (not tested on mobile):

https://www.moria.us/games/dstar/play

A state in this game is:

  enum Active {
    Ball,
    Block,
  }

  struct State {
    coins: u32,     // bitmask of which coins remain
    active: Active, // which player is active
    ball: Point,    // location of ball
    block: Point,   // location of block
  }

I thought about writing an A* solver for this, but a simple BFS found all the solutions quickly enough. With a single-threaded solver, each level could be solved in 40s or less. The longest solutions are around 100 moves long, and the entire set of 25 levels is solved with 2.5 minutes of CPU time.