towers of hanoi. recursion, i'm sure this will be on someone'sproblem set

[Ben Bacarisse]

Actually, unless you use a slow output device it's not "IO bound".
It's about 20% IO (in terms of time) to a file on my laptop.

Not really. While it was amusing to display the results at each step,
normally it will only show the results at the beginning and the end.

I find I can't detect a difference in time without doing some serious
stats. The results flip-flop between the three- and the four-argument
versions.

 

[Geoff]

i try hanoi1 as traslation C code "G G" wrote, until 19 disk would be
ok, this is the last that print in case 19 disk

The actual puzzle has 64 disks. Any solution that doesn't take 64
disks into account would be incomplete.

There is a group of monks working the puzzle manually. It is said when
they complete the puzzle the world will end. I don't know what they
say about when a machine completes the puzzle. Perhaps you should stop
now.

 

[Keith Thompson]

The actual puzzle has 64 disks. Any solution that doesn't take 64
disks into account would be incomplete.

The *original* puzzle supposedly had 64 disks. Versions with fewer
disks are perfectly legitimate as mathematical/programming puzzles.

There is a group of monks working the puzzle manually. It is said when
they complete the puzzle the world will end. I don't know what they
say about when a machine completes the puzzle. Perhaps you should stop
now.

I wouldn't worry about it. At 1 move per second, it would take about
585 billion years to solve the 64-disk puzzle.

http://en.wikipedia.org/wiki/Towers_of_hanoi#Origins

But I don't think a typical programmed solution would have any trouble
handling 64 disks (except that the hardware would likely crumble to its
constituent atoms before it finishes).

 

[G G]

On Mon, 16 Sep 2013 09:20:56 +0200, Rosario1903 wrote:

Rosario,

it depends on your computer as to how many disks it will handle.
if you can, try a few different systems and different operating systems, too.
also, try a few computers with different amounts of RAM memory.
remember this is a recursive call program. my computer can do
23 disks. if you can monitor your memory usage while the program
runs.

When it stops note which disks are where. Using Bill's idea, see if you start at
that point and see how far it goes to completion.

doing the which disks are where will require more programming
effort along. and continuing from a given state will require more
coding and thought as well.

i hope you will post your result.

g.

 

[Seebs]

But I don't think a typical programmed solution would have any trouble
handling 64 disks (except that the hardware would likely crumble to its
constituent atoms before it finishes).

Yeah.

If you are assuming you are playing correctly, you can see how far along
you are:

Begin with the largest disk. If it is in the correct position, write
down a 1. If it is not, write down a 0. Now, for each smaller disk,
if it is on top of the previous disk, write down the number you
just wrote down, and if it is not, write down the other number.

The result is, in plain old binary, the number of your current
position (where all discs on the starting peg is 0, and all discs
on the ending peg is 2^N-1).

-s

 

[glen herrmannsfeldt]

(snip)

The *original* puzzle supposedly had 64 disks. Versions with fewer
disks are perfectly legitimate as mathematical/programming puzzles.
(snip)

I wouldn't worry about it. At 1 move per second, it would take about
585 billion years to solve the 64-disk puzzle.

I remember when I thought that a 32 bit counter counting until it
wrapped was an infinite loop. (Time greater than the maintenance
interval of the processor.) Now, it doesn't take long at all.

But yes, a 64 bit counter still takes too long.

-- glen

 

[samparker967]

What if the amount of poles are 4? How would one solve recursively?

 

[glen herrmannsfeldt]

What if the amount of poles are 4? How would one solve recursively?

I think dynamic programming would work. DP is usually good for
problems with a recursive definition, though the implementations
usually don't use recursion.

-- glen

 

[Joe Pfeiffer]

What if the amount of poles are 4? How would one solve recursively?

Unless I had some good reason, I'd only use three of them.

 

[glen herrmannsfeldt]

What if the amount of poles are 4? How would one solve recursively?

OK, for N=1 and N=2 the solution is the same as 3 poles.

For N=3, there is a new solution, shorter than for 3 poles.

Now form recursions based on the N=3 solution.

That doesn't mean that there isn't a better solution for higher N,
though.

For 3 poles, at every move you have two choices, one of which takes
you back to where you came from, and so farther from the solution.

With 4 poles, I think there are some moves which are neutral,
that is, they don't get closer or farther from the solution.

-- glen

 

[Tim Rentsch]

Unless I had some good reason, I'd only use three of them.

An exponential performance improvement isn't a good
enough reason?

 

[Tim Rentsch]

Sort of depends on your goal.

Towers of Hanoi with 3 poles has (as I remember) a unique solution
(you could create other possible answers but they are clearly
inferior having extra redundant moves).

With a 4th pole, there are now a lot of choices. You could of
course ignore the extra pole and solve it just as the 3 pole
version. You can due "better" (in less moves) than this using the
extra pole. There are lots of options for how to do this, some
probably better than others.

In words, the method to solve the Tower of Hanoi (for 3 poles) is:

To move the pile of disks from size 1 to N from A to B (C being the 3rd)
1) First move the pile of disks from size 1 to N-1 from A to C
2) Move disk of size N from A to B
3) Move the pile of disks from size 1 to N-1 from C to B

(Note that steps 1 and 3 are where the recursion happens).

With 4 piles, step 1 can become move the pile of disks from size 1
to N-1, in some combination, to piles C and D. Note that depending
on what has previously been done, there may be limits which pile a
given disk can go to. This complication doesn't happen on the 3
pole version as it can be shown that when you are moving the size N
disk from A to B, all disks of size less than N are on C (as they
must be to do the move).

With 4 (or more) poles, you have choices, and having all the smaller
disks on a given pole is not needed, and may not be optimal.

If you aren't concerned about finding the "best" solution (minimum
moves), you can do better than the 3 pole version by reducing the
strength of recursion by changing 1 to something like:

1A) Move pile of disks from size 1 to N-2 from A to C
1B) Move disk of size N-1 from A to D

and step 3 to

3A) Move disk of size N-1 from D to B
3B) Move pile of disks from size 1 to N-2 from C to B

There is a fairly simple good solution, with pseudocode

hanoi4( n, a, b, c, d ){
if n < 3 : hanoi3( n, a, b, d ), return

choose appropriate k between 0 and n-1
hanoi4( k, a, b, d, c )
hanoi3( n-1-k, a, c, b )
move 1 disk from a to d
hanoi3( n-1-k, b, a, d )
hanoi4( k, c, a, b, d )
}

hanoi3( n, a, b, c ){ ... }

The choice of k can be made easily using the following table
and picking a k to minimize the number of moves need for
hanoi4( k, ... ) plus hano3( n-k-1, ... ).

disks moves needed for hanoi4
--------------------------------
0 0
1 1
2 3
3 5
4 9
5 13
6 17
7 25
8 33
9 41
10 49
11 65
12 81
etc

(If the pattern isn't obvious, take row-by-row differences
of the number of moves needed.)

I belive this solution is optimal but I haven't proved that.
Exercise for the reader.