I’ve been writing some code (in Java) to solve this fun puzzle. I’ve played the puzzle for many years – it’s part of the excellent and free Simon Tatham’s Portable Puzzle Collection which has been available on many platforms for ages and has recently been ported to Android too. Untangle was inspired by Planarity, written by John Tantalo.
My first effort modelled the puzzle as a physical system. The links between points are elastic bands, where the attractive force is proportional to the cube of their length. The points have an electric charge which produces a repulsive force between all points in line with Coulomb’s inverse square law. The whole thing is submerged in a viscous fluid so that things don’t move too fast.
It solves many puzzles just using those rules but sometimes, especially with puzzles with a large number of vertices, it gets stuck in ‘a knot’ or takes too long to stabilize. Also, if it happens to ‘choose’ an outer face with a large number of vertices, then some inner vertices can be pushed out by the repulsive force so that they cross the ‘perimeter line’.
I’m now working on a faster and guaranteed-to-work algorithm – though it may not be as interesting to watch in action. Stay tuned for an update…