Backtracking : Les 8 Reines

Le problème des huit reines consiste à positionner 8 reines sur un échiquier afin qu'aucun de ces reines ne puissent en menacer une autre.

// problème des huit reines



#include <conio.h>         

#include <stdio.h>

#include <time.h>



typedef int bool;



typedef struct {

  int nb_reines;

  int reineligne[8];

  bool reinecol[8];

  bool reinediagp[15];

  bool reinediags[15];

} Echiquier;



void afficher (Echiquier *echiq)

{

int i;

static n=1;



  printf ("\n----------%d\t",n++);

  for (i=0; i<8; i++)

    printf ("%d-%d ", i+1, echiq->reineligne[i]);

}



bool case_ok (Echiquier *echiq, int ligne, int col)

{

int diagp, diags;



  diagp = ligne + col - 2;

  diags = col - ligne + 7;

  return echiq->reinecol[col-1] && echiq->reinediagp[diagp]

    && echiq->reinediags[diags];

}



void ajouter_reine (Echiquier *echiq, int ligne, int col)

{

  echiq->nb_reines++;

  echiq->reineligne[ligne-1] = col;

  echiq->reinecol[col-1] = 0;

  echiq->reinediagp[ligne + col - 2] = 0;

  echiq->reinediags[col - ligne + 7] = 0;

}



void retirer_reine (Echiquier *echiq)

{

int i;



  echiq->nb_reines--;

  for (i = 0; i < 8; i++)

    echiq->reinecol[i] = 1;

  for (i = 0; i < 15; i++)

    echiq->reinediags[i] = echiq->reinediagp[i] = 1;

  for (i = 0; i < echiq->nb_reines; i++) {

    echiq->reinecol[ echiq->reineligne[i] - 1] = 0;

    echiq->reinediagp [ i + echiq->reineligne[i] -1 ] = 0;

    echiq->reinediags [ echiq->reineligne[i] - i + 6 ] = 0;

  }

}











void pb_reines (Echiquier *echiq)

{

int ligne,col;



  if (echiq->nb_reines == 8)

    afficher (echiq);

  else {

    ligne = echiq->nb_reines +1;

    for (col = 1 ; col <= 8; col++)

      if (case_ok (echiq, ligne, col)) {

        ajouter_reine (echiq, ligne, col);

        pb_reines (echiq);

        retirer_reine (echiq);

      }

  }

}



main ()

{

Echiquier echiquier = {0, {0, 0, 0, 0, 0, 0, 0, 0},

              {1, 1, 1, 1, 1, 1, 1, 1},

              {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},

              {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};



time_t t1,t2;



  t1 = time(NULL);

  pb_reines (&echiquier);

  t2 = time(NULL);

  printf ("temps = %f", difftime(t2,t1));

  return 0;

}