/***************************************************************
*               THE PROBLEM OF CHESS KNIGHT                    *
* ------------------------------------------------------------ *
* A question, in chess game, is to know wether a knight can    *
* go through all the board squares passing only once on each   *
* square. The answer is yes for a 8 x 8 board, as this small   *
* program shows. We use here the law givan by Warnsdorff in    *
* 1823 that almost always allows finding a solution:           *
* "In each strike, you must play the knight to the square from *
* which there are the less exits towards the squares not yet   *
* full."                                                       *
* ------------------------------------------------------------ *
*  After "Graphisme dans le plan et dans l'espace avec Turbo   *
*  Pascal 4.0 de R. Dony - MASSON 1990 page 227".              *
*                                                              *
*               C++ Release in API style By J-P Moreau, Paris. *
***************************************************************/
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

HDC  hdc;
RECT rect;
HPEN hpen;


//"home made" graphic commands for hdc environment used by above functions
void DrawPixel(int ix,int iy) {
  //sorry, no other available command found
  Rectangle(hdc,rect.left+ix,rect.top+iy,
	            rect.left+ix+2,rect.top+iy+1);
}

void Swap(int *i1,int *i2) {
  int it;
  it=*i1; *i1=*i2; *i2=it;
}

void DrawLine(int ix1,int iy1,int ix2,int iy2) {
  int i,il,ix,iy;
  float dx,dy;
  if (ix2<ix1) {
	Swap(&ix1,&ix2); Swap(&iy1,&iy2);
  }
  il=(int) sqrt((ix2-ix1)*(ix2-ix1)+(iy2-iy1)*(iy2-iy1));
  dx=(float) (ix2-ix1)/il; 
  dy=(float) (iy2-iy1)/il;
  ix=ix1; iy=iy1;
  for (i=1;i<il+1; i++) {
	DrawPixel(ix,iy);
	ix=(int) (ix1+i*dx); 
	iy=(int) (iy1+i*dy);
  }
}

void OutText(int ix,int iy,char *s) {
  RECT rct;
  rct.left=ix; rct.right=ix+10*strlen(s);
  rct.top=iy-5; rct.bottom=iy+15;
  DrawText(hdc, s, -1, &rct,
                DT_SINGLELINE | DT_CENTER | DT_VCENTER);
}

//begin specific section

#define  M      335     // set size of chessboard in pixels
#define  N      38

#define  FALSE  0
#define  TRUE   1

int  Echiquier[12][12],
     Xcasefuite[9],
     Ycasefuite[9],
     Nbrecasefuite[9];
bool casefuite;
int  lig,col,ct;
long duree;
int  compteur,cpt2,ordre,ligne,colonne;

HPEN FenPen,FenPen1;

const int pasy=N;

  void ReadOrder() {
    ordre=8; 
    duree=750000;  // for speed regulation
  }

  void ReadStart() {
    colonne=5;
	ligne=4;
  }

  void DisplaySolution() {
    char ch[12];
    sprintf(ch,"(%d,%d)", colonne, ligne);
    ct++;
    col=(ct % 3);
    switch(col) {
 	  case 0: {OutText(col*55+420,lig,ch); break;}
      case 1: {OutText(col*55+420,lig,ch); break;}
      case 2: {OutText(col*55+420,lig,ch); lig += 15;}
    }
  }

  void Init() {
    int l,c;
    for (l=0; l<12; l++)
      for (c=0; c<12; c++)
		Echiquier[l][c]=1;  
    for (l=2; l<=ordre+1; l++)
      for (c=2; c<=ordre+1; c++)
		Echiquier[l][c]=0; 
    compteur=0;
    casefuite=TRUE; ct=-1;
    lig=10+N*(8-ordre); col=0;
    FenPen =CreatePen(PS_SOLID,1,RGB(0,0,255));
    FenPen1=CreatePen(PS_SOLID,1,RGB(255,255,255));
  }

  void DrawKnight(int x, int y) {
    int xc,yc,xd,yd;
    xd=x+48; yd=y+33; xc=x+49; yc=yd; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+5;  yc=yc-13; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-5;  yc=yc-10; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-10; yc=yc-2;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; yc=yc-3;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-5;  yc=yc+3;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-2;  yc=yc-3;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-3;  yc=yc+3;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-5;  yc=yc+3;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-10; yc=yc+7;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; yc=yc+3;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+7;  yc=yc-2;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-5;  yc=yc+4;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+8;  yc=yc-2;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+10; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-10; yc=yc+9;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; yc=yc+3;  DrawLine(xd,yd,xc,yc);
	xd=xc; yd=yc; xc=x+48;  yc=y+33;  DrawLine(xd,yd,xc,yc);
    Ellipse(hdc,x+30,y+10,x+36,y+16);  // eye circle
  }

  void PutKnights() {
    char ch[3];
    int x,y;
    long i;
    double z;
    z=1.0;
    x=50*(colonne-1); y=M-N*ligne;
    SelectObject(hdc,FenPen);            // blue pen
    DrawKnight(x,y);
    MessageBeep(0);
    for (i=1; i<=duree; i++)  z += z*z;  // delay
	if (compteur<ordre*ordre-1) {
      SelectObject(hdc,FenPen1);         // white pen to erase (except last)
      DrawKnight(x,y);
    }
    compteur++;
    sprintf(ch,"%d", compteur);
    OutText(x+28,y+13,ch);
    Echiquier[ordre-ligne+2][colonne+1]=compteur;
    DisplaySolution();
  }

  void DrawBoard() {
    int i;
    SelectObject(hdc,FenPen);    // blue pen
    Rectangle(hdc,5,5,580,360);
    for (i=0; i<=ordre; i++)
      DrawLine(10,M-i*N,10+50*ordre,M-i*N);
    for (i=0; i<=ordre; i++)
      DrawLine(10+i*50,M,10+50*i,M-N*ordre);
  }

  void Test(int l,int c,int *cpt,int ind) {
	if (Echiquier[ordre-l+2][c+1]==0) {
      *cpt=*cpt+1;
      if (ind==1) {
        Xcasefuite[*cpt]=c;
        Ycasefuite[*cpt]=l;
      }
    }
  } 

  void GoAround(int lg, int cl, int *cpt,int ind) {
    int l,c;
    *cpt=0;
    casefuite=TRUE;
    l=lg+2; c=cl-1; Test(l,c,cpt,ind);
    l=lg+2; c=cl+1; Test(l,c,cpt,ind);
    l=lg+1; c=cl+2; Test(l,c,cpt,ind);
    l=lg-1; c=cl+2; Test(l,c,cpt,ind);
    l=lg-2; c=cl+1; Test(l,c,cpt,ind);
    l=lg-2; c=cl-1; Test(l,c,cpt,ind);
    l=lg-1; c=cl-2; Test(l,c,cpt,ind);
    l=lg+1; c=cl-2; Test(l,c,cpt,ind);
  }

  void FreeSquares() {
    int cpt,i,ll,cc;
	for (i=0; i<9; i++) {
      Xcasefuite[i]=0;
	  Ycasefuite[i]=0;
    }
    GoAround(ligne,colonne,&cpt,1);
    if (cpt != 0) {
      cpt2=cpt;
      for (i=1; i<=cpt2; i++) {
        cc=Xcasefuite[i];
        ll=Ycasefuite[i];
        GoAround(ll,cc,&cpt,2);
        Nbrecasefuite[i]=cpt;
      }
    }
    else 
      casefuite=FALSE;
  }

  void NextChoice() {
    int i, min,pos;
    min=255; pos=0;
    for (i=1; i<=cpt2; i++)
	  if (Nbrecasefuite[i] < min) {
        min=Nbrecasefuite[i];
        pos=i;
      }
    ligne=Ycasefuite[pos];
    colonne=Xcasefuite[pos];
  }

  void SeekSolution() {
	while (compteur < ordre*ordre && (casefuite)) {
      PutKnights();
	  FreeSquares();
      if (casefuite) NextChoice();
    }
  }

  // main function
  void Exec_Knights() {
    ReadOrder();
    ReadStart();
    Init();
    DrawBoard();
    OutText(100,15, "PROBLEM of CHESS KNIGHT");
    SeekSolution();
    DeleteObject(FenPen);
    DeleteObject(FenPen1);
  }

//end specific section


//Handle window Paint and Destroy messages
long FAR PASCAL /*_export*/ WndProc(HWND hwnd,
    UINT message, UINT wParam, LONG lParam) 
{
    HPEN        hpenOld;
    PAINTSTRUCT ps;

    switch (message) {
        case WM_PAINT:
	    hdc = BeginPaint(hwnd, &ps);
	    GetClientRect(hwnd, &rect);
            hpen = CreatePen(PS_SOLID, 1, RGB(0, 0, 255));
            hpenOld = SelectObject(hdc,hpen);

            Exec_Knights();
               
            SelectObject(hdc,hpenOld);
            DeleteObject(hpen);
			EndPaint(hwnd, &ps);
            return 0;
        case WM_DESTROY:
            PostQuitMessage(0);
            return 0;
    }
    return DefWindowProc(hwnd, message, wParam, lParam);
}

// main program
int PASCAL WinMain(HANDLE hInstance, HANDLE hPrevInstance,
    LPSTR lpszCmdParam, int nCmdShow)
{
    static char szAppName[] = "Knight";
    HWND        hwnd;
    MSG         msg;
    WNDCLASS    wndclass;

    if (!hPrevInstance) {
        wndclass.style         = CS_HREDRAW | CS_VREDRAW;
        wndclass.lpfnWndProc   = WndProc;
        wndclass.cbClsExtra    = 0;
        wndclass.cbWndExtra    = 0;
        wndclass.hInstance     = hInstance;
        wndclass.hIcon         = LoadIcon(NULL, IDI_APPLICATION);
        wndclass.hCursor       = LoadCursor(NULL, IDC_ARROW);
        wndclass.hbrBackground = GetStockObject(WHITE_BRUSH);
        wndclass.lpszMenuName  = NULL;
        wndclass.lpszClassName = szAppName;

        RegisterClass(&wndclass);
    }

    hwnd = CreateWindow(szAppName,  // window class name
        " PROBLEM OF CHESS KNIGHT", // window caption
        WS_OVERLAPPEDWINDOW,        // window style                       
        300,                        // initial x position
        300,                        // initial y position
        600,                        // initial x size
        425,                        // initial y size
        NULL,                       // parent window handle
        NULL,                       // window menu handle
        hInstance,                  // program instance handle
        NULL);                      // creation parameters

   ShowWindow(hwnd, nCmdShow);
   UpdateWindow(hwnd);

   while (GetMessage(&msg, NULL, 0, 0)) {
       TranslateMessage(&msg);
       DispatchMessage(&msg);
   }
   return msg.wParam;
}

//end of file knight.cpp