I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it.
some free games: (but be warned highly addictive)
Javascript: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html
Android: https://play.google.com/store/apps/details?id=softkos.untanglemeextreme&hl=en
the rules are simple:
You are given a number of points, some of which have lines drawn between them. You can move the points about arbitrarily; your aim is to position the points so that no line crosses another.
in some versions the difficulty is enriched by making 1 to 3 points unmovable.
This simple puzzle gives rise to all kinds of topological questions:
- is there an algorhitms to solve them?
Some of the games in the android download I was unable to solve, and that makes me wonder, probably there are unsolvable untangle puzzles (so that in any situation some lines will cross)
- how can you recognize them?
- what are the minimal cases of unsolvable puzzles?
- are there fundamentaly different cases of unsolvable puzzles?
Are there any mathematical reports written about these puzzles?
see now back trying to solve one.....
There are unsolvable puzzles. Untangle gives you a graph, i.e. a set of vertices (points) with edges (lines) between some of them. You are asked to find an embedding of the graph into the two-dimensional plane such that no two edges cross each other. A graph where that is possible is called a planar graph.
Not all graphs are planar - the smallest non-planar graph is the graph containing 5 vertices, and edges between all pairs of vertices. I.e., you start out with a pentagram, and then draw lines between all pairs of corners.
There are various ways to decide whether a graph is planar - check out http://en.wikipedia.org/wiki/Planar_graph and http://en.wikipedia.org/wiki/Planarity_testing
If you read those articles carefully, you'll notice that it doesn't really say that the edges must be lines - it allows edges to be any kind of curve. That, however, doesn't really make a difference. If you find some embedding of a graph into the two-dimensional plane where the edges - if represented as arbitrary curves - don't intersect one another, you can always move the points around such that these curves become straight lines.