[zzlk]

This is a nice solution. I came up with something similar where once it got stuck without making much progress I would just blow away a big radius and that would often help it get unstuck. I did eventually abandon this approach though. I can't remember the exact reason why but I think my back tracking system was not compatible with it. So if it got stuck after blowing away some tiles then it would be truly stuck and could not backtrack anymore.

[Doxin]

Mine didn't even have any backtracking at all. It'd just keep blowing stuff up until it happened to stumble on a solution. Obviously that only works if your tileset allows for many solutions, if there's only a single solution to an area it'll take a long while to stumble on it.