À propos du problème des huit dames | Retour sur trace et problème des n dames

Un casse-tête d’échecs de 1848

Max Bezzel, compositeur d’échecs allemand, a posé le problème dans une revue d’échecs berlinoise en 1848. Franz Nauck a publié les 92 solutions en 1850 et a posé la même question pour des échiquiers plus grands. Carl Friedrich Gauss a suivi le problème avec intérêt et en a parlé dans ses lettres.

Une dame par ligne et par colonne

Huit dames qui ne s’attaquent pas doivent se trouver sur huit lignes différentes et huit colonnes différentes. Une solution est donc un mélange des nombres de 1 à 8, une permutation, avec une règle en plus : deux dames ne peuvent pas partager une diagonale. Sur les 40 320 permutations, seules 92 conviennent.

Le retour sur trace

Le retour sur trace construit une solution morceau par morceau et revient en arrière dès qu’il tombe sur une impasse. Pour les dames : placez une dame sur la première case sûre de la ligne suivante, et quand une ligne n’a aucune case sûre, revenez à la ligne du dessus et faites avancer cette dame. En 1972, Edsger Dijkstra a utilisé ce problème pour expliquer la programmation structurée avec exactement cette recherche.

Symétrie

Faites tourner l’échiquier d’un quart de tour, ou reflétez-le, et une solution reste une solution. Cela donne jusqu’à huit versions de chacune. Les 92 solutions se répartissent en 12 familles de ce type : onze de 8 membres, et une de 4 seulement, parce que cette solution reste identique après un demi-tour.

Le problème des n dames

Sur un échiquier n×n, la question est la même avec n dames. Il existe des solutions pour tout n à partir de 4, et leur nombre croît vite : 2 pour 4×4, 92 pour 8×8 et 14 200 pour 12×12. Aucune formule n’est connue pour ce nombre ; les valeurs records viennent de grandes recherches par ordinateur.

Essayez dans PictorX

Ouvrez Huit dames et cliquez sur une case pour placer une dame ; cliquez de nouveau dessus pour la retirer. « Afficher les attaques » marque d’un point les cases que vos dames attaquent, et les dames en rouge s’attaquent entre elles. Résoudre lance la recherche par retour sur trace pas à pas et garde les dames que vous avez placées. Solution suivante parcourt toutes les solutions dans l’ordre, et Taille fait varier l’échiquier de 4×4 à 12×12.

Questions fréquemment posées

Qui a inventé le problème des huit dames ?

Max Bezzel, compositeur d’échecs allemand, en 1848. Franz Nauck a publié la première liste complète des solutions en 1850.

Combien y a-t-il de solutions ?

92 sur l’échiquier standard. Si l’on compte les rotations et les reflets comme une seule, il y en a 12.

Pourquoi l’échiquier 6×6 a-t-il si peu de solutions ?

Il n’en a que 4, toutes issues d’une seule famille. Le 5×5, plus petit, en a 10. Les échiquiers plus grands en ont de plus en plus : 40 sur 7×7 et 92 sur 8×8.

PictorX envoie-t-il quelque chose ?

Non. L’échiquier est dessiné sur un canevas dans votre navigateur. Enregistrer télécharge un PNG, et Modifier ouvre cette image dans l’éditeur PictorX.