/* The solution to the N queen problem.

   Let N be a natural number.
   Take an NxN chess board and N queens.
   Try to place the N queens on the chess board
   so that no queen is threatened.
   If N=1 there is obviously a solution.
   If N=2 there is obviously no solution.
   The algorithm is recursive. The time taken to
   calculate the solution increases exponentially
   with N.

Implemented by:
E. Lenz
Johann-Fichte-Strasse 11
8 Munich 40                                               */

#include <intuition/intuition.h>

#define FOREVER for(;;)

extern void *OpenLibrary();
extern void *OpenWindow();
extern void *GetMsg();

struct IntuitionBase *IntuitionBase;
struct GfxBase *GfxBase;
struct IntuiMessage *message;
struct RastPort *rp;
struct Window *w;

struct NewWindow nw =
{  0, 0,                  /*  left edge, top edge    */
   640, 256,              /*  width, height,         */
   0, 1,                  /*  detail, block pens     */
   CLOSEWINDOW            /*  IDCMP flags            */
 | MENUPICK,
                          /*  Regular flags for gadgets and such */
   WINDOWDEPTH
 | WINDOWSIZING
 | WINDOWDRAG
 | WINDOWCLOSE
 | SMART_REFRESH
 | ACTIVATE,

   NULL,                                   /* First gadget in list        */
   NULL,                                   /* User checkmark              */
   (UBYTE *)"The N Queen Problem: N=012",  /* Window Title                */
   NULL,                                   /* Pointer to screen           */
   NULL,                                   /* Pointer to superbitmap      */
   50, 25, 640, 256,                       /* Min and max size            */
   WBENCHSCREEN,                           /* Using the Workbench screen  */
};

struct IntuiText Queens =
{       0,1,                           /* frontpen, backpen */
        JAM1,                          /* drawmode */
        1,1,                           /* leftedge, topedge */
        NULL,                          /* TextAttr */
        (UBYTE *)" Number of queens",  /* IText */
        NULL,                          /* NextText */
};

struct MenuItem nqueens =
{       (struct MenuItem *) NULL,
        0,10,                                /* LeftEdge, TopEdge */
        150,10,                             /* Width, Height */
        ITEMTEXT | HIGHCOMP | ITEMENABLED,  /* Flags */
        0,                                  /* Mutual Exclude */
        (APTR)&Queens,                      /* ItemFill */
        NULL,                               /* SelectFill */
        0,                                  /* Command    */
        NULL,                               /* Subitem */
        0,                                  /* NextSelect */
};

struct IntuiText Noth =
{       0,1,                           /* frontpen, backpen */
        JAM1,                          /* drawmode */
        1,1,                           /* leftedge, topedge */
        NULL,                          /* TextAttr */
        (UBYTE *)"",                   /* IText */
        NULL,                          /* NextText */
};


struct MenuItem nothing =
{       (struct MenuItem *) &nqueens,
        0,0,                               /* LeftEdge, TopEdge */
        150,10,                             /* Width, Height */
        ITEMTEXT | HIGHCOMP | ITEMENABLED,  /* Flags */
        0,                                  /* Mutual Exclude */
        (APTR)&Noth,                        /* ItemFill */
        NULL,                               /* SelectFill */
        0,                                  /* Command    */
        NULL,                               /* Subitem */
        0,                                  /* NextSelect */
};

struct Menu menu =
{       (struct Menu *) NULL,        /* NEXT menu */
        0, 0, 150, 0,                /* LeftEdge, TopEdge, Width, Height */
        MENUENABLED,                 /* Flags */
        (BYTE *) "Number of queens", /* MenuName */
        (struct MenuItem *)&nothing, /* First item */
        0,0,0,0,                     /* JazzX,JazzY, BeatX, BeatY */
        };

#define STRINGSIZE 4
 UBYTE DefString[STRINGSIZE];
 UBYTE Undo [STRINGSIZE];

ULONG MessageClass;

main()
{  USHORT code;

 if (!(GfxBase = OpenLibrary("graphics.library",0L))) quit(1);
 if (!(IntuitionBase = OpenLibrary("intuition.library",0L))) quit(2);

 if (!(w = OpenWindow(&nw)))
   {  nw.Height=200;
      if (!(w = OpenWindow(&nw))) quit(3);
   }
 SetMenuStrip(w, &menu);

 rp = w->RPort;

 queen(12);

 FOREVER
    {  if (message = GetMsg(w->UserPort))
          { MessageClass = message->Class;
            code = message->Code;
            ReplyMsg(message);
            switch (MessageClass)
               {   case MENUPICK:     if ((code&0xff)!=0x20) break;
                                      queen(number());
                                      nw.Title[23]=DefString[0];
                                      nw.Title[24]=DefString[1];
                                      nw.Title[25]=DefString[2];
                                      SetWindowTitles(w,nw.Title,-1);
                                      break;
                   case CLOSEWINDOW : quit(0);
               }
          }
    }
}


quit(i)
int i;
{ if (w) CloseWindow(w);
  if (GfxBase) CloseLibrary(GfxBase);
  if (IntuitionBase) CloseLibrary(IntuitionBase);
  exit(i);
}

int abs(n)
int n;
{ return n>=0?n:-n; }

queen(n)
int n;
{  int s,h,j,k;
   int x[100];
   long l,m,o,p;

   SetAPen(rp,2L);
   Move(rp,100L,100L);
   Text(rp,"CALCULATING",11L);

   x[1]=1;
   h=2;
   k=1;
   while ((h<=n)&&(k<n))
     {  do
          { j=1;
            do
              {  s=((x[j]!=k)&&((h-j)!=abs(x[j]-k)));
                 j++;
              }
            while (!((j==h)||(s==FALSE)));
            if (s)
                x[h]=k;
            else
                k++;
          }
        while (!(s||(k>n)));
        if (message = GetMsg(w->UserPort))
          { MessageClass = message->Class;
            if (MessageClass==CLOSEWINDOW) quit(0);
          }
        if (s)
           { h++;
             k=1;
           }
        else
           do
             { if (h>1) h--;
               x[h] += 1;
               k = x[h];
             }
           while (!((k<n)||(h==1)));
     }

   SetAPen(rp,0L);
   o=nw.Width-2;
   p=nw.Height-2;
   RectFill(rp,2L,10L,o,p);

   if (!s)
      { SetAPen(rp,2L);
        Move(rp,100L,100L);
        Text(rp,"NO SOLUTION",11L);
        return;
      }

   SetAPen(rp,3L);
   k=(nw.Height-10)/n;
   m=nw.Width;
   for (h=1;h<n;h++)
       { l=h*k+10;
         Move(rp,0L,l);
         Draw(rp,m,l);
       }

   j=nw.Width/n;
   m=nw.Height;
   for (h=1;h<n;h++)
       { l=h*j;
         Move(rp,l,10L);
         Draw(rp,l,m);
       }

   SetAPen(rp,1L);
   for (h=1;h<=n;h++)
     { l=j*(h-1);
       m=k*(x[h]-1)+10;
       o=j*h;
       p=k*x[h]+10;
       RectFill(rp,l,m,o,p);
     }
}

/******************
  Get an integer
 ******************/

 struct IntuiMessage *message1;
 struct Window *w1;

 struct IntuiText ntext = {2,2,JAM1, 10, -11, 0,
   (UBYTE *) "Number entry", 0};

 struct StringInfo TexString = {
    DefString,                      /* Buffer - Pointer to Buffer */
    Undo,                           /* UndoBuffer - Undo buf ptr  */
    0,                              /* BufferPos - Init Chr Posn */
    STRINGSIZE,                     /* MaxChars - Max number of Chars */
    0, 0,                           /* DispPos - First Disp Chr */
    13,                             /* NumChars - Number of Characters */
    0, 0, 0,                        /* Posn Vars calc by Intuition */
    NULL,                           /* No pointer to Rasport */
    0,                              /* Longint Value */
    NULL                            /* No pointer to alt Keyboard */
 };

 SHORT Pairs[] = {
 -1,  -1,                            /* Information describing the */
 160, -1,                            /* border around the gadget */
 160, 9,
 -1, 9,
 -1, -1
  };

 #define NUM_PAIRS 5                /* There are Four pairs above */

 struct Border StrBorder = {
  -1, -1,                           /* LeftEdge, TopEdge */
  1, 0, JAM1,                       /* FrontPen,  BackPen  DrawMode  */
  NUM_PAIRS,                        /* Number of XY Pairs */
  Pairs,                            /* XY, Pointer to XY Pairs */
  NULL                              /* No more borders */
 };

 struct Gadget tex_gad = {
    0, 30, 30, 150,11, GADGHCOMP, STRINGCENTER | LONGINT | RELVERIFY,
    STRGADGET, (APTR)&StrBorder, 0,
    &ntext, 0, (APTR)&TexString, 0, 0
 };

 struct NewWindow nw1 =
{  100, 100,              /*  Start position       */
   220, 70,               /*  width, height,       */
   0, 1,                  /*  detail, block pens   */
   CLOSEWINDOW            /*  IDCMP flags          */
 | REFRESHWINDOW
 | GADGETUP,
                          /*  Regular flags for gadgets and such */
   WINDOWDEPTH
 | WINDOWSIZING
 | WINDOWDRAG
 | WINDOWCLOSE
 | SMART_REFRESH,

   &tex_gad,                       /* First gadget in list         */
   NULL,                           /* User checkmark               */
   (UBYTE *)"Number of queens",    /* Window Title                 */
   NULL,                           /* Pointer to screen            */
   NULL,                           /* Pointer to superbitmap       */
   0, 0, 1, 1,                     /* Ignored because not sizeable */
   WBENCHSCREEN,                   /* Using the Workbench screen   */
   };

number()
{  ULONG MessageClass;
   int val;

   DefString[0]='0';
   DefString[1]='1';
   DefString[2]='2';
   if (!(w1 = OpenWindow(&nw1) )) return(12);

   FOREVER
    {  if (message1 = GetMsg(w1->UserPort))
        { MessageClass = message1->Class;
          ReplyMsg(message1);
          switch (MessageClass)
            { case GADGETUP    : CloseWindow(w1);
                                 val = (ULONG)TexString.LongInt;
                                 if ((val>1)&&(val<100)) return(val);
                                 DefString[0]='0';
                                 DefString[1]='1';
                                 DefString[2]='2';
                                 return(12);

              case CLOSEWINDOW : CloseWindow(w1);
                                 return(12);
            }
        }
    }
}