home *** CD-ROM | disk | FTP | other *** search
/ 17 Bit Software 3: The Continuation / 17-Bit_The_Continuation_Disc.iso / amigan / amigan 21 / recursion / tour_c / ktour.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-01-27  |  6.8 KB  |  264 lines
  1. /*      ktour.c
  2.  *
  3.  *      Finds a knight tour of a chess board by exhaustive search.
  4.  *      Displays progress of the search graphically.
  5.  *
  6.  *      usage:  run ktour [n]
  7.  *              The option N specifies the chess board size.
  8.  *              The default and maximum value for N is 8.
  9.  *
  10.  *      author:
  11.  *              Douglas A. Jones
  12.  *              181-1000 Oaks Drive
  13.  *              Atlantic Highlands, NJ 07716
  14.  *
  15.  *      This program may be freely redistributed.
  16.  *
  17.  *      Compiled with MANX 3.6, haven't tried Lattice or earlier
  18.  *      versions of MANX.
  19.  */
  20.  
  21. #include <exec/types.h>
  22. #include <exec/nodes.h>
  23. #include <exec/tasks.h>
  24. #include <exec/memory.h>
  25. #include <intuition/intuition.h>
  26. #include <stdio.h>
  27. #include <functions.h>
  28.  
  29. struct NewWindow Newwind = {
  30.         0,0, 0,0,       /* size to be filled in later */
  31.         -1,-1, CLOSEWINDOW,
  32.         WINDOWCLOSE|WINDOWDEPTH|WINDOWDRAG|SMART_REFRESH,
  33.         NULL,NULL,
  34.         (UBYTE *)"Knight tour",
  35.         NULL,NULL, 0,0,0,0, WBENCHSCREEN
  36. };
  37. struct Window *Wind = NULL;
  38. struct RastPort *Rp;
  39. struct GfxBase *GfxBase;
  40. struct IntuitionBase *IntuitionBase;
  41.  
  42. /*
  43.  *      Constants for drawing chess board
  44.  */
  45. #define SQSZX   31
  46. #define SQSZY   15
  47. #define X0      5
  48. #define Y0      11
  49. #define TXX0    8
  50. #define TXY0    10
  51.  
  52. #define MXBOARDSZ       8               /* maximum board size */
  53. char Occupied[MXBOARDSZ][MXBOARDSZ];    /* position occupied flag */
  54. int Boardsz = MXBOARDSZ;                /* size of chess board */
  55.  
  56. /*
  57.  *      Initializes the board and then tries all starting positions
  58.  *      that are not reflections.
  59.  *      Reduces the task priority so that more important things
  60.  *      will run faster.
  61.  */
  62. main(argc,argv)
  63. int argc;
  64. char **argv;
  65. {
  66.         int i,j;
  67.  
  68.         if (argc > 1)
  69.                 Boardsz= atoi(argv[1]);
  70.         if (Boardsz<1 || Boardsz>MXBOARDSZ)
  71.                 Boardsz= MXBOARDSZ;
  72.         openwindow(Boardsz*SQSZX+X0+5,Boardsz*SQSZY+Y0+2);
  73.         nice();
  74.         for (i=0; i<Boardsz; i++) {
  75.                 for (j=0; j<Boardsz; j++) {
  76.                         Occupied[i][j]= 0;
  77.                         draw(i,j,0);
  78.                 }
  79.         }
  80.         for (i=0; i<(Boardsz+1)/2; i++)
  81.                 for (j=i; j<(Boardsz+1)/2; j++)
  82.                         tour(i,j,1);
  83.         waitclose();
  84. }
  85.  
  86. /*
  87.  *      Tries to move to position x,y.
  88.  *      If the move is legal, all subsequent moves are tried by
  89.  *      recursive call.
  90.  *      Stops and waits for the close-window gadget to be clicked
  91.  *      when a feasible solution is found.
  92.  *      Nmove is the move number.
  93.  */
  94. tour(x,y,nmove)
  95. int x,y,nmove;
  96. {
  97.  
  98.         if (x<0 || y<0 || x>=Boardsz || y>=Boardsz)
  99.                 return;         /* off the board */
  100.         if (Occupied[x][y])
  101.                 return;         /* position occupied */
  102.         Occupied[x][y]= 1;
  103.         draw(x,y,nmove);
  104.         if (nmove >= Boardsz*Boardsz)
  105.                 waitclose();    /* found solution */
  106.         chkclose();             /* give up ? */
  107.         tour(x-1,y-2,nmove+1);
  108.         tour(x-2,y-1,nmove+1);
  109.         tour(x-2,y+1,nmove+1);
  110.         tour(x-1,y+2,nmove+1);
  111.         tour(x+1,y+2,nmove+1);
  112.         tour(x+2,y+1,nmove+1);
  113.         tour(x+2,y-1,nmove+1);
  114.         tour(x+1,y-2,nmove+1);
  115.         Occupied[x][y]= 0;
  116.         draw(x,y,0);
  117. }
  118.  
  119. /*
  120.  *      Opens a window in which to draw the chess board.
  121.  *      Also opens the intuition and graphics libraries.
  122.  */
  123. openwindow(x,y)
  124. int x,y;
  125. {
  126.  
  127.         IntuitionBase= (struct IntuitionBase *)
  128.          OpenLibrary("intuition.library",0L);
  129.         if (IntuitionBase != NULL) {
  130.                 GfxBase= (struct GfxBase *)
  131.                   OpenLibrary("graphics.library",0L);
  132.                 if (GfxBase != NULL) {
  133.                         Newwind.Width= x;
  134.                         Newwind.Height= y;
  135.                         Wind= OpenWindow(&Newwind);
  136.                         if (Wind != NULL) {
  137.                                 Rp= Wind->RPort;
  138.                                 return;
  139.                         }
  140.                         fprintf(stderr,"can't open window\n");
  141.                         CloseLibrary(GfxBase);
  142.                 }
  143.                 fprintf(stderr,"can't open graphics.library\n");
  144.                 CloseLibrary(IntuitionBase);
  145.         }
  146.         fprintf(stderr,"can't open intuition.library\n");
  147.         exit(1);
  148. }
  149.  
  150. /*
  151.  *      Closes the window and libraries.
  152.  */
  153. closewindow()
  154. {
  155.  
  156.         CloseWindow(Wind);
  157.         CloseLibrary(GfxBase);
  158.         CloseLibrary(IntuitionBase);
  159. }
  160.  
  161. /*
  162.  *      Waits for the user to click the close-window gadget,
  163.  *      then closes the window and exits.
  164.  */
  165. waitclose()
  166. {
  167.  
  168.         for (;;) {
  169.                 Wait(1L << Wind->UserPort->mp_SigBit);
  170.                 chkclose();
  171.         }
  172. }
  173.  
  174. /*
  175.  *      Checks to see if the close-window gadget has been clicked.
  176.  *      If so, closes the window and exits.
  177.  */
  178. chkclose()
  179. {
  180.         struct IntuiMessage *msg;
  181.         long class;
  182.         int done;
  183.  
  184.         done= 0;
  185.         while (msg= (struct IntuiMessage *) GetMsg(Wind->UserPort)) {
  186.                 class= msg->Class;
  187.                 ReplyMsg(msg);
  188.                 switch (class) {
  189.                  case CLOSEWINDOW:
  190.                         done= 1;
  191.                         break;
  192.                  default:
  193.                         break;
  194.                 }
  195.         }
  196.         if (done) {
  197.                 closewindow();
  198.                 exit(1);
  199.         }
  200. }
  201.  
  202. /*
  203.  *      Draws square x,y of the chess board.
  204.  *      If n is <= 0, the background color of the square is drawn.
  205.  *      Otherwise, only the number n is drawn (presumably the
  206.  *      background was already drawn).
  207.  */
  208. draw(x,y,n)
  209. int x,y,n;
  210. {
  211.         long wx,wy,clr;
  212.         char buf[2];
  213.  
  214.         wx= SQSZX*x + X0;
  215.         wy= SQSZY*y + Y0;
  216.         if (((x+y)&01) == 0)
  217.                 clr= 1;
  218.         else
  219.                 clr= 0;
  220.         if (n <= 0) {           /* unoccupied */
  221.                 SetAPen(Rp,clr);
  222.                 RectFill(Rp,wx,wy,wx+SQSZX-1,wy+SQSZY-1);
  223.         } else {                /* occupied */
  224.                 SetAPen(Rp,2L);
  225.                 SetBPen(Rp,clr);
  226.                 buf[0]= n/10 + '0';
  227.                 buf[1]= n%10 + '0';
  228.                 if (buf[0] == '0')
  229.                         buf[0]= ' ';
  230.                 Move(Rp,wx+TXX0,wy+TXY0);
  231.                 Text(Rp,buf,2L);
  232.         }
  233. }
  234.  
  235. /*
  236.  *      Sets the task priority to -10 to let more useful tasks
  237.  *      get the processor when they want it.
  238.  */
  239. nice()
  240. {
  241.         struct Task *mytcb,*FindTask();
  242.  
  243.         mytcb= FindTask(0L);
  244.         if (mytcb != NULL)
  245.                 SetTaskPri(mytcb,-10L);
  246. }
  247.  
  248. #if 0                   /* MANX has one of these */
  249. /*
  250.  *      Converts the positive decimal integer in string *s into
  251.  *      internal integer representation.
  252.  *      Doesn't check for overflow.
  253.  */
  254. atoi(s)
  255. char *s;
  256. {
  257.         int n;
  258.  
  259.         for (n=0; '0'<=*s && *s<='9'; s++)
  260.                 n= n*10 + *s - '0';
  261.         return(n);
  262. }
  263. #endif
  264.