Towr of Hanoi move the disc

WatchTower · 07-16-2009, 12:10 AM

I already created the solver for the tower of hanoi. But I wanted to make a simple presentation of how the solver is working by showing the movement of the box as shown below. The problem I'm facing is:

How to make the program move the disk from tower-to-tower.
How the program will know which disk is the top, mid and bottom disk.
How the program will know which disk should go first to the other tower etc.....

Code:

void hanoi( int disc_num , int source, int using, int dest )
{
   if( disc_num != 0 )
   {
      hanoi( disc_num - 1 , source, dest, using );
      //printf( "Move the place from %d to %d\n", source, dest );
      disk_to_move( source, using, dest );
      hanoi( disc_num - 1 , using, source, dest );
   }
}

Code:

                 ║             ║               ║
             ╔══════╗          ║               ║
             ╚══════╝          ║               ║
            ╔════════╗         ║               ║
            ╚════════╝         ║               ║ 
         ╔══════════════╗      ║               ║
         ╚══════════════╝      ║               ║
═════════════════════════════════════════════════════════

Spidey · 07-16-2009, 12:21 AM

Quote:

How to make the program move the disk from tower-to-tower.

Do you mean you want to display the tower as ascii art and show the actual movement at every stage ?

WatchTower · 07-16-2009, 12:37 AM

Quote:

Originally Posted by Spidey

Do you mean you want to display the tower as ascii art and show the actual movement at every stage ?

Exactly, I can use the gotoxy of borland to make it move, but prior to that I must have an idea on how to resolve the problem I have stated in my first post.

Spidey · 07-16-2009, 12:55 AM

I implemented this same program once using stacks, however that was built in a graphics library.
The same concept apply's though -

Code:

void MoveTower(int n, stack start, stack finish, stack temp) {
if (n == 1) 
{
      Move a single disk from start to finish.
}
 else
   {
      Move a tower of size n - 1 from start to temp.
      Move a single disk from start to finish.
      Move a tower of size n - 1 from temp to finish.
   }
}

where move single disk would include popping from the start stack and then pushing to finish stack, and each disk would be an ascii rectangle. All you have to do after that is display the stack in order.

Another option would be using a 2D array to represent each disk and instead of simply calling printf, have a function which displays the array in order.

Adak · 07-16-2009, 01:04 AM

This is QBasic, but it shows the algorithm I used. It's ASCII (text based) art, but it's very good looking.

This is overly long, because I didn't consolidate the code - so it shows the same logic being used three times over, once for each needle (pole).

Code:

SUB Drawtowers (discnum%, playit%, move&)
'draw the towers (poles) and the discs
'discnum=number of discs in the game, playit=play move, movenum=move number
'first the tips of each pole only
VIEW PRINT
'print over any raised disks (above the poles) first
COLOR 1: LOCATE 5, 8: PRINT STRING$(21, 219);
LOCATE 5, 30: PRINT STRING$(21, 219): LOCATE 5, 52: PRINT STRING$(21, 219)

'Poles only need to be drawn at start of game
IF move& = 0 THEN
  COLOR 0 'poles are black
  'The body of each pole is displayed when
  'an empty discs is displayed. (which is everywhere a pole length is visible)
  LOCATE 7, 18: PRINT CHR$(219)
  LOCATE 7, 40: PRINT CHR$(219)
  LOCATE 7, 62: PRINT CHR$(219)
  ' now show the base holding up all three poles
  LOCATE 18, 6: PRINT STRING$(69, 223)
  COLOR 15
  LOCATE 18, 17: PRINT "ONE"; : LOCATE 18, 39: PRINT "TWO": LOCATE 18, 60: PRINT "THREE"
END IF
'
IF discnum% = 0 THEN discnum% = 10 'initial screen will show ten disks
IF move& = 0 THEN    'it's the start of a new game, initialize the second
                        'and third pole arrays to their start-up values
  j% = 6  ' j% is the number of the disc's color (how intuitive eh?)
  k% = 2 ' k% is the width of each disc
  
  IF discnum% < 10 THEN
    temp% = discnum%: j% = 15: k% = 20
    FOR i% = 9 TO 0 STEP -1
      IF discnum% > 0 THEN
        pole1(i%, 0) = j%
        pole1(i%, 1) = k%
        discnum% = discnum% - 1
      ELSE
        pole1(i%, 0) = -1
        pole1(i%, 1) = 20
      END IF ' discnum% > 0
      j% = j% - 1
      k% = k% - 2
    ' not really set up for this IF discnum% < 7 THEN k% = k% - 4 ELSE k% = k% - 2 ''new today *******
    NEXT i%
  discnum% = temp%
  END IF
  'old one works for ten disks only
 IF discnum% = 10 THEN
   FOR i% = 0 TO 9
     pole1(i%, 0) = j%
     pole1(i%, 1) = k%
     j% = j% + 1
     k% = k% + 2
   NEXT i%
  END IF 'discnum% = 10

  FOR i% = 0 TO 9
    pole2(i%, 0) = -1    'no color
    pole2(i%, 1) = 20   'maximum width value
  NEXT i%
  FOR i% = 0 TO 9
    pole3(i%, 0) = -1
    pole3(i%, 1) = 20
    'empty slots must have largest width value to allow
  NEXT i%               'complete erasing when large discs are moved.
END IF


'draw the discs - first pole1
FOR i% = 9 TO 0 STEP -1
  size% = pole1(i%, 1) / 2 - 1 'this is the width indicator printed on each disc
  LOCATE i% + 8, INT(18 - pole1(i%, 1) / 2)
  IF pole1(i%, 0) > -1 THEN  'there is a disc at this location at this pole
    j% = pole1(i%, 0)'get the color for this disc
    COLOR j%: PRINT STRING$(pole1(i%, 1) + 1, 219); 'show disc with ASCII chr$ 219
    'the +1 is for the width of the pole! (which is covered by the disk here)
    ' i% can't be used in this next line - it always shows the bottom disc
    'regardless of size as 9, next up is 8, etc. (their position in the array)
    COLOR 15, j%: LOCATE , 18: PRINT USING "#"; size%; : COLOR 15, 1
  ELSE
    'no disc on this position so color it with background color
    j% = 1
    COLOR j%: PRINT STRING$(pole1(i%, 1) / 2, 219); 'show empty disc with ASCII chr$ 219
    'in background color.+1 is the width of the pole! (which is NOT covered by the disk here)
    COLOR 0: PRINT CHR$(219); 'draw the pole
    COLOR j%: PRINT STRING$(pole1(i%, 1) / 2, 219)'the other half of the empty disc
  END IF
NEXT i%
'

'now pole2
FOR i% = 9 TO 0 STEP -1
  size% = pole2(i%, 1) / 2 - 1 'this is the width indicator printed on each disc
  LOCATE i% + 8, INT(40 - pole2(i%, 1) / 2)
  IF pole2(i%, 0) > -1 THEN  'there is a disc at this location at this pole
    j% = pole2(i%, 0)'get the color for this disc
    COLOR j%: PRINT STRING$(pole2(i%, 1) + 1, 219); 'show disc with ASCII chr$ 219
    'the +1 is for the width of the pole! (which is covered by the disk here)
    COLOR 15, j%: LOCATE , 40: PRINT USING "#"; size%; : COLOR 15, 1
  ELSE
    'no disc on this position so color it with background color
    j% = 1
    COLOR j%: PRINT STRING$(pole2(i%, 1) / 2, 219); 'show empty disc with ASCII chr$ 219
    'in background color.+1 is the width of the pole! (which is NOT covered by the disk here)
    COLOR 0: PRINT CHR$(219); 'draw the pole
    COLOR j%: PRINT STRING$(pole2(i%, 1) / 2, 219)'the other half of the empty disc
  END IF
NEXT i%
'

'and pole3 here
FOR i% = 9 TO 0 STEP -1
  size% = pole3(i%, 1) / 2 - 1 'this is the width indicator printed on each disc
  LOCATE i% + 8, INT(62 - pole3(i%, 1) / 2)
  IF pole3(i%, 0) > -1 THEN  'there is a disc at this location at this pole
    j% = pole3(i%, 0)'get the color for this disc
    COLOR j%: PRINT STRING$(pole3(i%, 1) + 1, 219); 'show disc with ASCII chr$ 219
    'the +1 is for the width of the pole! (which is covered by the disk here)
    COLOR 15, j%: LOCATE , 62: PRINT USING "#"; size%; : COLOR 15, 1
  ELSE
    'no disc on this position so color it with background color
    j% = 1
    COLOR j%: PRINT STRING$(pole3(i%, 1) / 2, 219); 'show empty disc with ASCII chr$ 219
    'in background color.+1 is the width of the pole! (which is NOT covered by the disk here)
    COLOR 0: PRINT CHR$(219); 'draw the pole
    COLOR j%: PRINT STRING$(pole3(i%, 1) / 2, 219); 'the other half of the empty disc
  END IF
NEXT i%
'
COLOR 15, 1'restore bright white foreground
VIEW PRINT 20 TO 24

END SUB

I couldn't get a screenshot to show the colors, so a couple suggestions:

1) You have all the char's you'll need for this, just look around in your ascii chart - (Ascii Table - ASCII character codes and html, octal, hex and decimal chart conversion is one source, iirc). Mine don't "float" in the air with spaces between them.

2) If the position on the needle has a disc, it's easy to just print the needle (pole), while you are printing the disc. Print left half of the disc, print the needle, then print the right half. Or you can print all the disc, and then print the needle, last (not the other way around, though

).

3) There are vibrant colors in text mode, and it looks great with them. I believe cprintf() prints colors in Turbo/Borland C text mode, in Windows.

Fun programming challenge, imo.

WatchTower · 07-16-2009, 04:56 AM

This truly challenging for me. Thank you for the algorithm, this is all I need to start coding this. I'll be posting my updated code just in case I experienced a problem. I'll be analyzing the algorithm as soon as I get home

WatchTower · 07-16-2009, 05:31 AM

Quote:

Originally Posted by Spidey

I implemented this same program once using stacks, however that was built in a graphics library.
The same concept apply's though -

Code:

void MoveTower(int n, stack start, stack finish, stack temp) {
if (n == 1) 
{
      Move a single disk from start to finish.
}
 else
   {
      Move a tower of size n - 1 from start to temp.
      Move a single disk from start to finish.
      Move a tower of size n - 1 from temp to finish.
   }
}

where move single disk would include popping from the start stack and then pushing to finish stack, and each disk would be an ascii rectangle. All you have to do after that is display the stack in order.

Another option would be using a 2D array to represent each disk and instead of simply calling printf, have a function which displays the array in order.

So with the code sample that you showed to me, the tower will also move. So to animate the towers and disk both the tower and disk should move. I thought the only thing that will move are the disks.

Spidey · 07-16-2009, 05:47 AM

Quote:

I thought the only thing that will move are the disks.

Exactly, the only thing that will move is a single disk.
MoveTower is the recursive function and can only move a single disk at a time.
Think of it this way, to move of tower of 8 from Stack A - C with B as the temp stack, you first need to move a tower of 7 from the first to the temporary stack.

For that, you will first have to -

Move the tower of size 7 from A - B
Move the single remaining disk from from A - C
Move the tower of size 7 from B - C

...and so on till 7 reaches 1

Notice that the only line which does anything is 'Move the single remaining disk from from A - C', which would be the function which moves your rectangle.

If you have trouble grasping this implementation, try using it with char's first instead of the stack. Where the each tower would represent a char say, 'A' 'B' 'C' and n is the number of disks. In this version MoveSingleDisk() would simply print out the number of the disk and the start and finish destination.

Adak · 07-16-2009, 01:27 PM

When you're moving the disc's, it's helpful if you:

1) Make each move a two step process:

>> a) Step one, is to raise the disc that's to be moved, and show it for a brief time (say 1/3rd of a second), above it's own needle.

>> b) Step two, is to move the disc from the raised position above it's needle, to it's final position around it's new needle.

If you don't slow things down with delay(#ofMilliseconds) or sleep(#ofSeconds), then the display moves so fast, you can't see what's going on.

Spidey · 07-17-2009, 03:48 AM

Well, I decided to code a quick sample of the algorithm I described.
Here is what it looks like with 3 disks.

Code:

    |===1===|           |               |
   |====2====|          |               |
  |=====3=====|         |               |
--------------------------------------------------
        |               |               |
   |====2====|          |               |
  |=====3=====|         |           |===1===|
--------------------------------------------------
        |               |               |
        |               |               |
  |=====3=====|    |====2====|      |===1===|
--------------------------------------------------
        |               |               |
        |           |===1===|           |
  |=====3=====|    |====2====|          |
--------------------------------------------------
        |               |               |
        |           |===1===|           |
        |          |====2====|    |=====3=====|
--------------------------------------------------
        |               |               |
        |               |               |
    |===1===|      |====2====|    |=====3=====|
--------------------------------------------------
        |               |               |
        |               |          |====2====|
    |===1===|           |         |=====3=====|
--------------------------------------------------
        |               |           |===1===|
        |               |          |====2====|
        |               |         |=====3=====|

07-16-2009, 12:55 AM	#4
Spidey Webhead Join Date: Jul 2009 Posts: 278	I implemented this same program once using stacks, however that was built in a graphics library. The same concept apply's though - Code: void MoveTower(int n, stack start, stack finish, stack temp) { if (n == 1) { Move a single disk from start to finish. } else { Move a tower of size n - 1 from start to temp. Move a single disk from start to finish. Move a tower of size n - 1 from temp to finish. } } where move single disk would include popping from the start stack and then pushing to finish stack, and each disk would be an ascii rectangle. All you have to do after that is display the stack in order. Another option would be using a 2D array to represent each disk and instead of simply calling printf, have a function which displays the array in order.
Spidey is offline

07-16-2009, 04:56 AM	#6
WatchTower Registered User Join Date: Jul 2009 Posts: 40	This truly challenging for me. Thank you for the algorithm, this is all I need to start coding this. I'll be posting my updated code just in case I experienced a problem. I'll be analyzing the algorithm as soon as I get home
WatchTower is offline

07-16-2009, 01:27 PM	#9
Adak Registered User Join Date: Sep 2006 Posts: 3,142	When you're moving the disc's, it's helpful if you: 1) Make each move a two step process: >> a) Step one, is to raise the disc that's to be moved, and show it for a brief time (say 1/3rd of a second), above it's own needle. >> b) Step two, is to move the disc from the raised position above it's needle, to it's final position around it's new needle. If you don't slow things down with delay(#ofMilliseconds) or sleep(#ofSeconds), then the display moves so fast, you can't see what's going on.
Adak is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Recursive function	WatchTower	C Programming	11	07-15-2009 07:42 AM
Incorporating en-passant and Castling into a chess program	mac025	C Programming	2	03-24-2006 08:36 PM
Request for comments	Prelude	A Brief History of Cprogramming.com	15	01-02-2004 10:33 AM
Formatting Output	Aakash Datt	C++ Programming	2	05-16-2003 08:20 PM
Towers of Hanoi, special output.	spoon_	C Programming	3	03-15-2003 06:08 PM