Vous avez déjà joué aux échecs ? Si oui, vous savez déjà que la reine est la pièce la plus importante et qu’elle peut se déplacer d’un nombre quelconque de cases verticalement, horizontalement ou en diagonale. Si ce n’est pas le cas, ne vous inquiétez pas : aujourd’hui, nous allons seulement apprendre à placer 8 reines sur l’échiquier de façon à ce qu’aucune reine ne puisse se déplacer sur une case occupée par une autre reine. Dans le jargon échiquéen, on dit que les reines ne pourront pas s’attaquer entre elles. Comment faisons-nous cela ? Nous utilisons le backtracking.
L’algorithme de backtracking trouve une solution aux problèmes dans lesquels certaines contraintes doivent être respectées. Il teste toutes les solutions possibles jusqu’à ce qu’il trouve la bonne. Essayons un exemple, avec quatre reines et un petit plateau. Nous allons commencer par placer la première reine:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Il vous montrera également de nombreuses autres stratégies de calcul qui vous aideront à résoudre des problèmes intéressants !
Maintenant que vous savez comment fonctionne le backtracking, nous pouvons résoudre le problème des 8 reines en taille réelle. Ci-dessous, il y a un échiquier avec lequel vous pouvez jouer pour pratiquer vos compétenceset trouver une solution. Commencez par placer la première reine en cliquant sur la case supérieure gauche de l’échiquier. Vous verrez que la reine que vous avez placée sera répertoriée dans la liste des « Reines actuelles ».
Reines actuelles
Vous pouvez maintenant placer une autre reine dans une position qui les empêchera de s’attaquer mutuellement. Notre première reine est en a8, la seconde, par exemple, peut être placée en c7. Continuez à placer des dames jusqu’à ce qu’il ne reste plus aucune case sûre sur l’échiquier. À ce moment-là, il est temps de revenir en arrière en cliquant sur « undo ». Cela effacera la dernière dame que vous avez placée et vous permettra de choisir une autre case pour la placer. Vous pouvez également retirer une reine de l’échiquier en cliquant directement dessus.
En jouant à ce jeu interactif, vous pouvez commencer à avoir une idée du retour en arrière. En tant qu’humains, il peut devenir difficile pour nous de garder la trace de tous les placements de reine précédents. C’est là que la programmation nous aide ! Ci-dessous, vous trouverez une animation générée par un programme démontrant ses compétences irréprochables en matière de backtracking:
Pseudocode:
- Débutez en plaçant la première reine sur la case supérieure gauche de l’échiquier.
- Si nous avons placé les 8 reines, nous avons terminé. Sinon, est-il possible de placer une autre reine dans une position sûre ?
- Si oui, alors marquez cela comme faisant partie de la solution, et retournez au point 2.
- Si non, alors changez la position de la reine précédente (retour en arrière) et retournez au point 2.
.