Probleme du cavalier [backtracking]

Soyez le premier à donner votre avis sur cette source.

Vue 12 208 fois - Téléchargée 623 fois

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()

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
3
Date d'inscription
vendredi 29 décembre 2006
Statut
Membre
Dernière intervention
17 novembre 2007

J'ai téléchargé et installé "Microsoft Visual C++ 2005" avec le "Platform SDK" et j'ai essayé de compiler l'ensemble des sources.

Je parviens à compiler chaque fichier ".c" (avec quelques Warnings) mais l'édition de liens conduit à des erreurs dans "main.obj", "winutil.obj" et "util.obj". Visiblement, le compilateur ne trouve pas "les bonnes librairies".

Peux-tu "éclairer ma lanterne" ?
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2
il faut creer un dossier "res" dans le dossier contenant le prgm.
Messages postés
755
Date d'inscription
samedi 15 mai 2004
Statut
Membre
Dernière intervention
30 janvier 2011

probleme : imposible d'ouvrir XXX.txt en mode wt
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2
Je ne connais pas cet environnement.
Normalement c'est un projet Win32 Application (enfin c'est ca sous VC++).
Messages postés
3
Date d'inscription
vendredi 29 décembre 2006
Statut
Membre
Dernière intervention
17 novembre 2007

Je suis totalement débutant en C++ (j'en suis resté au C sous UNIX !!!).

J'ai téléchargé l'IDE "Code::Blocks Studio" et j'aimerais savoir si tes sources sont compilables sous cet environnement et si "oui" quelle est la procédure à suivre (et notamment quel est le type de "projet" qu(il faut créer ?).
Afficher les 7 commentaires

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.