View Single Post
Old 11-22-2014, 05:56 PM
ceptimus's Avatar
ceptimus ceptimus is offline
Join Date: Aug 2004
Location: UK
Default Re: Simon Tatham's Puzzle Collection

I tweaked the algorithm a bit. Maybe it doesn't look as interesting now, but it gets the job done - even with large puzzles - and it's a very simple algorithm to implement manually, as described below.

  1. Find ANY "face". If you're doing it by hand then any triangle will do, but I made the program choose one of the largest faces.
  2. Put the points of the chosen face (triangle) at the outside. From now on, never move those points.
  3. Move any point towards where its connected lines would pull it if they were elastic bands.
  4. Chose a different point and repeat step 4 till no lines cross. The program just chooses all the points in turn, but if you're doing it manually, then you can choose one of the points with the longest connecting lines.

It's interesting that once the puzzle is solved any enclosed space (what I call a 'face') can be on the outside - imagine sliding the puzzle onto a sphere, and sliding it around - on a sphere you can then get any face to be the outside without ever crossing a line.

Since a triangle is always a triangle then it's easy to find one when the puzzle is in its messed up state - but if you try to find quadilateral or pentagon or whatever when the puzzle isn't solved, you're likely to chose one that isn't really a face - because it has triangles or other smaller polygons inscribed within it, It's not easy to spot that when the puzzle is messed up - but the program uses a fancy algorithm to do it.

Reply With Quote
Thanks, from:
Crumb (11-22-2014), Ensign Steve (11-22-2014), JoeP (11-23-2014), lisarea (11-22-2014)
Page generated in 0.19568 seconds with 11 queries