Probleme du cavalier [backtracking]

Télécharger le projet
Commenter

Description

résolution du problème du cavalier :
trouver une parcours du cavalier sur un jeu d'échec dans lequel il passe
par toutes les cases une et une seule fois.

L'algorithme consite à énumerer toutes les solutions, enfin presque,
on ne visite pas des branches entieres de solutions quand on
sait a l'avance qu'il n'y aura aucune solution.
Des que l'on sait que l'on va aboutir sur une impasse, on retourne
en arrière, on rebrousse chemin, et on passe a une autre solution,
c'est le principe du "backtracking"

L'algorithme peut etre améliorer avec quelques optimisations,
mais je préfére donner l'algorithme brute, directment lié
au principe du "backtracking".

Source / Exemple : 


//-------------------------------------------------
// 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()
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_JCDjcd)