The Parameterized Complexity of Ricochet Robots

摘要

Sliding maze puzzles like Ricochet Robots and Atomix are puzzles in which solvers must maneuver agents around a grid board subject to the constraint that whenever an agent moves in some direction, it must move as far as possible in that direction. In general, finding an optimal solution to these puzzles is known to be PSPACE-complete. This paper further shows that these puzzles are W[SAT]-hard with respect to the number of robots in the puzzle instance (and therefore unlikely to be Fixed Parameter Tractable).