Backtracking : Les 8 Reines

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

// problème des huit reines

#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 int 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++;30
  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);
      }
  }
}

int 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;
}