Thread: Towr of Hanoi move the disc

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    40

    Towr of Hanoi move the disc

    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:
                     ║             ║               ║
                 ╔══════╗          ║               ║
                 ╚══════╝          ║               ║
                ╔════════╗         ║               ║
                ╚════════╝         ║               ║ 
             ╔══════════════╗      ║               ║
             ╚══════════════╝      ║               ║
    ═════════════════════════════════════════════════════════

  2. #2
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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 ?

  3. #3
    Registered User
    Join Date
    Jul 2009
    Posts
    40
    Quote Originally Posted by Spidey View Post
    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.

  4. #4
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 07-16-2009 at 01:32 AM.

  6. #6
    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

  7. #7
    Registered User
    Join Date
    Jul 2009
    Posts
    40
    Quote Originally Posted by Spidey View Post
    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.

  8. #8
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  10. #10
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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=====|

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function
    By WatchTower in forum C Programming
    Replies: 11
    Last Post: 07-15-2009, 07:42 AM
  2. Replies: 2
    Last Post: 03-24-2006, 08:36 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Formatting Output
    By Aakash Datt in forum C++ Programming
    Replies: 2
    Last Post: 05-16-2003, 08:20 PM
  5. Towers of Hanoi, special output.
    By spoon_ in forum C Programming
    Replies: 3
    Last Post: 03-15-2003, 06:08 PM