[matsemann]

The transitions can often be sped up by not cloning and modifying state, but instead keeping track of all transitions and rollbacking. Not sure if it's doable here, since undoing a LEFT cannot know if the box was already the wall. So might need some extra bookkeeping. But for instance when solving 8-queens, sudoku or similar for huge grids, just walking back up the tree of transitions and undoing and reapplying stuff yields an immense speedup.

Edit: I see Radim mentions the same in a response to someone else.