Well, folks say they got going by using AXX's solution. I must not have understood exactly what AXX ment. I did implement what I thought that solution was, and it didn't help. But I did find something else that worked very well. The way to approach this problem is geometrically. SPOILERS FOLLOW: The basic approach is to compute the distance along the shortest path to interesting nodes and cut the link on that path. For basic exit nodes you simply cut the link to the closest node where distance is the number of edges that are traversed. In fact, if SKYNET is on a node adjacent to an exit it is the only move. if SKYNET is not adjacent to an exit node then you get your choice of things to cut. I call this a free move. But what to cut? A few failures and the obvious answer is that you need to cut a link to a node that connects to two exit nodes. But which one? The answer is to cut the "closest" one. But what metric do you use for distance? I believe that AXX's solution (which didn't work for me) was to use the sum of the "rank" of all the nodes on the shortest path to the dual-exit node, where the rank is the number of exit nodes connected to the given node. After looking at the failing boards for a few minute I saw that the key wasn't the rank, but instead the number of "free moves" that were between SKYNET and the dual-exit node. So, I used BFS to find the shortest path to the dual-exit nodes and then I backtracked along the shortest path and counted the number of nodes that had NO adjacent exits (these are free moves). Then I cut the link along the path that had the fewest "Free" moves. For all the puzzles this seemed to give the correct solution and did it quickly. There are a few more things you need to do to get the "right" shortest path, and things you need to do to reduce the complexity so that it runs fast enough, but defining the distance metric as the number of free moves along the shortest path got the answer for me.