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, c'est-à-dire qu'elles ne partagent ni la même ligne, ni la même colonne, ni la même diagonale.

Ce programme initialement réalisé en 1992 donne l'ensemble des solutions.

Version initiale

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

Version révisée pour une meilleure présentation des résultats

// problème des huit reines

#include <stdio.h>
#include <time.h>

typedef struct {
	int nb_reines;
	int reineligne[8];
	bool reinecol[8];
	bool reinediagp[15];
	bool reinediags[15];
} Echiquier;

void afficher (Echiquier *echiq)
{
int i, j;
static int n=1;

	printf ("----------%d\n",n++);
	for (i=0; i<8; i++) {
		for (j=0; j<8; j++)
			if (echiq->reineligne[i] == j+1)
				printf ("Q ");
			else if ((i+j)%2)
				printf ("□ ");
			else
				printf ("■ ");
		printf ("\n");
	}
	printf ("\n");
}

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

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

Solutions

92 solutions sont trouvées. En voici une :