For reference, here’s a code golf challenge for maze solving. It’s an “endless” challenge (meaning none of the code submissions are viewable) but the shortest sed solution is currently 98 bytes.

http://golf.shinh.org/p.rb?maze+solving

Not quite as hard as the OP, though, since the conditions are slightly easier: only 3 inputs are tested, all of them are the same size, and all of them have exactly one solution.

If I remember right, my overall approach was pruning dead-ends instead of a breadth-first search.