[MOC] Mechanical Tower of Hanoi solver

[aeh5040]

 

Here is perhaps my most ambitious creation.  It's an entirely mechanical (and pneumatic) robot that solves the Tower of Hanoi puzzle (in the minimum moves).  There is no computer or electronics, just one motor (plus two more for the compressor).  I believe it's the first time such a thing has been done, in LEGO or otherwise.

The Tower of Hanoi puzzle, invented by mathematician Edouard Lucas in 1883, is to move a pile of discs from one peg to another, using a third peg, one disc at a time, never putting a larger disc on top of a smaller disc. 5 discs (as here) takes 2x2x2x2x2-1 = 31 moves. 64 discs (in the original formulation of the puzzle) take 2^64-1 = 18,446,744,073,709,551,615 moves.

Most robots or programs to solve the puzzle use recursion, but here it is done by repeating a simple sequence of steps: grab, rotate, drop, advance the pegs. The key is that it always grabs the smaller of the two discs in front of it and transfers it to the other peg. It senses which that is by height - the grabber can only drop as far as the higher disc, which is the smaller one because of how the pegs are stepped.

The pegs are rotated by a chain drive, while all other actions are controlled by mechanically actuated pneumatic switches.

Sorry the video is a bit dark - I'll add some photos of the mechanisms soon.

[Saberwing40k]

That's amazing. I knew when I saw who posted the topic that it would be an amazing example of mechanical automation. This is an amazing mechanical robot.

[Rudivdk]

Wow, impressive! Mechanical engineering at its best!

[Carsten Svendsen]

Indeed, this is one of the better creations I have seen. I can see how it all works, except the rotation of the top part. I can't see how you get that to rotate. It looks pneumatic, but then how do you get it so precise 180° movement?

Also, I'd love to see how you made the triangle

[Jurss]

Almost fantastic, if was not real.

[Jeroen Ottens]

Wow, that is impressive. There are a lot of clever tricks in that build (rotating the pegs, using staggered pegs, the way to turn the pneumatic switches, the mechanism to lower the grabber, etc.). Did you invent them all yourself or did you have some inspiration from other mechanical solvers?

Also, have you considered using a pneumatic sequencer? I think it would not be as reliable as your solution with the rotating liftarms, but I was just wondering.

Whatever the answers, this is an amazing feat of engineering

[grum64]

My flabber is well and truly gasted!!!

[jorgeopesi]

I would like to want build those things because  I envy the fantastic time you had passed making it work. awesome work and solutions.

[Davidz90]

Fantastic build and brilliant engineering!

I'm also curious if the mechanism is inspired by some other mechanical solvers or original. Either way, fantastic 

[Didumos69]

This is truely awesome.

If I'm correct the pseudo-code of this solution reads as follows:

piles = pile[3];

// move discs from piles[0] to piles[2]

for (i = 0; i < 2^n - 1; i++)

{

    swap smallest disc between piles[i mod 3] and piles[(i + 1) mod 3];

}

A very nice way to produce the same step trace as the recursive solution would.

[BrickbyBrickTechnic]

This is awesomely well done and seems to work really smoothly hile being so complex!

[lcvisser]

Awesome, truly awesome!

I think you used the chain drive before somewhere, right? The "circular" automata? It seems to work very reliable and even quite strong, considering how small those links are and how heavy the whole turn table seems to be. Or did you reinforce it somehow?

I too am wondering how the top part rotates so reliably with respect to the pegs. Or is there some guiding mechanism that make sure the grabber fits nicely onto the pegs?

 

[MangaNOID]

I would like to ask what could be a stupid question, but can the sequence be interfered with and still have the puzzle solved? 

By that I mean, for example, could one swap one pile of discs onto another peg at some point in time when it's running and it would still end up completing it properly.

 

Edited November 11, 2018 by MangaNOID

[BusterHaus]

This is very cool, you made a physical version of the bubble sort.  I don't think I've ever seen it before. The Geneva mechanism that uses the chain is excellent, it had me wondering for half the video how it was achieved. 

By the way, this project would fit very well in the Eurobricks Robotics Forum... 

[ColletArrow]

Spectacular LEGO engineering, as you always accomplish. I love the mechanical solution to the problem, and the pnuematic implementation works beautifully.

I have a slightly random question, though; how noisy is the model when running? Could you place the compressor a little way off, and just have it hissing away to itself as it rearranges the discs?

[aeh5040]

20 hours ago, Carsten Svendsen said:

 I can see how it all works, except the rotation of the top part. I can't see how you get that to rotate. It looks pneumatic, but then how do you get it so precise 180° movement?

It is indeed pneumatic - the cylinder is attached to a gear rack which turns a gear, similar to Akiyuky's pneumatic GBC module.  There are end stops on the rotating part, to achieve the precise angle.

19 hours ago, Jeroen Ottens said:

Wow, that is impressive. There are a lot of clever tricks in that build (rotating the pegs, using staggered pegs, the way to turn the pneumatic switches, the mechanism to lower the grabber, etc.). Did you invent them all yourself or did you have some inspiration from other mechanical solvers?

Also, have you considered using a pneumatic sequencer? I think it would not be as reliable as your solution with the rotating liftarms, but I was just wondering.

It's pretty much all my own invention, although of course there is always inspiration from elsewhere.  As I mentioned above, the rotation of the grabber was partly suggested by an Akiyuky module.  Also the idea of the intermittent chain-to-knob-wheel drive (which rotates the pegs) has been used before.

The concept of a mechanical Hanoi solver (as opposed to computer controlled) is completely new so far as I know.

Pneumatic sequencer!  Yes indeed, I initially tried to do it that way (I even designed a mechanism to advance the pegs 120 degrees pneumatically), so that it would all be powered by an air supply.  Sadly I just could not get anything work reliably enough that way (I'm not quite sure why).  Maybe I'll give it another go at some point.  I'd also like to have a purely mechanical version (without pneumatics) - I'm working on that, we'll see whether it works.  But for now I'm just happy to have any working solution! :D

17 hours ago, Didumos69 said:

If I'm correct the pseudo-code of this solution reads as follows:

That's exactly right!  Of course I'm not the first to observe that this algorithm works (see the wikipedia page).  I find it somewhat miraculous that it does, and in the minimum moves!  

16 hours ago, Ludo Visser said:

I think you used the chain drive before somewhere, right? The "circular" automata? It seems to work very reliable and even quite strong, considering how small those links are and how heavy the whole turn table seems to be. Or did you reinforce it somehow?

I too am wondering how the top part rotates so reliably with respect to the pegs. Or is there some guiding mechanism that make sure the grabber fits nicely onto the pegs?

Yes, well spotted.  The chain drive is definitely a bit of a weak point. It did survive a weekend running on-and-off at BrickCon, however.

Just the end stops.  The curve at the end of the liftarms helps too.  If it is lowered not quite in the right place it can self-correct a little bit.  It does occasionally drop one (once or twice per hour).  I think inaccuracy in the chain drive is more often to blame.

13 hours ago, MangaNOID said:

I would like to ask what could be a stupid question, but can the sequence be interfered with and still have the puzzle solved? 

By that I mean, for example, could one swap one pile of discs onto another peg at some point in time when it's running and it would still end up completing it properly.

Good question.  No, it will not solve from an arbitrary state.  In general it will get into a different loop.  For a simple example, if you start with the smallest green disc in the wrong place, it will just shuffle that one round endlessly!

5 hours ago, ColletArrow said:

I have a slightly random question, though; how noisy is the model when running? Could you place the compressor a little way off, and just have it hissing away to itself as it rearranges the discs?

It is quite noisy - no reason why one could not do this.  You could also move the switches away, but it still needs drive to operate the rotation of the three pegs (which much be synchronized with the switches).

[aeh5040]

I've put some pictures on bricksafe:

http://bricksafe.com/pages/aeh/hanoi

Edited November 12, 2018 by aeh5040

[LucyCol]

Wonderful piece of engineering, the fact that it all seems to work so smoothly is a credit as well.

[Didumos69]

11 hours ago, aeh5040 said:

I find it somewhat miraculous that it does, and in the minimum moves!

I find it miraculous too. The Tower Of Hanoi is a school example of recursion, because the problem of moving N discs is easily decomposed into the problem of moving N - 1 discs and a simple case:

1. moving N - 1 discs from source peg to auxiliary peg
2. moving the Nth disc from source peg to destination peg
3. moving N - 1 discs from auxiliary peg to desitination peg

The fact that this will lead to a solution is not hard to comprehend. However, the insight that something as trivial as swapping the smallest disc between two pegs, while iterating over peg pairs in one direction (like source-axiliary, auxiliary-destination, destination-source, source-auxiliary, etc.) will solve the problem too, feels like solving the issue without the need to understand it.

It reminds me of a quest where blue and red midgets, which can't communicate with each other and don't know which color they are (they can see the color of other midgets though), need to line up with all red ones on one side and all blue ones on the other side. They can solve the problem by lining up one by one, with each one lining up right inbetween the already lined-up red ones and already lined-up blue ones, or simply at the end as long as there is only one color present. But in that case it makes perfect sense that the simple task each midget has to perform, will eventually solve the problem. Opposed to that, I can't comprehend why iteratively swapping the smallest disc between two pegs solves the Tower of Hanoi problem.

Edited November 12, 2018 by Didumos69

[AFOLegofan66]

Amazing LEGO creation...you put a lot of thinking into this.... fantastic!!!

[TeamThrifty]

This kind of project is one of my favourite things to see posted, i could watch this all day. Brilliant! 

[FernandoQ]

A great creation I have enjoyed watching the video many times and understanding all the solutions.

[shadow_elenter]

Oeh, missed this one before!
Glad I spotted it now, already learned a new trick while watching, and to me those are the best moments when browsing the forums!

Great work mate!

[wissamms]

Amazing creation, I'm trully impressed about all the thinking and effort behind all the technical solutions you have implemented. 

[skaah]

Nice bit of Beethoven in the video too!