In 2005 a mathematics student called Mary Radcliffe developed the concept of a puzzle she called Planarity. It was implemented as a computer game on the internet by John Tantalo. The idea is to take an undirected graph, and the puzzle is to place the vertices (‘nodes’) in such a way that the graph is planar, i.e. the the edges (‘lines’) do not cross. A graph (drawn in 2D) without crossing edges is called a planar graph in mathematics, and this suggested name Planarity. It is an old problem in mathematics how to quickly determine whether a graph is planer or not.
The game became somewhat of a craze among the flash-based gaming community under the name Untangle (just google for “untangle game” and you will find dozens of implementations). Unexpectedly, the game is also available on the iPhone.
There are two implementations of Planarity in the app store (links redirect to iTunes): UntangleManiak (there is also a Lite version) and The Plateau (also available in a Lite version). UntangleManiak (shown here to the left) is part of the PuzzleManiak suite of puzzles, which all have a nice system of online scoreboards and daily internet challenges.The graphics are simple, but very functional. If you touch a vertex, it will show all connected vertices in red, which is very helpful in solving the puzzles (this trick was already used by John Tantalo’s original implementation).
The Plateau (shown here at the top of this post) has much more fancy graphics. Though very beautifully made, the graphics distract a bit from the basic puzzle. Your preference might depend on whether you are more interested in the abstract puzzle pleasure (like me), or whether you enjoy gorgeous visuals (as most probably do).
The only request I have is to make these apps multi-touch. The touch screen of the iPhone can deal with more than one touch at a time, but this innovative feature is still not really used by developers. For solving planarity it would be ideal to be able to move various vertices at once, e.g. using both thumbs. This is illustrated quite nicely in one of the concept videos of Jeff Han (from 2006) about possible usages of multi-touch screens (predating the iPhone). At about 3’00 into the clip, you will see two people playing planarity on one big screen, both using both their hands at once to move vertices around. This is how this game should be played. And technically it is possible on the iPhone, though both UntangleManiak and The Plateau do not (yet) allow this.
[Update 3 March 2009] UntangleManiak got a new layout (shown to the right), but still no multi-touch. The new look might seem fancy, but I actually find it a step back in playability. The background is greenish, and unentangled lines are also green, which makes them difficult to see in larger levels. Also, for some unknown reason the indication of connected point is gone. The original UntangleManiak showed which dots where connected to the dot you were moving (in red). This effect is gone, and I have not been able to find a setting to switch it back. Very unfortunate. The developer fell for nice looks, but forgot the practicalities of the game play. Remember next time: game play is more important than nice looks (though I now that, unfortunately, the app will probably sell more copies because of flashy looks…). [Update on update 20 March 2009] Various users complained about the removal of the indication of connected points, and the developer wisely put it back in.
[Update 17 March 2009] A new contender for the same puzzle: Uncross It. I find it too expensive to try it out, but from the description it sounds like a classic planarity implementation. However: it mentions “multi-touch” as one of the features, so this might be that I have been asking for!
[Update 30 March 2009] This one also starts to become a classic on the iPhone. Today gives us Tangled. At least the name “planarity” is mentioned in the blurb.
[Update 31 March 2009] No comment: Mesh Solver.