View Single Post
  #17  
Old 11-29-2007, 09:19 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCCXXI
Default 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.
__________________
Reply With Quote
Thanks, from:
Ensign Steve (11-29-2007)
 
Page generated in 0.22154 seconds with 11 queries