home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / MC20.ZIP / HANOI.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-20  |  3.7 KB  |  178 lines
  1. /*
  2.  * Towers of Hanoi
  3.  *
  4.  * This program solves the "Towers of Hanoi" problem, which is to move a stack
  5.  * of different sized rings from one of three towers to another. Only one ring
  6.  * may be moved at a time, and a ring may not be placed on top of a smaller
  7.  * ring.
  8.  *
  9.  * Original Author Unknown
  10.  */
  11. #include \mc\stdio.h            /* Standard I/O definitions */
  12. #include \mc\video.h            /* Video    I/O definitions */
  13.  
  14. #define POST            0xB3
  15. #define POST_BASE        0xC1
  16. #define BASE            0xC4
  17. #define RING            0xDC
  18.  
  19. #define SCREEN_WIDTH    80
  20. #define SCREEN_HEIGHT    25
  21.  
  22. #define RING_WIDTH        ((((SCREEN_WIDTH-2)/3)&0xFE)-1)
  23. #define LEFT_POST        (RING_WIDTH/2+1)
  24. #define CENTER_POST        (LEFT_POST+RING_WIDTH)
  25. #define RIGHT_POST        (LEFT_POST+2*RING_WIDTH)
  26.  
  27. #define MOVING_ROW        2
  28. #define BASE_ROW        15
  29. #define POST_HEIGHT        11
  30.  
  31.     char top[3] = { BASE_ROW-1, BASE_ROW-1, BASE_ROW-1 };
  32.     unsigned pause;
  33.  
  34. /*
  35.  * Main program, draw the posts & begin moving rings
  36.  */
  37. main(argc, argv)
  38.     int argc;
  39.     char *argv[];
  40. {
  41.     int nrings, i;
  42.  
  43.     if(argc < 2  ||  argc > 3)
  44.         abort("\nUse: hanoi <rings> [delay]\n");
  45.  
  46.     nrings = atoi(argv[1]);                        /* Number of rings */
  47.     pause = argc > 2 ? atoi(argv[2]) : 2500;    /* Delay count */
  48.  
  49.     vopen();
  50.  
  51.     /* Draw the posts */
  52.     for(i = MOVING_ROW+2; i < BASE_ROW; ++i) {
  53.         putxy(LEFT_POST, i, POST);
  54.         putxy(CENTER_POST, i, POST);
  55.         putxy(RIGHT_POST, i, POST); }
  56.  
  57.     /* Draw the base */
  58.     vgotoxy(0, BASE_ROW);
  59.     for(i = 1; i < SCREEN_WIDTH; ++i)
  60.         vputc(BASE);
  61.  
  62.     /* Draw the post-base connections */
  63.     putxy(LEFT_POST, BASE_ROW, POST_BASE);
  64.     putxy(CENTER_POST, BASE_ROW, POST_BASE);
  65.     putxy(RIGHT_POST, BASE_ROW, POST_BASE);
  66.  
  67.     /* Draw the title */
  68.     vgotoxy(30, BASE_ROW+2);
  69.     V_ATTR = REVERSE;
  70.     vputs(" TOWERS OF HANOI ");
  71.     V_ATTR = NORMAL;
  72.  
  73.     /* Draw the initial ring positions */
  74.     for(i = nrings; i > 0; --i)
  75.         draw(i, LEFT_POST, top[0]--, RING);
  76.  
  77.     /* Perform the movements */
  78.     hanoi(nrings, 0, 2, 1);
  79.     vgotoxy(0, 20);
  80. }
  81.  
  82. /*
  83.  * Performs towers of hanoi movements by recursing from the current
  84.  * position to the bottom of the ring stack, moving a single ring,
  85.  * and walking back up again, re-arranging the movements with each
  86.  * recursion.
  87.  */
  88. hanoi(n, a, b, c)
  89.     char n, a, b, c;
  90. {
  91.     if(n) {
  92.         hanoi(n-1, a, c, b);
  93.         movering(n, a, b);
  94.         hanoi(n-1, c, b, a); }
  95. }
  96.  
  97. /*
  98.  * Place a character on the screen at a specified X/Y address
  99.  */
  100. putxy(x, y, c)
  101.     char c;
  102.     int x,y;
  103. {
  104.     vgotoxy(x,y);
  105.     vputc(c);
  106. }
  107.  
  108. /*
  109.  * Draw a ring at a position on the screen
  110.  */
  111. draw(ring, centre, y, c)
  112.     char ring, centre, y, c;
  113. {
  114.     char i;
  115.  
  116.     vgotoxy(centre-ring, y);
  117.  
  118.     for(i=0; i<ring; ++i)
  119.         vputc(c);
  120.  
  121.     vgotoxy(centre+1, y);
  122.  
  123.     for(i=0; i<ring; ++i)
  124.         vputc(c);
  125. }
  126.  
  127. /*
  128.  * Move a ring between two posts by repeatedly drawing and erasing it
  129.  */
  130. movering(ring, from, to)
  131.     char ring, from, to;
  132. {
  133.     char fromc, toc;
  134.     char fromy, toy;
  135.  
  136.     fromc = LEFT_POST + from * RING_WIDTH;
  137.     toc = LEFT_POST + to * RING_WIDTH;
  138.     fromy = ++top[from];
  139.     toy = top[to]--;
  140.  
  141.     while(fromy != MOVING_ROW) {
  142.         draw(ring, fromc, fromy, ' ');
  143.         draw(ring, fromc, --fromy, RING);
  144.         wait(); }
  145.  
  146.     if(fromc < toc)
  147.         while(fromc != toc) {
  148.             putxy(fromc-ring, fromy, ' ');
  149.             putxy(fromc, fromy, RING);
  150.             putxy(fromc+1, fromy, ' ');
  151.             putxy(fromc+ring+1, fromy, RING);
  152.             ++fromc;
  153.             wait(); }
  154.     else if (fromc > toc)
  155.         while(fromc != toc) {
  156.             putxy(fromc+ring, fromy, ' ');
  157.             putxy(fromc, fromy, RING);
  158.             putxy(fromc-1, fromy, ' ');
  159.             putxy(fromc-ring-1, fromy, RING);
  160.             --fromc;
  161.             wait(); }
  162.  
  163.     while(fromy != toy) {
  164.         draw(ring, fromc, fromy, ' ');
  165.         draw(ring, fromc, ++fromy, RING);
  166.         wait(); }
  167. }
  168.  
  169. /*
  170.  * Wait a pre-defined delay period
  171.  */
  172. wait()
  173. {
  174.     int i;
  175.  
  176.     for(i=0; i < pause; ++i);
  177. }
  178.