Simon Tatham's Puzzle Collection

[JoeP]

I'm whiling away many a spare minute on this set of puzzles.

Simon Tatham's Portable Puzzle Collection

There are versions for Windows, Linux, OS X 10.3, and Palm on his site. There's a port for Symbian UIQ3 here or here, so I can play the puzzles on my phone as well (and look like I'm urgently rearranging client meetings). You can also get it, it would appear, for Nintendo and PocketPC/Windows Mobile.



Includes well-known puzzles like Sudoku and Fifteen, and some unique ... and mighty puzzling ... puzzles. No shooting, no jumping, no penguins, and no online multiplayer role-playing versions.

[Ensign Steve]

I'm finding that cube game impossible. Is there a strategy?

[ceptimus]

Originally Posted by Ensign Steve

I'm finding that cube game impossible. Is there a strategy?

I try to pick up the blue, put it back down in one of the 'unrolled cube' configurations, then pick it all up in one go. Examples of 'unrolled cubes':

 *
****
 *

 *
****
  *

*
****
   *

[JoeP]

I've tried the cube game but not very seriously. There has to be a strategy but I don't know what it is.

[Ensign Steve]

That's okay. There's enough of them that I can do to keep me entertained for hours.

[Nightson]

Untangle is ridiculously fun.

[Ensign Steve]

I haven't tried them all yet, but I keep getting sucked back into Bridges.

[JoeP]

Light Up, Galaxies and Map are occupying most of my attention at the moment.

[Ensign Steve]

I couldn't ever get a handle on Light Up. Galaxies is definitely one of my faves! Haven't tried Map yet.

[JoeP]

Untangle is great. I can solve every puzzle I've tried quickly, but I couldn't explain what I'm doing. It just seems to work out.

[ceptimus]

* ceptimus agrees with JoeP.

* ceptimus has been trying to work out an algorithm to solve untangle. This is more fun than actually untangling by hand...

[Crumb]

My girlfriend is addicted to untangle, map and network. These are very cool puzzles, thanks for posting.

[JoeP]

How's your untangle algorithm going, cep?

[ceptimus]

I'm stuck at the moment.

[ceptimus]

[ceptimus]

Originally Posted by JoeP

How's your untangle algorithm going, cep?

Aha! I came back to this algorithm when I was inspired by a graph representation diagram in the Coursera free on-line Algorithms course I'm taking. It's only been seven years since I last thought about it!

So I've written some code that models (and animates) Untangle as a physical system. The lines connecting the dots represent elastic bands trying to pull the dots closer to each other and I gave all the dots a positive charge so that they repel each other, especially when they get close, and that prevents all the dots from collapsing together into a black hole due to the elastic attractive forces.

Oh and I added some viscosity too, so the points don't just twang into position but move fairly smoothly - as though they are being dragged through treacle.

I started out with Hooke's law for the spring forces (force proportional to length) but I experimented and found it works best when the force is proportional to length cubed. I've kept the repulsion force using the standard Coulomb's law (inverse-square).

It works pretty great and smoothly at Untangling up to a few hundred points, but gets a bit slow and stuttery after that. It's very interesting to watch it working - although I am of course biased, being the proud author!

It sometimes solves the puzzle completely just using the model described above, but more often it gets stuck with just a few crossing lines around the outside edge. I found that at that stage (when the initial movements cease) the program can automatically freeze some of the outer points (that form a loop) in position and then remove all the repulsion forces - and the last few crossing points are then eliminated as the tension takes over.

[JoeP]

Originally Posted by ceptimus

So I've written some code that models (and animates) Untangle as a physical system. The lines connecting the dots represent elastic bands trying to pull the dots closer to each other and I gave all the dots a positive charge so that they repel each other, especially when they get close, and that prevents all the dots from collapsing together into a black hole due to the elastic attractive forces.

Oh and I added some viscosity too, so the points don't just twang into position but move fairly smoothly - as though they are being dragged through treacle.

I started out with Hooke's law for the spring forces (force proportional to length) but I experimented and found it works best when the force is proportional to length cubed. I've kept the repulsion force using the standard Coulomb's law (inverse-square).

It works pretty great and smoothly at Untangling up to a few hundred points, but gets a bit slow and stuttery after that. It's very interesting to watch it working - although I am of course biased, being the proud author!

It sometimes solves the puzzle completely just using the model described above, but more often it gets stuck with just a few crossing lines around the outside edge. I found that at that stage (when the initial movements cease) the program can automatically freeze some of the outer points (that form a loop) in position and then remove all the repulsion forces - and the last few crossing points are then eliminated as the tension takes over.

This post is useless without a flash animation.

[ceptimus]

Originally Posted by JoeP

This post is useless without a flash animation.

Redoing it in Flash would be a lot of work - and Flash seems to be dying out now that phones and tablets don't support it.

I'll capture the output in an animated gif and post that.

The program is written in Java. I'll look at putting that on-line once I've tidied up the code a little.

ETA:

[Ensign Steve]

There's really an algorithm? I thought it was just move the balls to the opposite side to uncross the lines.

[ceptimus]

Well that's basically it, but sometimes a simple algorithm like that seems to get stuck in a loop, and you have to radically rearrange the points to get anywhere.

Try playing the game with more points and you'll see what I mean. Go to the Type menu, choose Custom... and try, say, 50 points.

What I'd posted, by the way, was that you should select any point that had lines radiating from it that crossed other lines. Then you should move that point to each of the adjacent areas (crossing one line) and choose that area which results in the greatest reduction in line crossing count. Keep moving the same point till no further reduction is possible by moving it to any adjacent area, and then choose another point to move and repeat till the puzzle is solved.

In practice you also have to move the points around to create a bit more room to work with, but as you can do this without altering the topology of the mesh (I mean without altering the number of line crossings in any way), then it is just a practical consideration that doesn't affect the logic of the algorithm.

But there are certain pathological arrangements that can't be solved by this simple algorithm - which is why I deleted my post.

[Nightson]

It's only fun with a custom number of points, the default ones are too easy. Here's a 100 point one (and no silly algorithms for me )



Edit: Woot, 200 down

[Artemis Entreri]

Yeah, Untangle is fun with high numbers.
I did 100 in about 15minutes
Then I tried 150 and got bogged down.

Thanks for the cool puzzles!

[Ensign Steve]

Okay, I see what you guys mean. I had just been playing the default, 10 points, and it was boringly easy. I just tried it at 25 and had the aha moment. I'm trying it at 50 now. Whee!

Edit: 50 done in 10 minutes. Now trying 100. Whee!

Edit: Shit, you guys! It's too big for my screen. With 50 I had to hide the dock to get to the bottom dots, but at 100 I can't do it at all. Any suggestions from mac users?

[ceptimus]

Originally Posted by Ensign Steve

Okay, I see what you guys mean. I had just been playing the default, 10 points, and it was boringly easy. I just tried it at 25 and had the aha moment. I'm trying it at 50 now. Whee!

Edit: 50 done in 10 minutes. Now trying 100. Whee!

Edit: Shit, you guys! It's too big for my screen. With 50 I had to hide the dock to get to the bottom dots, but at 100 I can't do it at all. Any suggestions from mac users?

Now I have a mac I see what you mean I couldn't find any way to resize the window on the mac executable version without using add-on applications.

But if you use the java version that runs in your browser, then you get to see the whole thing. Be warned it takes quite a while to generate a custom 250 point untangle.

[ceptimus]

Can't you resize the mac version? With the Windows version you can resize the window in the normal way.