Ricochet Robots is a path finding board game where you place robots on a board and then try to find an optimal path to get those robots to different targets on the board. I play this game frequently with a group of friends and typically we can get robots to move there in a 10 moves or less, but sometimes we get truly stumped with scenarios that require 20 or more moves. We are pretty sure there’s usually a more optimal solution in these cases, but without finding it, who knows? So to answer that, I decided I’m going to write a solver, with a UI and everything. Maybe I can get one of those gaming display table things to play on instead of the physical board.
This is another relatively hard problem to solve, in fact, there’s a research paper that established that the game is NP-hard! However, the parallels between this and the Eternity II puzzle are striking. A simple solver will just walk through the different states that can be reached, but that may never resolve due to the complexity of the problem. However, I really want to be able to resolve the question in real time while my friends and I are playing, we’ll see how it goes!