Re: Simon Tatham's Puzzle Collection
Well that's basically it, but sometimes a simple algorithm like that seems to get stuck in a loop, and you have to radically rearrange the points to get anywhere.
Try playing the game with more points and you'll see what I mean. Go to the Type menu, choose Custom... and try, say, 50 points.
What I'd posted, by the way, was that you should select any point that had lines radiating from it that crossed other lines. Then you should move that point to each of the adjacent areas (crossing one line) and choose that area which results in the greatest reduction in line crossing count. Keep moving the same point till no further reduction is possible by moving it to any adjacent area, and then choose another point to move and repeat till the puzzle is solved.
In practice you also have to move the points around to create a bit more room to work with, but as you can do this without altering the topology of the mesh (I mean without altering the number of line crossings in any way), then it is just a practical consideration that doesn't affect the logic of the algorithm.
But there are certain pathological arrangements that can't be solved by this simple algorithm - which is why I deleted my post.
__________________
|