Comment fonctionne 8 reines

Selon les cercles dans lesquels vous évoluez – par exemple, votre meilleur ami est un programmeur informatique et votre sœur est une prodige des échecs – vous connaissez peut-être déjà le puzzle des 8 reines. Pour le reste d'entre nous, le puzzle des 8 reines (ou problème ou simplement « 8 reines ») n'est probablement pas quelque chose auquel nous passons beaucoup de temps à réfléchir.

Le puzzle est assez simple. Comment pouvez-vous placer 8 reines sur un échiquier pour qu'il n'y en ait pas deux qui s'attaquent ? Alternativement, la question est parfois formulée comme "Quel est le nombre maximum de reines qui peuvent être placées sur un échiquier, de sorte que deux ne puissent pas s'attaquer", mais ce puzzle devient beaucoup moins difficile lorsque vous Google cela, et le terme "le puzzle des 8 reines" apparaît.

Vous vous demandez peut-être pourquoi quelqu'un se soucie de l'endroit où vous gardez vos huit reines. Et oui, superficiellement, ce n'est qu'un casse-tête stratégique. Mais (et c'est là qu'il est pratique d'avoir un meilleur ami qui code des ordinateurs) le puzzle 8 Queens est un excellent moyen de tester le savoir-faire et l'alphabétisation d'un programmeur.

Maintenant, n'ayez pas peur. Vous ne serez pas obligé de comprendre les subtilités de la programmation informatique pour continuer à lire. Mais vous devez savoir que résoudre le puzzle peut être réalisé à l'aide d'un code de programmation - et certains sont plus élégants que d'autres. Par exemple, vous pouvez certainement trouver la solution en utilisant un programme de "force brute" qui pourrait simplement parcourir tous les emplacements possibles, en excluant un à la fois. Mais un codeur sophistiqué pourra construire un programme qui a des raccourcis en utilisant un algorithme plus raffiné pour vous trouver une solution plus rapidement. Être capable de trouver des façons inhabituelles ou originales de coder une solution à un problème aussi vaste que 8 Queens peut être un excellent test pour le savoir-faire d'un auteur de code.

Ainsi, même si nous ne vous enchaînerons pas de 1 et de 0 pour vous expliquer le fonctionnement de 8 Queens, nous vous donnerons quelques solutions au casse-tête.

Maintenant que nous comprenons la prémisse de base du puzzle, nous devons établir pourquoi le problème est si unique. Pour ce faire, révisons nos bases d'échecs. Dans une partie d'échecs, la reine est une force avec laquelle il faut compter. Elle peut se déplacer en ligne droite verticalement, horizontalement ou en diagonale, d'autant d'espaces qu'elle le souhaite. Le seul hic, c'est qu'elle ne peut pas sauter de pièces, donc si un pion se trouve sur son chemin, elle doit le capturer et s'arrêter.

C'est ce qui rend le puzzle des 8 reines intéressant. Si les reines peuvent se déplacer vers le haut, le bas, la gauche, la droite et en diagonale, alors combien de royals en guerre peuvent occuper le plateau sans partager la même ligne, colonne ou ligne diagonale ? Maintenant, vous pourriez penser que ce serait une excellente idée de simplement placer une reine sur le plateau, en essayant différentes combinaisons avant de les toucher toutes. Et bien sûr, c'est possible. Mais il existe 4 426 165 368 solutions potentielles, vous pouvez donc envisager de trouver un raccourci.

Avant de placer nos reines dans 4 milliards de carrés différents, reconnaissons d'abord que quelqu'un s'est assis un jour et a décidé que ce serait une bonne façon de perdre un après-midi ou deux. Comme on pouvait s'y attendre, ce n'était pas quelqu'un qui avait des rediffusions de "My Big Fat Gypsy Wedding" à rattraper – c'était un maître d'échecs et compositeur allemand du XIXe siècle nommé Max Bezzel. (Un compositeur d'échecs est quelqu'un qui crée des problèmes d'échecs - également appelés puzzles - à résoudre.) Il est apparu pour la première fois dans le magazine d'échecs allemand DieSchachzeitung en 1848.

Bezzel n'était pas si intéressé à résoudre le puzzle; il se contenta de poser simplement la question. Cependant, en 1850, le mathématicien Franz Nauck a écrit un autre article qui traitait du problème. (Les premières solutions au puzzle ont finalement été résolues par Nauck.) Cela a attiré l'attention de Karl Gauss, un mathématicien du XIXe siècle connu pour avoir découvert la théorie fondamentale de l'algèbre. Lorsque Gauss s'est intéressé à trouver la solution, d'autres ont suivi et différentes approches pour résoudre le puzzle ont commencé à émerger.

Il n'est pas vraiment surprenant que "huit" soit la réponse à notre question spécifique sur le nombre de reines qui peuvent être placées sur un plateau sans s'attaquer les unes les autres. Mais explorons de combien de façons huit reines peuvent être placées et comment cela est établi.

Nous avons parlé de la façon dont les programmes informatiques de force brute sont un moyen de résoudre le puzzle – et tester manuellement 4 426 165 368 possibilités serait certainement qualifié de force brute – mais il existe des moyens plus simples de réduire les solutions. Une méthode simplifiée a été fournie lorsque JWL Glaisher, un autre mathématicien, a publié un article en 1874 décrivant son utilisation des déterminants pour trouver une solution. "Déterminants" semble un peu difficile, mais tout ce que vous devez vraiment savoir, c'est que Glaisher a essentiellement construit une matrice et - en utilisant un système qu'il a dérivé de cette matrice - a pu réduire les solutions possibles à 92.

Et 92 solutions il reste. Mais ne soyez pas dupe; vous ne pourrez pas aligner 92 échiquiers, chacun avec un ensemble unique de 8 reines installées paisiblement, car il n'y a en fait que 12 solutions uniques.

Confus? La différence entre 12 solutions uniques et 92 solutions fondamentales repose, littéralement, sur la façon dont vous la regardez. Bien que vous puissiez configurer 12 planches différentes distinctement avec vos huit reines, il vous suffit simplement de tourner la planche - ou même de la refléter sur un miroir - pour que les planches aient techniquement un aspect différent et aient ainsi un "différent" Solution. (Ceci est appelé opérations de symétrie de rotation et de réflexion.) Vous prenez donc vos 12 planches uniques, vous les tournez de 90, 180 et 270 degrés, puis vous les réfléchissez à chaque rotation. Mais encore une chose - une planche unique est symétrique, elle a donc la même apparence sous deux angles. Alors que toutes les autres cartes ont huit variantes, la carte symétrique n'en a que quatre. Ainsi, au lieu de 12 planches multipliées par 8 variations (96), nous soustrayons en fait les quatre qui n'existent pas avec la planche symétrique. Qu'obtenons-nous ? 92 solutions fondamentales.

Maintenant, ne laissez pas les maths vous tromper. Vous pouvez toujours vous trouver un échiquier et tenter de dénicher quelques placements par vous-même. (Trouver une réponse, bien sûr, est beaucoup plus facile que de trouver les 12.) Et il existe même des programmes sur le Web qui vous permettent de trouver différentes solutions. (Attention : ils peuvent vous faire sentir stupide.)

Avant de mélanger vos reines, consultez la page suivante pour en savoir plus.

Étant une personne moins intéressée par un algorithme qu'un alphabet, je n'avais pas de grands espoirs pour comprendre le puzzle des 8 reines. Bien que j'étais sûr qu'il avait une sorte d'application pratique, je n'étais pas capable de le voir. Ironiquement, c'est quand j'ai compris l'immensité du problème que j'ai commencé à voir pourquoi cela pouvait être utile. Trouver un ensemble de solutions à partir d'une quantité massive de possibilités est l'une des raisons pour lesquelles le code existe. Le problème des 8 reines met au défi les programmeurs et les mathématiciens de découvrir de nouvelles techniques pour simplifier la recherche.

Liens connexes

Sources