Problème des huit dames

Un article de Wikipédia, l'encyclopédie libre.

Exemple de solution

Le problème des huit dames (parfois dit à tort problème des huit reines), est de placer huit dames d'un jeu d'échecs sur un échiquier de 8×8 cases sans que les dames ne puissent se menacer mutuellement, conformément aux règles du jeu d'échecs (la couleur des pièces étant ignorée.) Par conséquent, deux dames ne devraient jamais partager la même rangée, colonne, ou diagonale.

Simple mais non trivial, ce problème sert souvent d'exemple à des techniques de programmation.

Sommaire

1 Histoire
2 Élaboration d'une solution
3 Les solutions
4 Variantes
5 Le problème des huit dames en informatique
- 5.1 Programme d'exemple en Python
6 Programme d'exemple en C
7 Voir également
8 Références
9 Liens externes
- 9.1 Liens vers les solutions

[modifier] Histoire

Durant des années, beaucoup de mathématiciens, y compris Gauss ont travaillé sur ce problème, qui est un cas particulier du problème généralisé des n-dames, posé en 1850 par Franz Nauck, et qui est de placer n dames « libres » sur un échiquier de n×n cases. En 1874, S. Gunther proposa une méthode pour trouver des solutions en employant des déterminants, et J.W.L. Glaisher affina cette approche.

Ce problème fut utilisé au début des années quatre-vingt-dix, dans le jeu sur ordinateur The 7th Guest (Le Septième Invité).

[modifier] Élaboration d'une solution

Il existe un algorithme simple retournant une solution simple pour n dames si n n = 1 ou n ≥ 4:

Diviser n par 12. Se rappeler du reste (c'est 8 pour le problème des huit dames).
Écrire dans l'ordre la liste des nombres pairs de 2 à n.
Si le reste est 3 ou 9, mettre 2 à la fin de la liste.
Écrire dans l'ordre les nombres impairs de 1 à n, mais, si le reste est 8, permuter les deux à deux (ie 3, 1, 7, 5, 11, 9, …).
Si le reste est 2, permuter les places de 1 et 3, puis mettre 5 à la fin de la liste.
Si le reste est 3 ou 9, mettre 1 et 3 à la fin de la liste.
Placer la reine de la première colonne dans la ligne avec le premier nombre de la liste, placer la reine de la seconde colonne dans la ligne avec le deuxième nombre de la liste, etc.

Pour n = 8 ceci a pour conséquence la solution montrée ci-dessus.

14 dames (reste 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
15 dames (reste 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
20 dames (reste 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.

[modifier] Les solutions

Le problème des huit dames a 92 solutions distinctes, ou seulement 12 solutions en tenant compte de transformations telles que des rotations ou des réflexions (par l'intermédiaire du lemme de Burnside.)

Solution unique 1

Solution unique 2

Solution unique 3

Solution unique 4

Solution unique 5

Solution unique 6

Solution unique 7

Solution unique 8

Solution unique 9

Solution unique 10

Solution unique 11

Solution unique 12

[modifier] Variantes

Avec des pièces différentes

Trente-deux cavaliers, quatorze fous ou seize rois peuvent être disposés sur un échiquier traditionnel. Les pièces d'échecs féeriques peuvent remplacer les dames.

Avec des échiquiers différents: Pólya a étudié le problème des n-dames sur un échiquier toroïdal. D'autres supports ont été utilisés, comme les échiquiers tridimensionnels.
Le problème des dominations: Le problème est de trouver le nombre minimal de dames (ou d'autres pièces) nécessaires pour contrôler toutes les cases d'un échiquier n×n. Par exemple pour un échiquier « 8×8 », ce nombre vaut cinq.
Le problème des neuf dames (en anglais): Il faut placer neuf dames et un pion sur un échiquier classique, en évitant que les dames ne puissent se prendre. Ce problème se généralise en considérant un échiquier n×n et r dames (r>n) et il faut trouver le nombre minimum de pions, de telle sorte que les dames et les pions puissent être placés sur l'échiquier sans que des dames ne se menacent. Le problème général n'est toujours pas résolu.
Le Carré magique: En 1992, Demirörs, Rafraf et Tanik ont publié une méthode de conversion de carrés magiques en solutions du problème des n-dames, et réciproquement.
Le carré latin
Les problèmes d'échecs
Les types de problèmes d'échecs

[modifier] Le problème des huit dames en informatique

Le problème des huit dames est un bon exemple de problème simple mais non évident. Pour cette raison, il est souvent employé comme support de mise en œuvre de différentes techniques de programmation, y compris d'approches non traditionnelles de la programmation telles que la programmation par contraintes, la programmation logique ou les algorithmes génétiques.

Le plus souvent, il est employé comme exemple d'un problème qui peut être résolu avec un algorithme récursif, en exprimant qu'une solution du problème des n-dames peut être obtenue, par récurrence, à partir d'une solution quelconque du problème des (n-1)-dames par l'adjonction d'une dame. La récurrence commence avec la solution du problème de 0-dame qui repose sur un échiquier vide.

Cette technique est beaucoup plus efficace que l'algorithme naïf de recherche exhaustive, qui parcourt chacun des 64⁸ = 2⁴⁸ = 281 474 976 710 656 placements possibles des huit dames, pour retirer tous ceux pour lesquels plusieurs dames se trouvent sur une même case (laissant seulement $A_{64}^8=64!/56! = 178 462 987 637 760$ arrangements possibles) ou pour lesquels des dames se menacent mutuellement.

Ce très « mauvais » algorithme, produira les mêmes résultats à plusieurs reprises en attribuant différentes places aux huit dames, et recommencera les mêmes calculs plusieurs fois pour différentes parties de chaque solution. Un algorithme légèrement meilleur de recherche exhaustive place une seule dame par rangée, réduisant à seulement 8⁸ = 2²⁴ = 16 777 216 placements possibles.

Il est possible de faire beaucoup mieux que cela. Par exemple, le programme de recherche en profondeur ci-dessous examine seulement 15 720 placements possibles des dames en construisant un arbre de recherche et en parcourant les rangées de l'échiquier une par une, éliminant la plupart des positions possibles à un stade très primitif de leur construction.

La programmation par contraintes est bien plus efficace pour ce problème. Un algorithme de « réparation itérative » commence typiquement à partir d'un placement de toutes les dames sur l'échiquier, par exemple avec une seule dame par colonne. Il compte alors le nombre de conflits entre dames, et utilise une méthode heuristique pour déterminer comment améliorer les placements des dames. La méthode heuristique de moindre conflit, qui consiste à déplacer la pièce ayant le plus grand nombre de conflits, dans la même colonne à une place où le nombre de conflits est le plus petit, est particulièrement efficace. Elle résout le problème des millions de dames (sur un échiquier de 1 000 000× 1 000 000 cases) en moins de 50 étapes en moyenne!

L'obtention de cette moyenne de 50 étapes suppose que la configuration initiale soit raisonnablement bonne. Si au début, un million de dames sont placées dans la même rangée, l'algorithme prendra évidemment plus de 50 étapes pour résoudre le problème. Un point de départ « raisonnablement bon » consiste à placer chaque dame dans une colonne telle qu'elle soit en conflit avec le plus petit nombre de dames se trouvant déjà sur l'échiquier.

Remarquez que la méthode de réparation itérative, à la différence de la recherche en profondeur décrite ci-dessus, ne garantit pas une solution. Comme toutes les méthodes de plus profonde descente, elle peut se bloquer sur un extremum local (dans ce cas l'algorithme peut être remis en marche avec une configuration initiale différente.) D'un autre côté, elle peut résoudre des problèmes de grandes tailles qui sont largement au-delà de la portée d'une recherche en profondeur.

[modifier] Programme d'exemple en Python

Ce programme écrit en langage de programmation Python emploie la recherche en profondeur combinée avec les règles suivantes:

aucune paire de pièces ne peut partager la même rangée;
toute solution pour n dames sur un échiquier de n× m doit contenir une solution pour (n-1)-dames sur un échiquier de (n-1)× m;
cette marche à suivre maintiendra toujours les dames dans l'ordre, et produira chaque solution seulement une fois.

 # Retourne une liste de solutions du problème des ''n''-dames sur un
 # échiquier de ''n'' par ''n''. Une solution est représentée par une liste de
 # positions de colonnes des dames, indexées par les lignes.  
 # Les lignes et les colonnes sont indexées à partir de zéro.
 def n_dames(n, largeur):
     if n == 0:
         return [[]] # une solution, la liste vide
     else:
         return ajoute_dame(n-1, largeur, n_dames(n-1, largeur))

 # Essaie toutes les façons d'ajouter une dame à une colonne d'indice la ligne nouvelle_ligne, et retourne
 # une liste de solutions.  precedentes_solutions doit être une liste de solutions 
 # pour le problème des nouvelle_ligne-dames.
 def ajoute_dame(nouvelle_ligne, largeur, precedentes_solutions):
     solutions = []
     for sol in precedentes_solutions:
         # Essaie de placer une dame sur chaque colonne à la ligne nouvelle_ligne.
         for nouvelle_colonne in range(largeur):
             # print 'essaie', nouvelle_colonne, 'à la ligne', nouvelle_ligne
             if dame_sans_danger(nouvelle_ligne, nouvelle_colonne, sol):
                 # Pas d'interférence, donc ajoute cette solution à la liste.
                 solutions.append(sol + [nouvelle_colonne])
     return solutions

 # Peut-on ajouter sans danger une dame à sol en (nouvelle_ligne, nouvelle_colonne)?  Retourne
 # true si c'est le cas.  sol doit être une solution au problème des nouvelle_ligne-dames.
 def dame_sans_danger(nouvelle_ligne, nouvelle_colonne, sol):
     # Vérifie de nouveau chaque pièce en chacune des nouvelle_ligne lignes existantes.
     for ligne in range(nouvelle_ligne):
         if (sol[ligne] == nouvelle_colonne or                  # conflit sur une même colonne
             sol[ligne] + ligne == nouvelle_colonne + nouvelle_ligne or  # conflit sur une diagonale
             sol[ligne] - ligne == nouvelle_colonne - nouvelle_ligne):   # autre diagonale
                 return 0
     return 1

 for sol in n_dames(8, 8):
    print sol

[modifier] Programme d'exemple en C

Ce Programme écrit en C, renvois sous la forme "XXXXXXXX" la totalité des solutions au problème des 8 dames.


my_putchar(char c)
{
  write (1, &c, 1)
}

int     testit(int tab[10], int i, int c)
{
  int   a;
  int   b;

  a = 1;
  b = 0;
  while (c - a >= 1)
    {
      if (tab[c - a] == i )
        b++;
      if (tab[c - a] + a == i)
        b++;
      if (tab[c - a] - a == i)
        b++;
      a++;
    }
  if (b == 0 || c ==  1)
    return(1);
  else
    return(0);
}

int     print_it(int tab[9])
{
  my_putchar(tab[1] + '0');
  my_putchar(tab[2] + '0');
  my_putchar(tab[3] + '0');
  my_putchar(tab[4] + '0');
  my_putchar(tab[5] + '0');
  my_putchar(tab[6] + '0');
  my_putchar(tab[7] + '0');
  my_putchar(tab[8] + '0');
  my_putchar('\n');
}

int     my_chess(int tab[10], int i, int c)
{
  int   a;

  tab[c] = i;
  i = 1;
  c++;
  if (c == 9)
    {
      tab[0]++;
      print_it(tab);
      return(tab);
    }
  while (i < 9)
    {
      a = testit(tab, i, c);
      if (a == 1)
        tab = my_chess(tab, i, c);
      i++;
    }
  return (tab);
}

int     my_8r2()
{
  int   tab[9];
  int   i;

  i = 0;
  while (i < 10)
    {
      tab[i] = 0;
      i++;
    }
  tab[0] = my_chess(tab, 0, 0);
  return(tab[0]);
}