This is an NP problem, which means there's no way to solve it in polynomial time. What that means in layman's terms is that as the scale of the problem you want to solve increases linearly, the computational complexity to solve it increases exponentially or even superexponentially. There's no way to "prune" bad paths, because the optimal solution could actually be on a path that appears bad at first.
As I've said before, the Trench Digging gamemode doesn't actually solve this. It attempts to, but falls short as soon as you move outside of its operational assumptions. Once you do, its optimization method actually decays rapidly as it recombines bricks in nonoptimal ways. Anyone who's played Trench Warfare will have seen this happen; trying to fill in an enemy tunnel will result in a disjointed mess of blocks almost every single time.