/*      ktour.c
 *
 *      Finds a knight tour of a chess board by exhaustive search.
 *      Displays progress of the search graphically.
 *
 *      usage:  run ktour [n]
 *              The option N specifies the chess board size.
 *              The default and maximum value for N is 8.
 *
 *      author:
 *              Douglas A. Jones
 *              181-1000 Oaks Drive
 *              Atlantic Highlands, NJ 07716
 *
 *      This program may be freely redistributed.
 *
 *      Compiled with MANX 3.6, haven't tried Lattice or earlier
 *      versions of MANX.
 */

#include <exec/types.h>
#include <exec/nodes.h>
#include <exec/tasks.h>
#include <exec/memory.h>
#include <intuition/intuition.h>
#include <stdio.h>
#include <functions.h>

struct NewWindow Newwind = {
        0,0, 0,0,       /* size to be filled in later */
        -1,-1, CLOSEWINDOW,
        WINDOWCLOSE|WINDOWDEPTH|WINDOWDRAG|SMART_REFRESH,
        NULL,NULL,
        (UBYTE *)"Knight tour",
        NULL,NULL, 0,0,0,0, WBENCHSCREEN
};
struct Window *Wind = NULL;
struct RastPort *Rp;
struct GfxBase *GfxBase;
struct IntuitionBase *IntuitionBase;

/*
 *      Constants for drawing chess board
 */
#define SQSZX   31
#define SQSZY   15
#define X0      5
#define Y0      11
#define TXX0    8
#define TXY0    10

#define MXBOARDSZ       8               /* maximum board size */
char Occupied[MXBOARDSZ][MXBOARDSZ];    /* position occupied flag */
int Boardsz = MXBOARDSZ;                /* size of chess board */

/*
 *      Initializes the board and then tries all starting positions
 *      that are not reflections.
 *      Reduces the task priority so that more important things
 *      will run faster.
 */
main(argc,argv)
int argc;
char **argv;
{
        int i,j;

        if (argc > 1)
                Boardsz= atoi(argv[1]);
        if (Boardsz<1 || Boardsz>MXBOARDSZ)
                Boardsz= MXBOARDSZ;
        openwindow(Boardsz*SQSZX+X0+5,Boardsz*SQSZY+Y0+2);
        nice();
        for (i=0; i<Boardsz; i++) {
                for (j=0; j<Boardsz; j++) {
                        Occupied[i][j]= 0;
                        draw(i,j,0);
                }
        }
        for (i=0; i<(Boardsz+1)/2; i++)
                for (j=i; j<(Boardsz+1)/2; j++)
                        tour(i,j,1);
        waitclose();
}

/*
 *      Tries to move to position x,y.
 *      If the move is legal, all subsequent moves are tried by
 *      recursive call.
 *      Stops and waits for the close-window gadget to be clicked
 *      when a feasible solution is found.
 *      Nmove is the move number.
 */
tour(x,y,nmove)
int x,y,nmove;
{

        if (x<0 || y<0 || x>=Boardsz || y>=Boardsz)
                return;         /* off the board */
        if (Occupied[x][y])
                return;         /* position occupied */
        Occupied[x][y]= 1;
        draw(x,y,nmove);
        if (nmove >= Boardsz*Boardsz)
                waitclose();    /* found solution */
        chkclose();             /* give up ? */
        tour(x-1,y-2,nmove+1);
        tour(x-2,y-1,nmove+1);
        tour(x-2,y+1,nmove+1);
        tour(x-1,y+2,nmove+1);
        tour(x+1,y+2,nmove+1);
        tour(x+2,y+1,nmove+1);
        tour(x+2,y-1,nmove+1);
        tour(x+1,y-2,nmove+1);
        Occupied[x][y]= 0;
        draw(x,y,0);
}

/*
 *      Opens a window in which to draw the chess board.
 *      Also opens the intuition and graphics libraries.
 */
openwindow(x,y)
int x,y;
{

        IntuitionBase= (struct IntuitionBase *)
         OpenLibrary("intuition.library",0L);
        if (IntuitionBase != NULL) {
                GfxBase= (struct GfxBase *)
                  OpenLibrary("graphics.library",0L);
                if (GfxBase != NULL) {
                        Newwind.Width= x;
                        Newwind.Height= y;
                        Wind= OpenWindow(&Newwind);
                        if (Wind != NULL) {
                                Rp= Wind->RPort;
                                return;
                        }
                        fprintf(stderr,"can't open window\n");
                        CloseLibrary(GfxBase);
                }
                fprintf(stderr,"can't open graphics.library\n");
                CloseLibrary(IntuitionBase);
        }
        fprintf(stderr,"can't open intuition.library\n");
        exit(1);
}

/*
 *      Closes the window and libraries.
 */
closewindow()
{

        CloseWindow(Wind);
        CloseLibrary(GfxBase);
        CloseLibrary(IntuitionBase);
}

/*
 *      Waits for the user to click the close-window gadget,
 *      then closes the window and exits.
 */
waitclose()
{

        for (;;) {
                Wait(1L << Wind->UserPort->mp_SigBit);
                chkclose();
        }
}

/*
 *      Checks to see if the close-window gadget has been clicked.
 *      If so, closes the window and exits.
 */
chkclose()
{
        struct IntuiMessage *msg;
        long class;
        int done;

        done= 0;
        while (msg= (struct IntuiMessage *) GetMsg(Wind->UserPort)) {
                class= msg->Class;
                ReplyMsg(msg);
                switch (class) {
                 case CLOSEWINDOW:
                        done= 1;
                        break;
                 default:
                        break;
                }
        }
        if (done) {
                closewindow();
                exit(1);
        }
}

/*
 *      Draws square x,y of the chess board.
 *      If n is <= 0, the background color of the square is drawn.
 *      Otherwise, only the number n is drawn (presumably the
 *      background was already drawn).
 */
draw(x,y,n)
int x,y,n;
{
        long wx,wy,clr;
        char buf[2];

        wx= SQSZX*x + X0;
        wy= SQSZY*y + Y0;
        if (((x+y)&01) == 0)
                clr= 1;
        else
                clr= 0;
        if (n <= 0) {           /* unoccupied */
                SetAPen(Rp,clr);
                RectFill(Rp,wx,wy,wx+SQSZX-1,wy+SQSZY-1);
        } else {                /* occupied */
                SetAPen(Rp,2L);
                SetBPen(Rp,clr);
                buf[0]= n/10 + '0';
                buf[1]= n%10 + '0';
                if (buf[0] == '0')
                        buf[0]= ' ';
                Move(Rp,wx+TXX0,wy+TXY0);
                Text(Rp,buf,2L);
        }
}

/*
 *      Sets the task priority to -10 to let more useful tasks
 *      get the processor when they want it.
 */
nice()
{
        struct Task *mytcb,*FindTask();

        mytcb= FindTask(0L);
        if (mytcb != NULL)
                SetTaskPri(mytcb,-10L);
}

#if 0                   /* MANX has one of these */
/*
 *      Converts the positive decimal integer in string *s into
 *      internal integer representation.
 *      Doesn't check for overflow.
 */
atoi(s)
char *s;
{
        int n;

        for (n=0; '0'<=*s && *s<='9'; s++)
                n= n*10 + *s - '0';
        return(n);
}
#endif