/*************************************************************
*             Chess: Problem of the Eight Queens             *
* ---------------------------------------------------------- *
* Description:                                               *
* This famous problem consists in finding locations of eight *
* queens on a chess board,  such as no one can be taken by   *
* another one. After Arthur Engel Cedic (1979), this problem *
* was posed for the first time in 1848 by Max Bezzel in a    *
* Chess Journal. This publication gave way to an extraordi-  *
* nary passion and on sept. 21th, 1850 a certain Dr Nauck    *
* gave all the solutions when the famous mathematician Gauss *
* had only found 72 out of 92. But it is true that he had    *
* better to attend to... This small program gives all the    *
* solutions from n=4 to n=8 (size of board) by using the so  *
* called "backtracking method".                              *
* ---------------------------------------------------------- *
* REFERENCE:                                                 *
* "Graphisme dans le plan et dans l'espace avec Turbo Pascal *
*  4.0 By R. Dony - MASSON, Paris 1990".                     *
*                                                            *
*             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, hpenOld;


//"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   365
#define  N    38
#define  BLUE  1

#define  FALSE 0
#define  TRUE  1

typedef int Rt[9]; 

Rt   R;                // table storing one solution
Rt   S[93];            // maximum 92 solutions
Rt   Xr, Yr;
int  i,j,order;
bool ok, fin;
int  x,y,k,l;
int  num, old;
int  Numsol[9];

const int pasy=N;

  void ReadOrder() {
    int i;
    order=8;
    for (i=0; i<9; i++) R[i]=0;
  }

  void DrawQueen(int x, int y) {
    int xc,yc,xd,yd,x1,y1;
    xd=x+28; yd=y+35; xc=x+43; yc=y+35; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; yc=yc-4; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-30; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; yc=yc+4;  DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+15; DrawLine(xd,yd,xc,yc);
    xd=xc-15; yd=yc; xc=xc-20; yc=yc-15; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+5; yc=yc-5; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+5; yc=yc-1; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+5; yc=yc-2; DrawLine(xd,yd,xc,yc);
    x1=xc; y1=yc; 
    xd=xc-2; yd=yc; xc=xc; yc=yc+20; DrawLine(xd,yd,xc,yc);
    xd=x1; yd=y1; xc=x1+10;yc=y1;   DrawLine(xd,yd,xc,yc);
	xd=x1; yd=y1; xc=xc+5; yc=yc+2; DrawLine(xd,yd,xc,yc);
    x1=xc; y1=yc;
    xd=xc; yd=yc; xc=xc-2; yc=yc+18;DrawLine(xd,yd,xc,yc);
    xd=x1; yd=y1; xc=x1+5; yc=y1+1; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc+5; yc=yc+5; DrawLine(xd,yd,xc,yc);
    xd=xc; yd=yc; xc=xc-4; yc=yc+15;DrawLine(xd,yd,xc,yc);
    Ellipse(hdc,x+ 8,y+13,x+12,y+17);
    Ellipse(hdc,x+18,y+10,x+22,y+14);
    Ellipse(hdc,x+28,y+ 8,x+32,y+12);
    Ellipse(hdc,x+38,y+10,x+42,y+14);
    Ellipse(hdc,x+48,y+15,x+52,y+19);
  }

  void Init() {
    char c[2];
    Xr[1]=0; Yr[1]=M-42;
    for (i=2; i<=order; i++)  Xr[i]=Xr[i-1]+50;
    for (i=2; i<=order; i++)  Yr[i]=Yr[i-1]-N;
    fin=FALSE;
    i=0; num=0; k=-1;
    l=(9-order)*N-25;
    DrawQueen(6,0);
	sprintf(c,"%d", order);
    OutText(31,17,c);
    Numsol[4]= 2;
    Numsol[5]=10;
    Numsol[6]= 4;
    Numsol[7]=40;
    Numsol[8]=92;
  }

  void DrawBoard() {
    int i;
    for (i=0; i<=order; i++)
      DrawLine(5,M-i*N,5+50*order,M-i*N);
    for (i=0; i<=order; i++)
      DrawLine(5+i*50,M, 5+i*50,M-N*order);
  }

  void TestPreviousQweens() {
    ok=TRUE;
    j=1;
    while (j <= i-1 && (ok)) {
      if (R[i]==R[j] || abs(R[i]-R[j])==i-j) ok=FALSE;
      j++;
    }
  }

  void ColumnDown() {
    R[i]=0;
    i--;
    if (i==0) fin=TRUE;
    else i--;
  }

  void DrawSolution(int n, int coul) {
    int i;
    if (coul==BLUE)
      for (i=1; i<=order; i++)
        DrawQueen(Xr[i],Yr[S[n][i]]);
  }

  void Display() {
    char ch[9], chaine[9];
    short j;
    strcpy(chaine,"");
    num++; 
	for (j=1; j<=order; j++) 
	  S[num][j]=R[j];
	for (j=1; j<=order; j++) {
      sprintf(ch,"%d", R[j]);
      strcat(chaine,ch);
    }
    k++;
    switch(k % 3) {
	  case 0: {OutText(410,l,chaine); break;}
      case 1: {OutText(480,l,chaine); break;}
      case 2: {OutText(550,l,chaine); l += 15;}
    }
  }

  void SeekSolution() {
    char ch[15];
	while (!fin) {
      i++; 
      while (i<=order && (!fin)) {
        ok=FALSE;
        while (R[i]<order && (!ok)) {
          R[i]=R[i]+1;
          TestPreviousQweens();
        }
        if (!ok) ColumnDown();
	    i++;
      }
      if (!fin) {
        Display();
        R[order]=0;
        i=order-2;
      }
    }
    MessageBeep(0);
	sprintf(ch,"%2d solutions.", num);
    OutText(130,17, ch);
  }

  // main subroutine
  void Exec_Queens() {
    int n; char ch[15];
    ReadOrder();
    Init();
    DrawBoard();
	SeekSolution();
	n=10;
    DrawSolution(n,BLUE);
	sprintf(ch,"Solution #%d", n);
	OutText(125,380,ch);
  }

// end specific section


//Handle window Paint and Destroy messages
long FAR PASCAL /*_export*/ WndProc(HWND hwnd,
    UINT message, UINT wParam, LONG lParam) 
{
   
    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_Queens();
               
            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[] = "Queens";
    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 QUEENS", // window caption
        WS_OVERLAPPEDWINDOW,        // window style                       
        CW_USEDEFAULT,              // initial x position
        CW_USEDEFAULT,              // initial y position
        650,                        // initial x size
        550,                        // 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 queens.cpp