PROBLEME DU CAVALIER [BACKTRACKING]

//-------------------------------------------------
// INCLUDES
//-------------------------------------------------
#ifndef _UTIL_H_
	#include "util.h"
#endif // _UTIL_H_

#ifndef _MATH_H_
	#include "math.h"
#endif // _MATH_H_

#ifndef _DATA_H_
	#include "data.h"
#endif // _DATA_H_

#ifndef _WINUTIL_H_
	#include "winutil.h"
#endif // _WINUTIL_H_

//-------------------------------------------------
#define SIZE_CHESSBOARD 8

//-------------------------------------------------
// DATA_WINDOW
//-------------------------------------------------
typedef struct tagDATA_WINDOW
  {
  // handle sur la fenetre
  HWND              hwnd;
  // est-ce-que l'algorithme est fini ou non ? (vraiment utile pour un echiquier de taille < 8*8 ...)
  BOOL              bEndOfAlgo;
  // le damier, ou l'echiquier, une simple matrice d'entier
  //  0 -> case vide
  //  i -> le cheval etait present au i-eme coup
  U32               chessboard[SIZE_CHESSBOARD][SIZE_CHESSBOARD];
  //  quelques informations
  int               nbSol,nbTest;
  // pile des etapes ("STEP")
  STACK             stack;
  }DATA_WINDOW,*P_DATA_WINDOW,**PP_DATA_WINDOW;

//-------------------------------------------------
// permet de representer un couple d'entier
// (une coordonnee dans l'echiquier par exemple)
// qui pourront etre en fait dans une liste de
// couple
typedef struct tagPOSITION
  {
  LINK_DBL_LIST   link;   // le lien de la liste
  int             i,j;    // les coordonnees
  }POSITION,*P_POSITION,**PP_POSITION;

//-------------------------------------------------
// represente une etape
// le programme possede couramment une pile
// d'etape, une etape represente la position
// du cavalier a la <iStep>-eme etape sur la
// case de coordonnee (i,j)
// on construit a chaque fois la liste des cases
// que le cavalier pourra explorer a partir
// de ca position-ci et bien-sur en fonction
// de la configuration de l'echiquier courant
// (s'il est deja passe par un case par exemple...)
typedef struct tagSTEP
  {
  DBL_LIST    lstPos;   // liste des cases a visiter
  int         iStep;    // numero de l'etape
  int         i,j;      // coordonnees
  LINK_STACK  lnkStack; // lien de la pile
  }STEP,*P_STEP,**PP_STEP;

//-------------------------------------------------
// fonction tres stupide, mais tres utile !
// elle permet de rajouter un case a la liste des
// cases q'un cavalier peut aller (dans un etape)
// pour cela on lui fournit l'echiquier, la liste
// et les coordonnees (i,j)
// la valeur ajoutee de cette fonction, c'est que
// c'est elle qui verifie que (i,j) soit bien dans
// l'echiquier (par exemple on pourrait sortir
// du plateau) et que la case est bien vide
void addPos(U32 chessboard[SIZE_CHESSBOARD][SIZE_CHESSBOARD],P_DBL_LIST dblList,int i,int j)
{
if(
    // teste de validite de la plage des (i,j)
    i >= 0 && i < SIZE_CHESSBOARD && j >=0 && j< SIZE_CHESSBOARD
      &&
    // teste que la case est bien vide
    0 == chessboard[i][j]
   )
  {
  // tout est OK, on ajoute :
  P_POSITION pos;
  pos = Malloc(POSITION,1); // creation de la structure par allocation memoire
  pos->i = i; // initialisation des champs
  pos->j = j;
  InsertFirstLinkDblList(dblList,&pos->link); // on insert dans la liste ce nouvel element
  }
} // addPos()

//-------------------------------------------------
// la creation d'une etape consiste
// a placer le cavalier a la position
// et a construire la liste des cases accessibles
P_STEP createStep(P_DATA_WINDOW data,int i,int j,int iStep)
{
P_STEP step;

// initialisation
step                    = Malloc(STEP,1); // creation de l'etape par allocation memoire
step->iStep             = iStep;  // le numero de l'etape
step->i                 = i;  // coordonnees du cavalier
step->j                 = j;
PushLinkStack(&data->stack,&step->lnkStack); // ajout de l'etape dans la pile des etapes
data->chessboard[i][j]  = iStep; // placement du cavalier sur l'echiquier

InitDblList(&step->lstPos); // initialisation de la liste des positions possibles
// il y a 8 positions accessibles au maximum par le cavalier
// le cavalier peut se deplacer en L :
//  .......
//  ..8.1..
//  .7...2.
//  ...C...
//  .6...3.
//  ..5.4..
//  .......
addPos(data->chessboard,&step->lstPos,i + 1,j + 2); // #1
addPos(data->chessboard,&step->lstPos,i + 2,j + 1); // #2
addPos(data->chessboard,&step->lstPos,i + 2,j - 1); // #3
addPos(data->chessboard,&step->lstPos,i + 1,j - 2); // #4
addPos(data->chessboard,&step->lstPos,i - 1,j - 2); // #5
addPos(data->chessboard,&step->lstPos,i - 2,j - 1); // #6
addPos(data->chessboard,&step->lstPos,i - 2,j + 1); // #7
addPos(data->chessboard,&step->lstPos,i - 1,j + 2); // #8
return step;
} // createStep()

//-------------------------------------------------
// execution d'une etape de l'algorithme
// le principe est simple :
// on prend l'etape courante
// si la liste des cases possibles est vide
// alors on remonte, i.e. on a deja visite
// toutes les possibilites avec ce cavalier sur
// cette position, donc on passe a une autre position
// de ce cavalier.
// sinon la liste n'est pas vide, alors on prend
// la premiere case de la liste, et on deplace le
// cavalier sur cette case, et on appelle recursivement
// l'algorithme sur cette nouvelle case
void algo(P_DATA_WINDOW data)
{
data->bEndOfAlgo = (0 == data->stack.nElem);

if(!data->bEndOfAlgo)
  {
  P_LINK_STACK  curLinkStack;
  P_STEP        curStep;

  data->nbTest  ++; // un passage de plus !

  // on recupere l'etape courante
  curLinkStack  = FirstLinkStack(&data->stack);
  curStep       = FROM_TO(STEP,lnkStack,curLinkStack);
  if(curStep->lstPos.nElem > 0) // on teste la position suivante
    {
    P_LINK_DBL_LIST curLinkDblList;
    P_POSITION      curPos;

    // on recupere le premiere element de la liste
    curLinkDblList  = FirstLinkDblList(&curStep->lstPos);
    curPos          = FROM_TO(POSITION,link,curLinkDblList);
    // on appelle recursivement l'algorithme, i.e.
    // on ajoute un etape sur cette position, en
    // incrementant le numero de l'etape
    createStep(data,curPos->i,curPos->j,curStep->iStep + 1);

    // ici on teste si on trouve (enfin) un solution
    // le teste est simple, si le numero de l'etape
    // est exactement le nombre de case de l'echiquier alors ...
    if(1 + curStep->iStep == SIZE_CHESSBOARD*SIZE_CHESSBOARD)
      {
      P_FILE_UTIL   file;
      char          name[256];
      int           i,j;
      
      data->nbSol ++; // un solution de plus !!! BINGO !!!
      _snprintf(name,COUNT(name),"res\\solution[%d][%d].txt",SIZE_CHESSBOARD,data->nbSol);
      file = FileOpen(name,"wt"); // on ouvre le fichier
      // on ecrit la solution dans le fichier
      for(i=0;i<SIZE_CHESSBOARD;i++)
        {
        for(j=0;j<SIZE_CHESSBOARD;j++)
          {
          FilePrint((file,"  %2d",data->chessboard[i][j]));
          }
        FilePrint((file,"\n")); // saut de ligne
        }
      FileClose(file); // fermeture du fichier
      }

    // on enleve la case de la liste, car on vient de la traiter
    RemoveLinkDblList(&curStep->lstPos,curLinkDblList);
    Free(curPos); // liberation de l'allocation memoire
    }
  else // on remonte car la liste est vide
    {
    CloseDblList(&curStep->lstPos); // on ferme la liste (vide)
    PopLinkStack(&data->stack); // on enleve l'etape
    data->chessboard[curStep->i][curStep->j] = 0; // on efface la position du cavalier
    Free(curStep); // on libere l'allocation memoire
    }
  }
} // algo()

//-------------------------------------------------
// WND_PROC
//-------------------------------------------------
int WndProc(P_MY_WINDOW myWindow,HWND hwnd,UINT iMsg,WPARAM wParam,LPARAM lParam)
{
P_DATA_WINDOW   data;

data = (P_DATA_WINDOW)myWindow->userData;

switch(iMsg)
  {
  // creation de la fenetre
	case WM_CREATE:
    {

    // parametres de la fenetre
    myWindow->bResizedWindow   = TRUE;
    myWindow->bUseBackBuffer   = FALSE;
    myWindow->colorBackGround  = RGB_WHITE;

    // initialisations de la fenetre
    data->hwnd        = hwnd;
    data->bEndOfAlgo  = FALSE;
    data->nbSol       = 0;
    data->nbTest      = 0;

    // initialisation de l'algo.
      {
      int i,j;
      for(i=0;i<SIZE_CHESSBOARD;i++)
        {
        for(j=0;j<SIZE_CHESSBOARD;j++)
          {
          // on vide l'echiquier
          data->chessboard[i][j] = 0;
          }
        }
      }
    InitStack(&data->stack);
    createStep(data,0,0,1); // on mets le cheval dans un coin (par exemple)

    // initialisation du timer
    SetTimer(hwnd,314,250,NULL);

    break;
    }
  case WM_TIMER:
    {
    switch(wParam)
      {
      case 314:
        {
        DWORD t0;
        t0 = GetTickCount();
        while(GetTickCount() < 250 + t0) // on travaille pendant 1/4 de secondes
          {
          algo(data);
          }
        myRepaintWindow(hwnd); // on redessine la fenetre
        break;
        }
      }
    break;
    }
  // les touches
  case WM_KEYDOWN:
    {
    switch((int)wParam)
      {
/*
      // une etape, manuellement
      case 'A':
        algo(data);
        myRepaintWindow(hwnd);
        break;
*/
      default:
        break;
      }

    break;
    }
  // le commandes
  case WM_COMMAND:
    {
    switch(LOWORD(wParam))
      {
      }
    break;
    }
  // on dessine
	case WM_PAINT:
    {
    P_MY_HDC  hdc;
    int       cx,cy;

    cx  = myWindow->cx;
    cy  = myWindow->cy;
    hdc = (P_MY_HDC)wParam;

    SetBkMode(GetHdc(hdc),TRANSPARENT);

    if(data->bEndOfAlgo)
      {
      SetTextColor(GetHdc(hdc),RGB_RED);
      myPushFont(hdc,10,20,800,"Courier New");
        myTextOut(hdc,cx/2,0.5,2*cy/5,0.5,"Fin de l'algorithme");
        myTextOut(hdc,cx/2,0.5,3*cy/5,0.5,"%d solutions trouvées",data->nbSol);
      myPopFont(hdc);
      }
    //else
      {
      int cxFont,cyFont,dx,dy;
      int k,i,j;

  
      dx      = 50;
      dy      = 50;
      cxFont  = 15;
      cyFont  = 30;    

      myPushFont(hdc,cxFont,cyFont,800,"Courier New");
      // la grille
      myPushPen(hdc,PS_SOLID,0,RGB_LIGHTGRAY);
      for(k=0;k<=SIZE_CHESSBOARD;k++)
        {
        myLine(hdc,k*dx,0,k*dx,SIZE_CHESSBOARD*dy,FALSE);
        myLine(hdc,0,k*dy,SIZE_CHESSBOARD*dx,k*dy,FALSE);
        }
      myPopPen(hdc);
      // les numéros
      SetTextColor(GetHdc(hdc),RGB_BLACK);
      for(i=0;i<SIZE_CHESSBOARD;i++)
        {
        for(j=0;j<SIZE_CHESSBOARD;j++)
          {
          U32 nb;
          nb = data->chessboard[i][j];
          if(0 != nb)
            {
            myTextOut(hdc,(2*i+1)*dx/2,0.5,(2*j+1)*dy/2,0.5,"%d",nb);
            }
          }
        }
      // les informations
      SetTextColor(GetHdc(hdc),RGB_BLACK);
      myTextOut(hdc,0,0.,cy-2*cyFont,1.,"nombre d'essais : %d"  ,data->nbTest);
      myTextOut(hdc,0,0.,cy-1*cyFont,1.,"profondeur : %d"       ,data->stack.nElem);
      myTextOut(hdc,0,0.,cy-0*cyFont,1.,"%d solutions trouvées" ,data->nbSol);

      myPopFont(hdc);
      }

		break;
    }
  // destruction de la fenetre
	case WM_DESTROY:
    {
    // on vide la pile
    while(data->stack.nElem > 0)
      {
      P_LINK_STACK      linkStack;
      P_STEP            step;      
      linkStack = PopLinkStack(&data->stack); // on enleve l'element de la liste
      step      = FROM_TO(STEP,lnkStack,linkStack); // on recupere <STEP> a partir de <LINK_STACK>
      // on vide la liste de chaque etape de la pile
      while(step->lstPos.nElem > 0)
        {
        P_LINK_DBL_LIST   linkDblList;
        P_POSITION        pos;
        linkDblList = FirstLinkDblList(&step->lstPos); // on recupere un element de la liste (le premier)
        RemoveLinkDblList(&step->lstPos,linkDblList); // on supprime l'element de la liste
        pos = FROM_TO(POSITION,link,linkDblList); // on recupere <POSITION> a partir de <LINK_DBL_LIST>
        Free(pos); // on libere l'allocation memoire
        }
      CloseDblList(&step->lstPos); // on ferme la liste
      Free(step); // on libere l'allocation memoire
      }
    CloseStack(&data->stack); // on ferme la pile
    PostQuitMessage(0); // see you later ...
		break;
    }
  }


return 0;
} // WndProc()


//-------------------------------------------------
// WIN_MAIN
//-------------------------------------------------
int WINAPI WinMain(
                   HINSTANCE  hInstance,
                   HINSTANCE  hPrevInstance, 
                   LPSTR      lpszCmdLine,
                   int        iCmdShow
                   )       
{
WNDCLASSEX    wc;
RECT          rc;
P_MY_WINDOW   myWindow;
HWND          hwnd;
P_DATA_WINDOW data;
MSG           msg;


// ouverture des librairies
InitLibUtil();
InitLibWinutil(hInstance);

// initialisation de la classe
mySetDefaultWindowClass(&wc,hInstance);
wc.lpszClassName  = "JCD_PbCavalier";
mySetRectWH(&rc,0,0,500,500);

// creation de la fenetre
myWindow = myCreateWindow(&wc,
	                        " Problème du cavalier",
                          WS_OVERLAPPEDWINDOW,
                          &rc,
                          TRUE,
                          TRUE,
	                        NULL,
                          NULL,
	                        sizeof(DATA_WINDOW),
                          (void*)lpszCmdLine,
	                        WndProc
                          );

data = (P_DATA_WINDOW)myWindow->userData;
hwnd = myWindow->hwnd;

ShowWindow(hwnd,iCmdShow);
UpdateWindow(hwnd);
// boucle de messages
while(GetMessage(&msg,NULL,0,0))
	{
  TranslateMessage(&msg);
  DispatchMessage(&msg);
	}

// fermeture des librairies
CloseLibUtil();
CloseLibWinutil();

// tout va bien !
// see you later ...
return 0 ;
} // WinMain()