Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

typodupeerror

## 108 Ways To Do The Towers of Hanoi192192

hlarwood74 writes "While it is common to program in a few different languages, somebody has written "towers of hanoi" in 108 different ways, most of them in different programming languages. It's not just the number of languages though ... there are many neat implementations and in some cases he's come up with some strange ways of solving hanoi such as this: "you ping the hanoi machine with the number of disks encoded in the type of service field, and you get response packets whose sequence numbers represent the disk moves need to solve the puzzle". I wanted to ask "why" but the title of the page (hanoimania) explains a few things :)"
This discussion has been archived. No new comments can be posted.

## 108 Ways To Do The Towers of Hanoi

• #### Next up: 108 ways to post the same story on /. (Score:5, Funny)

on Monday December 08, 2003 @07:53AM (#7658590) Journal
nt
• #### Isn't there a legend involved? (Score:5, Funny)

on Monday December 08, 2003 @07:54AM (#7658593) Journal
When someone works out every single way to solve the problem, the towers will crumble to dust and the world will vanish
• #### Re:Isn't there a legend involved? (Score:5, Informative)

on Monday December 08, 2003 @08:16AM (#7658665)
No, when somebody completes the problem with 64 disks, the world will end. It's an exponential-time function (big O of N^2), so doing that would take an insanely long time. I once calculated this out - assuming you could move 1 disk per second, it would take about 5 billion years, which is very roughly the predicted remaining lifespan of the sun.
• #### Re:Isn't there a legend involved? (Score:1)

I'm just experiencing a pretty hangover, so I could be wrong here, but N^2 is not exponential with regards to N...
• #### Re:Isn't there a legend involved? (Score:5, Informative)

on Monday December 08, 2003 @08:28AM (#7658700) Homepage
It's an exponential-time function (big O of N^2).

With 3 poles, you need (2 ^ discs)-1 moves to solve the problem. With 64 disks, and one move per second it's more like 584 billion years.

• #### Re:Isn't there a legend involved? (Score:2)

Heh. I stand corrected - when I worked it out on my calculator, it came out to 5.849424174*10^11 years.
• #### Re:Isn't there a legend involved? (Score:1, Informative)

by Anonymous Coward
Which is 584x10^9, in other words 584 billion... Learn to read standard form!
• #### Re:Isn't there a legend involved? (Score:2)

Sheesh. And if you can do 584 moves per second, then you can do it in a billion years.

What a simple problem.
• #### this isn't exponential... (Score:2)

It's an exponential-time function (big O of N^2).

Either this is quadratic time not exponential, or else I'm bigger trouble with this "Analysis of algos." exam I have tommorrow :)

O(2^N) is exponential.

• #### Re:this isn't exponential... (Score:2)

You'll pass that exam just fine. O(N^2) is polynomial, not exponential. Now for a harder problem: is O(N^(log(2)N)) polynomial or exponential?
• #### ..and the answer is.. (Score:2)

It's neither. n^log(2)n grows faster than any polynomial, but more slowly than 2^cn for any c>0.
• #### Re:Isn't there a legend involved? (Score:2, Interesting)

Besides, if I remember the legend correctly, the disks were supposed to be moved at the rate of one per year. (They're heavy, ok?)
• #### Re:Isn't there a legend involved? (Score:2, Informative)

True-ish, as that may be (64 disks with a move per second takes 585 billion years), computers can solve the puzzle much faster. A nanosecond per move is not entirely unreasonible, and a computer at that speed would have it solved in 585 years (namely, a billionth of the time ;).
• #### Re:Isn't there a legend involved? (Score:5, Insightful)

on Monday December 08, 2003 @08:54AM (#7658801)
Of course, a mathematician can solve the puzzle in 5 minutes. He proves the algorithm will solve the puzzle in the end, and leaves the actual moving of the stones as an exercise for his readers.

He then goes on to generalize the algorithm to support n-dimensional stacks.
• #### Re:Isn't there a legend involved? (Score:2)

Why do I think this should have been modded as "Funny"...
• #### Re:Isn't there a legend involved? (Score:1)

Unfortunately it isn't. I just had to perform said task for my CS173 class. I guess maybe it could be funny, because now I can go up to anybody and say "133t3r than thou" or something...
• #### Re:Isn't there a legend involved? (Score:5, Informative)

on Monday December 08, 2003 @09:21AM (#7658928)
n^2 is quadratic, not exponential ;)

When n is the number of disks:

The recurrence is T(n) = 2*T(n-1) + 1. (No, there isn't a faster way)
The function is T(n) = 2^n - 1

I can't quote the exact value of 2^64-1 offhand, but the maximum value of an unsigned 64-bit integer is definately pretty huge.
• #### Re:Isn't there a legend involved? (Score:2)

you ping the hanoi machine with the number of disks encoded in the type of service field, and you get response packets whose sequence numbers represent the disk moves need to solve the puzzle

Uhhh huh. And I'd like to see how that machine responds to a 255 in the type of service header. The response packets would Shashdot the entire universe till the end of time.

-
• #### Reverse DOS? (Score:3, Interesting)

on Monday December 08, 2003 @07:57AM (#7658600) Homepage Journal
"you ping the hanoi machine with the number of disks encoded in the type of service field, and you get response packets whose sequence numbers represent the disk moves need to solve the puzzle"

ping HanoiServer -tos=128

Send one packet, get a hundred thousand (I'm sure I lost count somewhere) in return?
• #### Re:Reverse DOS? (Score:1, Funny)

Yea Yeah Yeah, I know the TOS field isn't big enough to show 128.

It's a joke, so laugh.
• #### Whitespace? (Score:5, Interesting)

on Monday December 08, 2003 @07:57AM (#7658604)
Hmm, not all the important languages are represented in the list. I didn't see e.g. whitespace [dur.ac.uk] implementation.
• #### Re:Whitespace? (Score:5, Funny)

on Monday December 08, 2003 @08:31AM (#7658712)
Maybe they did, but you just didn't see it?
• #### Re:Whitespace? (Score:2, Funny)

I have discovered a truly marvelous demonstration of this proposition and have encoded it here in Whitespace.

• #### Re:Whitespace? (Score:1)

No LISP either :(
• #### My addition (Score:5, Funny)

on Monday December 08, 2003 @08:02AM (#7658625)
Here it is coded in Whitespace [dur.ac.uk]:

• #### Re:My addition (Score:5, Funny)

on Monday December 08, 2003 @11:28AM (#7659690)
Hmmm, looks like slashcode's added a couple of extra whitespaces in there. Won't compile.
• #### But what about... (Score:3, Funny)

on Monday December 08, 2003 @08:02AM (#7658627) Homepage
...Brainfuck [muppetlabs.com]?
• #### pfff ... Big deal ... (Score:5, Funny)

on Monday December 08, 2003 @08:09AM (#7658642)
Converting the Towers of Hanoi syntax into 108 different languages?

Visual Studio.NET includes a standard wizard for that.
• #### Reminds me of... (Score:4, Insightful)

on Monday December 08, 2003 @08:15AM (#7658659)
http://www2.latech.edu/~acm/HelloWorld.shtml

The Hello World page.

The difference? The examples on the Hello World page all have source code. Hanoimania... Not so.

But.... solving the Towers of Hanoi shows a lot more of the programming environment than Hello World does... Conditionals, branching, recursion, function calls...
• #### Re:Reminds me of... (Score:3, Informative)

You can view the source code if you click on the name of the language in the section of the page labeled: "The Implementations"

• #### Re:Reminds me of... (Score:1)

The keyword here is all.

The page clearly states that there are 4 for which there is no source code.They are:

* Hanoi OS for SPARC
* Sun Solaris /proc
* Sun Solaris STREAMS
* Sun Solaris kernel module

Curious, isn't it, that they are all related to Sun?
• #### Re:Reminds me of... (Score:2, Interesting)

The keyword here is

all.

Indeed, the keyword is all.

http://www2.latech.edu/~acm/HelloWorld.shtml

Is missing:

BLISS
Cecil
Demeter
Elf
Escher
Hope
Infer
NESL
Obliq
Proteus
SGML
Sisal
Theta
Tycoon
emacs
Lotus 1,2,3
Unisys' WFL
OWL
MFC
ZApp
Zinc

And those are just the languages listed that don't have a link at the Hello World! page http://www2.latech.edu/~acm/HelloWorld.shtml [latech.edu]

• #### Re:Reminds me of... (Score:5, Interesting)

on Monday December 08, 2003 @10:38AM (#7659360)
The first one I checked (Common Lisp,) was just wrong:

(defun dohanoi(n to from u)
(if (> n 0)
(eval
(dohanoi (- n 1) u from to)
(format t "move ~D --> ~D~&" from to)
(dohanoi (- n 1) to u from)
)
)
)

(defun hanoi(n)
(eval
(dohanoi n 3 1 2)
)
)

eval is not what we want here (it evaluates a single form in the current dynamic environment.) Also, we can use 1- and indent trailing parens correctly. For extra credit, we could make dohanoi local to hanoi.

(defun dohanoi(n to from u)
(when (> n 0)
(dohanoi (1- n) u from to)
(format t "move ~D --> ~D~&" from to)
(dohanoi (1- n) to u from)))

• #### X11? (Score:1)

So which one of these should I run if I want to view it animated in X11?

• #### Re:X11? (Score:1)

That would be the Hanoi Xlib [kernelthread.com] version.
• #### yeah... (Score:5, Funny)

on Monday December 08, 2003 @08:33AM (#7658727) Homepage
to the joy of millions of 1st year Computer Science students.
• #### Re:yeah... (Score:3, Funny)

And much to the chagrin of thousands of CS profs.
• #### Re:yeah... (Score:1)

IAAFYCSS, and that happened to be my favorite lab :-)
• #### Re:yeah... (Score:2)

But think of how convenient it will be every September when the new CS students start posting their questions to various news groups with subject lines like :

Need Help ASAP! How Do I Do This??!!

Now we can just point them to this page and ignore them istead of trying to explain how we're not here to do their homework for them. Ah, yes. The changing color of the leaves, the crisp coolness of the air, the desperate plea of the programmer newbies. Those are the first signs of autumn that I love so much.

• #### Why is the C++ version so complex... (Score:5, Interesting)

on Monday December 08, 2003 @08:42AM (#7658756)
...when the C version is so simple? He could have used the C version for both. Even if he was trying to show off the features of the
language the C++ version is still way overkill.
• #### Re:Why is the C++ version so complex... (Score:2, Informative)

Because the C++ version is non-recursive.

I'm glad he did it this way. I had heard of a previous student that programmed it non-recursively. Now I have an example to look at.
• #### Re:Why is the C++ version so complex... (Score:2)

His non-recursive C++ version is rather bogus. It works, but it is recursive, it is just taking the stack out of the hands of the compiler and managing it himself. Take a look at some of the cyclic answers in other comments here for a very nice non-recursive version.
• #### Not really non-recursive. (Score:1)

His solution isn't really non-recursive.. I actually replied to this point in another comment [slashdot.org] (that I thought was a reply to this) which includes a more honestly non-recursive solution (and a pointer to an implentation of it even).
• #### Re:Why is the C++ version so complex... (Score:1)

my question is why he made his own stack object. i could have sworn the STL has a stack object included.
• #### Re:Why is the C++ version so complex... (Score:3, Interesting)

my question is why he made his own stack object. i could have sworn the STL has a stack object included.

Er, just a guess, but maybe the original concept of his code predated the wide availability of STL. Or quite likely, as a tutorial, he just wanted to depend on nothing beyond iostreams.

I'm more concerned with some other points:

Why "#define STYPE int" instead of "typedef int stype"?

Why the #defines for EMPTY, FULL, and PUSH_OK instead of an enum?

Why the "Stack::Stack(void)" instead of just "Stack::S
• #### Re:Why is the C++ version so complex... (Score:2, Interesting)

very true. i guess it goes to another comment that someone else had about writing code in C and it being compilable in C++. while true there are different ways your suppose to write C++ code vs. C code. however it seems a large amount of people use a mix. Or maybe no one is teaching people to program in C++ but in C with C++ constructs.
• #### Re:Why is the C++ version so complex... (Score:1)

that's what my teachers at my school did, they didn't realize that they were teaching c++ stuff in my c class :/
• #### Re:Why is the C++ version so complex... (Score:2)

Why the #defines for EMPTY, FULL, and PUSH_OK instead of an enum?

Probably because CAPACITY is too, and CAPACITY is a macro because this was probably written before static const ints could be used as array size initialisers.

Presumably this also explains why he didn't use exceptions instead of EMPTY/FULL/PUSH_OK. There's no excuse for the variables starting with underscores, though.

OK, here's my version [bromage.org].

• #### Haskell? (Score:4, Insightful)

<mattr@@@telebody...com> on Monday December 08, 2003 @08:43AM (#7658761) Homepage Journal
Is it just me or does the Haskell one seem to have inverted parameters wrt the vanilla Perl one? Not that I know Haskell.. I was hoping to see some lexical wierdness in Perl and some lambdas and arrows all hanging out for the Haskell one. And wha-hey no smalltalk? well the world goes on..

Neat idea, I like to see how things are done in other languages. It would be an interesting and intuitive way to show people what other languages are like, a list of programs the same in each language, plus commentary about the highlights of the language that are used.
• #### Re:Haskell? (Score:2)

The Perl one's really weird

(\$#ARGV == 0) or die "usage: \$0 N\n";

Wow, that's really confusing. It's trying to say unless we've got arguments, we need to die with an error message. Which can be witten as

unless (@ARGV)
{ die "usage: \$0 N\n"; }

That's not the only other thing that's odd too. Using local instead of my is odd - though both will work. my will do proper lexical variables, whereas local is using main variables in the stash and creating temp copies each itteration of the subroutine.

Oh, and w

• #### Re:Haskell? (Score:2)

whoops, the \$from and \$to should be \$from_peg and \$to_peg, obviously.

d'oh.

Yes, if I'd run that perl would have complained at me because use strict was on.

• #### Re:Haskell? (Score:4, Informative)

by Anonymous Coward on Monday December 08, 2003 @10:25AM (#7659265)
"(condition) or die" is perfectly good, non-confusing Perl. It's the way you're told to do it in the Camel book, for God's sake.
• #### Re:Haskell? (Score:2)

There's more than one way to it.

;-)

• #### Re:Haskell? Obligatory Simpsons Quote (Score:1)

Homer(Max): There's three ways to do things; the right way, the wrong way, and the Max Power way!

Bart: Isn't that the wrong way?

Homer(Max): Yeah, but faster!

• #### Missed a language (Score:2)

You can program anything in RLL. Not that you'd want to--but your Client probably wants you to.

• #### Re:Missed a language (Score:1)

You can program anything in RLL. Not that you'd want to--but your Client probably wants you to.

Amen to that... How I loathe PLCs... ugh.

• #### Multi-user 3D (Score:1)

I once did a 3D-visualized Prolog implementation [it.kth.se] of the towers of Hanoi for a course assignment. It used the VR system DIVE for visualization, the Hanoi implementation was a simple proof of concept of the rudimentary Prolog interface to DIVE that was the actual assignment... Sweet memories :)

(Un?)fortunately, the code is not publicly available.
• #### What is the most disks you have solved for? (Score:2, Interesting)

I've solved the towers of hanoi with 8 disks.. Curious if anyone has solved a more insane number without computer assistance.

Though it seems pretty pointless and boring to solve for a high number of disks as the learning curve drops sharply after you figure out how to solve for the basic three disks.
• #### Re:What is the most disks you have solved for? (Score:1)

As a younger child, a teacher would give this problem to "gifted" students who were bothering her. We couldn't ask another question until we solved it, with 10 disks.
• #### Re:What is the most disks you have solved for? (Score:3, Funny)

Eight here too. In fact when I first heard of the problem (when I was 10 I think), it specified 8 disks. Never occurred to me to solve for a smaller problem first. It took me some 14 months to find a solution for the 8-disk problem by myself. Man, those were the days! I used playing cards instead of disks, and everybody around me thought I was playing some weird form of Solitaire. Sigh.
Yes, I'm still single. Why do you ask?
• #### Re:What is the most disks you have solved for? (Score:3, Funny)

10 here. i wrote a computer program to draw a sexy 3d version of it and let me move pieces by tapping the 1, 2 and 3 keys. after solving 4 or 5 discs a few times my fingers would get into this wierd zone where they'd just fly over those three keys without any conscious thought. very cool.

justin
• #### not that you need recursion for this... (Score:2, Interesting)

max = 1 no_of_discs;
for (x = 1; x max; x++)
printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);

• #### Re:not that you need recursion for this... (Score:1)

/* oops, forgot to format as code.
it should've looked like:
*/

max = 1 << no_of_discs;
for (x = 1; x < max; x++)
printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);

• #### yet another missing language (Score:2)

where is the quakec implementation? This would make quite the interesting demonstration.
• #### And the 109th way... with a guitar (Score:2)

http://www.towersofhanoi.org
• #### Re: your sig (Score:1, Offtopic)

A musician without the RIAA, is like a fish without a bicycle.

Try this...A musician without the RIAA is like a fish without a hook.

The RIAA is actually harmful. The original quote suggested simply that women didn't need men. (Also that women were slimy scaly smelly creatures and men were carefully engineered tools of great craftsmanship, but I digress...)
• #### My favourite (Score:5, Interesting)

on Monday December 08, 2003 @11:01AM (#7659486)
A quick scan of the listing didn't show my favourite one -- a non-recursive implementation.
#include <stdio.h>

#define NO_OF_DISKS 4

void main()
{
int max, x;

max = 1 << NO_OF_DISKS;
for (x = 1; x < max; x++) {
printf("Move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
}
}
• #### Re:My favourite (Score:1)

This algorithm has a slightly different result from the recursive algorithm.

For an even number of disks it your code moves the disks from stack 0 to 1, and for an odd number of disks from stack 0 to 2.

(The recursive algorithm in the 102 examples moves the disks from stack 0 to 2 always).
• #### Towers of hanoi and bit flip correlation (Score:5, Interesting)

on Monday December 08, 2003 @11:43AM (#7659770)
One neat thing I discovered about the towers of hanoi is that the sequence of disks to move for a solution

1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5...
is the exact same sequence that you get when you look at the number of bits flipped between consecutive binary numbers (i.e.
00000->00001 (1 flip),
00001->00010 (2 flips),
00010->00011 (1 flip),
00011->00100 (3 flips),
00100->00101 (1 flip),
00101->00110 (2 flips)
etc... (1,2,1,3,1,2,...)

The reason it works is because just like the towers of hanoi algorithm, when the general solution to move n disks is:
Recursively solve the puzzle for n-1 disks
Take the nth disk and move it to the goal
Recursively solve the puzzle for n-1 disks.

The bit flipping goes like this:
While the nth bit is 0, the solution works for the n-1 disk solution
When we go from 011111 (n-1 1's) to 10000000 (n-1 0's) we flip n bits
Then the nth bit stays 1 and we repeat the solution for the n-1 disks.

• #### Re:Towers of hanoi and bit flip correlation (Score:2)

The Chinese rings puzzle is also based on the binary numbers. I have a puzzle called "The Brain" with rods that slide in and out. These are all really the same puzzle and have the same solution:

Alternate moving the smallest ring and doing the only other move left.

The only problem is that you need to go in the correct direction at the beginning, otherwise you're moving an odd number instead of even or vice-versa. I got to where I could solve the Brain (8 sliders) in a few seconds with my eyes closed.

• #### Representative? (Score:2)

Now here's a question:

Do you think that this problem is representative of the language? e.g. Perl is more efficient than PHP. Or is this going about it all wrong because of the specialisation of programming? Perhaps a series of tests consisting of different types of problems would be possible?

• #### XML/XSL (Score:5, Interesting)

on Monday December 08, 2003 @11:51AM (#7659827) Homepage Journal
As an XSL guy, I felt left out. So, given this xml:
<?xml version="1.0"?>
<hanoi>
<arg n="3"/>
</hanoi>

you can transform with this:
<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:template match="/">
<xsl:variable name="n">
<xsl:value-of select="//arg/@n"/>
</xsl:variable>
<xsl:element name="hanoi-solve">
<xsl:call-template name="dohanoi">
<xsl:with-param name="n" select="number(\$n)"/>
<xsl:with-param name="to" select="3"/>
<xsl:with-param name="from" select="1"/>
<xsl:with-param name="using" select="2"/>
</xsl:call-template>
</xsl:element>
</xsl:template>
<xsl:template name="dohanoi">
<xsl:param name="n"/>
<xsl:param name="to"/>
<xsl:param name="from"/>
<xsl:param name="using"/>
<xsl:if test="number(\$n) &gt; 0">
<xsl:call-template name="dohanoi">
<xsl:with-param name="n" select="number(\$n) - 1"/>
<xsl:with-param name="to" select="\$using"/>
<xsl:with-param name="from" select="\$from"/>
<xsl:with-param name="using" select="\$to"/>
</xsl:call-template>
<xsl:element name="move">
<xsl:attribute name="from">
<xsl:value-of select="\$from"/>
</xsl:attribute>
<xsl:attribute name="to">
<xsl:value-of select="\$to"/>
</xsl:attribute>
</xsl:element>
<xsl:call-template name="dohanoi">
<xsl:with-param name="n" select="number(\$n) - 1"/>
<xsl:with-param name="to" select="\$to"/>
<xsl:with-param name="from" select="\$using"/>
<xsl:with-param name="using" select="\$from"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
</xsl:stylesheet>
• #### Do It in Hardware (Score:3, Interesting)

on Monday December 08, 2003 @11:53AM (#7659842) Homepage Journal

I remember decades ago coming across the towers of Hanoi built with wooden dowels and hardwood disks with holes in them. This was late one evening when everyone else had retired.

After playing around with it for a few minutes, my mind just naturally got into the algorithm. The disks were flying around with hardly any conscious thought required on my part.

Just one of those cool game zombie states...

Probably because I'm prone to addictive behaviors I tend to avoid getting involved too closely with games; but I still remember the great buzz of doing Towers of Hanoi the first time.

[There's another hardware puzzle, like a Chinese lock with multiple loops, that's similarly fun for the recursively minded.]

• #### the Common Lisp version doesn't work (Score:3, Informative)

on Monday December 08, 2003 @12:43PM (#7660218) Journal

The person that wrote it sure did not have a firm grasp of Lisp. The use of eval was completely bogus. In any case, eval takes one argument, not three.

This [known.net] is a better one that actually works. I would have posted it here in the comment, but you can't format code in slashdot.

• #### Very easy non-recursive solution (Score:5, Insightful)

on Monday December 08, 2003 @12:43PM (#7660222)
This solution I always liked best:

Imagine the disk are in a cricle. Repeat:

1. move the smallest disk one step clockwise
2. do the only legal move not involving the smallest disk
Much easier to remember and perform by hand than the various iterative C programs posted. The proof that it works is left as an exercise to the reader...
• #### More interesting (Score:1)

The guy's Resume says that he works on Linux on the Desktop at IBM's research lab.

Interesting to see IBM working with Linux on the Desktop at all.
• #### Combsort in a few languages (Score:1, Interesting)

Gravatite [slashdot.org] and I like to code Combsort when we're learning a new language. Combsort a very simple modification to bubblesort that makes it competative with Quicksort but without quite as much complexity -- it's good for those rare occasions where you have to hand-code a sort and don't need all the fuss of quicksort.

I've done combsort in about a dozen dozen languages [yagni.com], and Gravatite has done it in a few more languages, including postscript [nickstoys.com].

• #### He ain't using a tower though... (Score:2)

His page also contains the best review of a PowerBook 17" [kernelthread.com] that I've ever read.
• #### I'm surprised no one has suggested... (Score:2, Funny)

Malbolge. Who ever said programming was supposed to be easy or fun?

Malbolge, Programming From Hell [mines.edu]

• #### That C++ version sucks. (Score:4, Interesting)

on Monday December 08, 2003 @01:44PM (#7660702)
That's the worst C++ feature-masturbation I've ever seen.

Here's a version using C++ template metaprogramming I just whipped up:

#include <iostream>

template <int N, int From, int To, int Using>
class HanoiSolver
{
public:
static void solve()
{
HanoiSolver<N-1, From, Using, To>::solve();
std::cout << "Move " << From << " to " << To << std::endl;
HanoiSolver<N-1, Using, To, From>::solve();
}
};

template <int From, int To, int Using>
class HanoiSolver<0, From, To, Using>
{
public:
static void solve()
{
}
};

int main()
{
HanoiSolver<10, 1, 2, 3>::solve();
}
• #### When I read the title.. (Score:1, Funny)

by Anonymous Coward
I thought of 108 Ways To Do The Girls of Hanoi.

Much more, uh, arousing.
• #### Black & White (Score:1)

at one moment of the game, you have to resolve this kind of problem in Black & White [bwgame.com].
• #### Not really non-recursive (Score:3, Interesting)

<stephen_samuel&bcgreen,com> on Monday December 08, 2003 @02:21PM (#7661001) Homepage Journal
His "non-recursive" solutions aren't really non-recursive. They simply store the state (what's being moved where) onto the stack, and then pulls and pops the state. It's just a simple enough 'machine' that you only have 4 variables (from, to, using, depth). All you've really done is taken the stackwork away frm th compiler.

Back in the late '70s, me and some friends came up with a solution that is more honestly non-recursive:

Move the smallest disk to the right (cyclically). If the other two stacks are empty, you're done, else move the smallest top disk of the two stacks to the other stack (the only move you can make if you're not moving disk 1 again).

(note: The above solution only works for an even number of disks... For an odd number of disks, disk 1 moves to the LEFT.)

Oh, sigh... The perl implementation of this is on my website [bcgreen.com].

Yes, the solution is provably correct, but I don't have the time to write it up right now... Just consider the fact that you can never move disk1 twice in a row, (or you're wasting a move), and if you're not moving disk1, there's only one move, then you have to move disk1 again (or you're wasting a move). All you have to do then is prove that disk1 always moves in the same direction.

• #### Towers of Hanoi in KOTOR (Score:2)

Ok, I know its slightly offtopic...

Its true, the towers of Hanoi puzzle is actually present in the Star Wars: Knights of the Old Republic game. Its the 4 disk version.

Always fun to see classic puzzles show up in computer games under a different guise.
• #### Good god! (Score:2)

108 versions??

Not to sound trollish but, this guy has way too much time on his hands and needs to get a life, or find something interesting to program.

Maybe its just me but I get nightmares from Tower of Hanio programs.

Its what made me decided that Biology and not CS is where I belonged.

Shudder.

• #### One more port he missed... (Score:1)

Laszlo LZX wasn't on the list so I fixed that...
Here [mylaszlo.com] is an LZX version :)

Laszlo Systems INC [laszlosystems.com]

You'll have to be patient for the XAML (Longhorn) or Macromedia Flex versions since they're a ways off ;)
• #### The Brainfuck implementation was left off the list (Score:2)

See the Brainfuck solution here [sange.fi].

It begins like (lameness filter prevents a longer excerpt, just click the link):

The first stack frame (0 0 0 0 0 0 0 0)
is used to abort the recursion
>>>>>>>>

These are the parameters for the program
(1 4 1 0 'a 'b 'c 3)
+>++++>+>>
>>>>++++++++[-]+>+>-]++>+++>+++>

And so on.
• #### cpp (Score:3, Interesting)

on Monday December 08, 2003 @04:24PM (#7661992)

The best one still have to be the version implemented in the C preprocesser.

• #### Well, you know waht they say... (Score:4, Funny)

<david@dgould.org> on Monday December 08, 2003 @06:22PM (#7663109) Homepage

I wanted to ask "why"

Never ask a geek "why". Just nod slowly as you back away.
• #### A Useful Tool in Religious Disputation (Score:3, Interesting)

<aebrain@webone.com.au> on Monday December 08, 2003 @08:31PM (#7664347) Homepage Journal

Everyone agrees that arguments about Languages are Religious, right?

Well, maybe not. Just have a look at these samplings of code. Now you can argue that some implementations are un-neccessarily complex, and others inefficient. Fair enough. But apart from such deliberately obfuscated grotesques such as the sed implementation, you can get a "within an order of magnitude" estimate of how simple/powerful/readable a language is by looking at the sources.

For example, contrast the PERL [kernelthread.com] implementation with the C [kernelthread.com] implementation.
Now look at the Java [kernelthread.com] vs the Ada [kernelthread.com] implementations.
The similarities, and differences, are instructional.

Parenthetically, with the forthcoming release of Java 1.5, which has Ada facilities such as strong typing of enumerations and generics, the architectural similarities between Ada and Java will become even more pronounced. IMHO Java has a far neater notation of Object-Oriented features than Ada-95's, but in all other respects suffers from C's over-terse syntax. But that's just my opinion. Look at the examples and form your own.
What is not a matter of opinion is that readability helps improve code quality. And wonder why "everyone knows" Ada is over-complicated, too difficult to implement, and too costly - especially when open-source free compilers have been around for nearly a decade now.

• #### towers implemented as a Slashdot thread (Score:2, Funny)

by Anonymous Coward
``=I=`` I I
`==I==` I I
===I=== I I