Untangle the dots

by Eszter Hargittai on July 12, 2005

I have accumulated quite a list of fun sites. So far I have protected CT readers by only posting these occasionally. But I have so many now that I think I am going to make it a weekly feature. As additional warning, I have created a little button to signal these posts. The point of the button is to note: you have been warned, I take no responsibility for the amount of time you end up wasting due to clicking on these links.

Planarity Flash Game

Your job is to reposition the nodes so the links do not overlap. After posting a link to this on the SOCNET mailing list yesterday, a friend of mine remarked: “LOL! That is why we have software Eszter!”. Afterward, a serious discussion about visualization software ensued. Who says games are just for wasting time?

After level 10 I decided it was time to get back to work. [UPDATE: I’ve now gone to level 13, see link to images in the comments section.] That amount of game time made me start seeing the dots and lines even when not at my computer. You have been warned.

Tuesday may not be the best time to post such links, I realize, maybe I will make it a weekend feature in the future.

{ 1 trackback }

Ars Mathematica » Blog Archive » Pure Planar Evil
07.13.05 at 1:57 am



Jeremy Osner 07.12.05 at 7:33 am

That is fun — I just did a couple of levels and then put it aside for later on but it’s way cooler than say Minesweeper.


des von bladet 07.12.05 at 7:57 am

“LOL! That is why we have software Eszter!”

That’s exactly what we said about Sudoku, which is odd since we weren’t speaking to Ezster at the time.


joejoejoe 07.12.05 at 8:29 am

Level 10? Do you have a giant brain or something?


Eszter 07.12.05 at 8:47 am

Yeah, I think it’s more fun than many other games. And more addictive, unfortunately. It’s just a flash file so if you can load that on your PDA this should be good while standing in lines. It may not be so good for your eyes though given the small screens.

That’s funny, Des. For those wondering about Sudoku, you can try it here.

Joejoejoe, you get better with practice (or you may). I just went through to level 10 again and completed it in less than 7.5 minutes. Once I get more work done perhaps I’ll try level 11 as a break between projects.


Troy 07.12.05 at 9:39 am

Madness! and fun, too. But I think I shall see the lines and dots for awhile now. :O


JR 07.12.05 at 11:05 am

This is like unraveling a tangled fishing line.


Eszter 07.12.05 at 12:52 pm

Good point, jr. Actually, Andy, to whom I should have given credit for finding this described it as follows: “for people who detangle Christmas tree lights for fun”.


Ash 07.12.05 at 3:47 pm

I can’t get anywhere near your level, and I’ve spent most of the afternoon. No fair!


george 07.12.05 at 4:28 pm

I got to level 6 before I had to leave the house, yet my score was 4 or 5 orders of magnitude from the top 10 scores.


g 07.12.05 at 4:34 pm

I hate you.

(Done levels 1-12. nough for me!)


Eszter 07.12.05 at 4:45 pm

I wouldn’t be too concerned about the high scores. They’re probably spammed with unlikely figures. I hadn’t reached 100K yet after level 10 and the top scores were in the hundreds of millions if not billions.


Dick Durata 07.12.05 at 4:56 pm

Tuesday seems right to me. Aren’t these games usually played at work?


Eszter 07.12.05 at 6:37 pm

g – I took that as a challenge. I have now completed level 13. The game gets very slow so the timing is not perfect. I did level 12 in 8:22 and got a time of 17:31 for level 13. However, by the end, there was a 15-20 sec pause between moves. This is what the screen looked like close to the start. This is what the completed screen looked like.


Jeremy Osner 07.12.05 at 7:09 pm

Question for the math whizzes — how does one prove that a particular arrangement of dots with lines connecting them is soluble or insoluble? I think there must be some layout of this game that can’t be solved, and the people who wrote the game must have ensured that such a layout would not come up; but I can’t imagine how you would do that.


Walt Pohl 07.12.05 at 7:22 pm

Jeremy Osner: Dots with lines, like in the game, are known as “graphs”. There are two “bad” graphs that are the minimal unsolvable examples. If a graph contains one of the minimal unsolvable examples, then it is unsolvable; otherwise it’s solvable. (The graph is then called “planar”.)

The minimal unsolvable graphs are known as K5 and K3,3. K5 is the graph with five dots, all of which are connected to each other. K3,3 is when you have two groups of three dots, and all of the dots in one group are connected to all of the dots in the other group.

This result is known as Kuratowski’s Theorem.


John Tantalo 07.12.05 at 9:05 pm

Hi, programmer here.

The method I designed to create the graph insures that every graph is solvable. Basically, the game generates n random lines and finds all the intersections. The segments between these intersections become edges. For n lines, there are n choose 2 vertices. The difficulty scales by incrementing this line number by one each level (initially, n is four).

One guy figured out how to crack the trivial protection I placed on my high score database, this much I’m sure of. Plenty have tried, though. The high score right now, 6378867134884 from Kagashin, may look false, but he has several seemingly-legit scores lower than that, so I’m inclined to believe that he did not use a crack.


Jeremy Osner 07.12.05 at 9:54 pm

Thanks, Walt


george 07.12.05 at 11:44 pm

This game is evil. I spent the better part of my one free day this week achieving the hollow victory of level 9. But I do have a question: how does the scoring work? It seemed like I was roughly doubling each level, but not exactly. If that’s how it works, Kashagin must have gotten into the 30s.


g 07.13.05 at 6:16 am

There are efficient algorithms for embedding planar graphs. It would be entertaining to write a program that interacts with John’s game and moves the vertices according to such an algorithm. Perhaps Kagashin did. :-)


dylan 07.13.05 at 8:51 pm

there’s an “easy/simple” algorithm to use on this game. First find any triangle (3 vertices, each of which is connected to the other 2) and fix it’s position around the border, then repeatedly position each vertex in the center of gravity of it’s neighbors. through some sort of black magic created by laszlo lovasz, you manage to find an embeding. of course this doesn’t work well with too many dots though.


Sebastian Holsclaw 07.14.05 at 12:33 am

Hmm, I didn’t find the game very hard until around level 10. I use what I thought of as an ‘insideness/outsideness’ concept. Nodes with 3 links belong on the outside, nodes with more belong inside 3 link nodes. At the high levels you have interlocking sets of 3 link nodes surrounding more link nodes. There is probably something more sophisticated to the arrangement of the more link nodes but I haven’t consciously interpreted it.

I think this is similar to dylan’s algorithm.


Shannon Clark 07.14.05 at 3:36 am

Well I’m up to level 15 with a current score score of 1605809… dangerous…

but addictive.


Thon Brocket 07.14.05 at 5:13 am

Absolutely the worst bloody time-thief I’ve ever come across. Curse you, John Tantalo.


Vaughn Cato 07.14.05 at 12:34 pm

I’ve found a provably unsolvable one for Level 3. Assuming the number in the lower left corner is the random number seed, it is 00198901. It has a K3,3 equivalent subgraph.


David 07.15.05 at 2:18 pm

Just finished Level 16…


The lag gets horrible the higher you get. I suspected it might be because it starts to scan itself for intersections at some point in the detangling process (?). I tried something this last time: I took one vertex from a section that I’d completed untangling, and dragged it over said section. And it seemed to work, too–less slowdowns during gameplay, as the scan picked up on the area I’d retangled PDQ and aborted itself.

Unfortunately, though, no solutions for the lag at the end of a level–each time it takes longer, and I have to keep telling the computer not to abort the script (whatever that means)…

Does this game have an end? Please tell me that it doesn’t go on forever, ’cause I don’t think my OCD brain could handle it.

Oh, well, back to untangling the Xmas lights…

Comments on this entry are closed.