My Photo
Blog powered by Typepad

« always be a good boy, don't ever play with guns | Main | Puttin the 'Ray' back in 'raygun' »

March 09, 2006


Feed You can follow this conversation by subscribing to the comment feed for this post.

(Hi Clint; I was one of the people in the big discussion group at starbucks after your lecture.)

Planarity actually admits a somewhat degenerate solving strategy due to the nature of how the boards are generated. It's only somewhat degenerate because it's still a lot of work at higher levels, and I'm not sure it necessarily leads to the best human solving times.

Every vertex in a planarity puzzle has degree 2, 3, or 4 (that is, they have 2, 3, or 4 connections to other vertices), due to the way the puzzles are constructed. It turns out (also due to the construction) that every planarity puzzle admits a solution in which the vertices on the "outside" edge of the puzzle have arbitrary degree, and the vertices on the inside are all of degree 4.

Thus, the "degenerate" solution is to first determine all the vertices on the "outside". Find a 2- or 3-degree vertex, then walk along connected vertices, grabbing those that are degree 2 or 3 (although greediness will require some fixup when all of the vertices adjacent to a 3-degree vertex are on the outside).

When you reach a point where all of the unconsumed adjacent vertices are of degree-4, you'll have to probe them to see which one is nearest to a degree-3 or degree-4 node. This can get tricky simply because it's hard to see. Eventually you'll loop back to your starting 2- or 3-degree vertex, and you're done the outside. The remaining vertices can be processed in the order that they are close to the outside, since that provides a good guide for where to place them.

I don't know for sure how the puzzles are constructed, but one way to construct puzzles with this property is to draw a collection of random lines and create a vertex at the intersection of any two pairs, and the obvious edges. Any interior vertex has adjacent vertices along each line in both directions (4); vertices of degree 2 or 3 occur when there are no further intersections along one line in one or both directions.

The comments to this entry are closed.