Sokoban

Before any search, a reverse pull-BFS from the goals marks every square a box could ever be brought home from; the rest are dead squares (toggle the checkbox to see them). Push a box onto one and it is provably stuck — the solver prunes those pushes outright. The solver itself is a push-optimal BFS whose state is the box set plus the player's reachable region.