Vérifier l'échec et mat Bienvenue bienvenue avec un autre problème à résoudre ! Si vous aimez jouer aux échecs et : celui-ci est pour vous ! Aujourd'hui, nous allons aider le roi à survivre un autre jour sur le champ de bataille, en écrivant également un assez gros tas de code. coder Alors sans plus tarder, voyons notre problème. Avant de commencer, comme toujours, deux avis de non-responsabilité : Ces problèmes sont fournis par la merveilleuse newsletter Daily Coding Problem, à laquelle vous pouvez vous abonner : jetez-y un coup d'œil et essayez également de résoudre votre défi quotidien ! ici Je ne suis pas un programmeur expert, juste un gars qui aime partager ses tentatives (et ses échecs). Si vous avez une meilleure idée ou une meilleure solution, vous êtes plus que bienvenu pour la partager : j'aimerais beaucoup vous voir l'aborder ! Le problème Le problème d'aujourd'hui a été initialement posé par Oracle. matrice On vous présente une 8 par 8 représentant les positions des pièces sur un échiquier. Les seules pièces sur le plateau sont le roi noir et diverses pièces blanches. Compte tenu de cette matrice, déterminez si le roi est en échec. Pour plus de détails sur la façon dont chaque pièce se déplace, voir ici . Par exemple, étant donné la matrice suivante : ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q.. Vous devez renvoyer True , puisque le fou attaque le roi en diagonale. Le problème est assez clair, nous n'allons donc pas en dire plus. Nous avons juste besoin de quelques spécifications de départ : On est sur un graphe, pas sur un plateau : . Le résultat est le même; on considérera chaque point donné par le problème comme le centre d'une case sur le plateau Le roi blanc est parti en vacances avec 7 autres pions : le roi et les pions sont les plus ennuyeux de toutes les pièces et les retirer ne changera pas grand-chose à notre solution ; Nous devons , ce qui signifie qu'au prochain tour blanc, il sera pris s'il ne bouge pas ; vérifier si le roi est en échec à ce tour précis : je n'entrerai pas dans la vérification des pièces qui se chevauchent ou des mauvaises positions de départ. Les positions sont initialement données par le jeu La solution Tout d'abord, un petit récapitulatif des pièces et des move-sets : Compte tenu de la position de départ de chaque pièce et de son ensemble de coups, nous pouvons "facilement" . calculer chaque prochain coup possible de chaque pièce Et puisqu'ils sont tous intéressés à capturer le roi le plus rapidement possible, on peut supposer que . Par conséquent, puisque nous connaissons également la position du roi noir, il nous . Si c'est le cas, lors du prochain tour blanc, la pièce blanche s'y déplacera pour capturer le roi noir. leur prochain coup sera celui de capturer le roi noir suffit de vérifier si la position du roi noir est l'un des prochains coups possibles des autres pièces La situation ressemble à ceci : Dans l'image ci-dessus, vous pouvez voir (… je l'espère, désolé pour la confusion…) du côté blanc, colorés de différentes couleurs, et le roi noir au-dessus attendant d'être capturé. Ainsi, par exemple, le fou, commençant en (2,7), peut se déplacer en (1,6), (1,8), (3,8), (3,6), (4,5), (5, 4) et ainsi de suite. tous les mouvements possibles de chaque pièce J'ai juste décidé au hasard des positions de départ de ces pièces car cela n'affecte pas le résultat final. Puisque nous sommes sur un graphique 8x8 (pour être clair, toutes les autres dimensions fonctionneront de la même manière) et que nous avons les coordonnées de départ de chaque pièce, nous pouvons construire des séries de coordonnées qui seront nos prochains mouvements. Pour ce faire, nous définissons d'abord une définissons ses coordonnées puis x,y classe pour chaque pièce, définissons les règles pour calculer chaque mouvement possible à partir de là. Les pièces — Le Pion Commençons simplement avec le Pion. Au fait, je construis ceci en , car c'est l'un des langages les plus populaires en ce moment et sans doute le plus lisible par quiconque. Néanmoins, pour pouvoir suivre à partir de maintenant. une explication assez soignée de ce concept. Python vous aurez besoin de savoir ce qu'est une classe Voici https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py Expliquons brièvement : nous définissons d'abord la class et ses coordonnées . Après cela, nous définissons la méthode pour calculer les mouvements possibles du pion à partir de là. Les mouvements de pion sont relativement faciles, nous les ajoutons donc simplement à la variable , après avoir vérifié qu'il ne sort pas de notre grille, et renvoyons le tableau . Deux choses à noter ici, spécifiquement pour le pion : class Pawn __init__ x,y possibleMoves moves moves Nous considérons que le pion blanc se déplace de bas en haut, comme si nous étions le joueur blanc déplaçant notre pion vers notre adversaire. Cela ne change vraiment rien, c'est juste garder les choses en ordre. Nous , puisque nous sommes intéressés à capturer le roi noir : puisque le pion ne peut capturer qu'en diagonale et que nous ne nous soucions pas de déplacer les pièces dans d'autres directions, nous pouvons sauter son mouvement normal. sautons intentionnellement le mouvement normal Maintenant, nous pouvons simplement vérifier les mouvements du pion en lui donnant ses coordonnées et en appelant la méthode , comme ceci : et nous devrions obtenir quelque chose comme . possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] De plus, vous pouvez voir en haut que , nous pouvons donc éventuellement les modifier pour exécuter l'algorithme sur des cartes d'autres dimensions. nous avons défini nos dimensions de grille en tant que variables Passons maintenant à la tour. La tour https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py Encore une fois, nous initialisons la classe Tower avec ses coordonnées et définissons la fonction . Pour collecter tous les mouvements possibles ici variables , qui seront renvoyés après toutes les boucles. Comme précédemment, pour vérifier les mouvements de la tour, nous pouvons simplement et nous devrions obtenir quelque chose comme ceci : . possibleMoves , nous rangeons tous les points sur les deux axes de la tour et ajoutons chaque coordonnée unique aux moves print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)] L'évêque C'est maintenant au tour de l'évêque. https://gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py Les mouvements de Bishop sont plus complexes que la tour, nous pourrions donc expliquer un peu ce qui se passe ici. Fondamentalement, . Après avoir déclaré la classe et la méthode init, nous créons deux variables : , comme précédemment, et , qui seront utilisées pour garder une trace des points que nous avons collectés en nous déplaçant le long de ses axes. Maintenant, en utilisant la boucle et en vérifiant que nous ne nous déplaçons pas en dehors de notre grille, nous et . Par exemple, si nous voulons nous déplacer vers le haut à gauche de ses positions de départ, nous devrons décrémenter la valeur tout en incrémentant la valeur . Si nous voulons descendre vers la droite, nous devrons incrémenter la valeur tout en décrémentant la valeur et ainsi de suite. Enfin, nous retournons simplement une fois de plus. nous devons collecter des points sur les deux axes diagonaux à partir de sa position de départ moves currentPos while augmentons et diminuons x y en fonction de l'endroit où nous voulons nous déplacer x y x y moves La reine Maintenant, vous pourriez penser : si les mouvements de tour sont complexes et le fou encore plus, comment diable allons-nous coder la reine ? En fait, les mouvements de reine sont les plus faciles à coder, juste à l'aide d'une astuce simple. Voyons la reine alors. https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py D'accord, que se passe-t-il ici ? Eh bien, si nous y réfléchissons, . Elle ressemble plus à un mecha-bot évêque en forme de tour qu'à une reine. Pour cette raison, coder ses mouvements est vraiment simple. Après avoir déclaré sa classe, nous définissons simplement ses comme le . la reine a les mêmes mouvements que le fou et la tour combinés possibleMoves tableau d'union des mouvements résultant des mouvements possibles de l'évêque et de la tour Notez que lors de l'appel des instances des classes et dans la fonction , leurs paramètres et sont donnés sous la forme , ce sont donc en fait les coordonnées des reines. Bishop Tower possibleMoves x y self.x, self.y Le chevalier Maintenant au chevalier ! https://gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py Le chevalier est le plus particulier pour moi. Son ensemble de mouvements est étrange, comme en forme de "L", donc je n'ai pas trouvé de moyen particulièrement intelligent ou rapide de le coder et j'ai fini par coder en dur ses mouvements en calculant simplement . chacun des 8 mouvements possibles qu'il a depuis sa position de départ Le roi Quelques brèves notions sur le roi. Puisque nous ne sommes pas obligés de déplacer le roi, juste de dire s'il est vérifié ou non, . Cependant, nous verrons également une brève implémentation à la fin de l'article. De plus, le coder n'est pas aussi simple que de nerfer l'ensemble de mouvements de la reine, comme nous le verrons plus tard. Donc pour l'instant, sautons ses mouvements et voyons la solution. nous n'avons pas vraiment besoin d'implémenter son move-set Le code des solutions Étant donné que nous avons les positions possibles pour chaque pièce, la solution est assez simple maintenant : il suffit de vérifier si les coordonnées du roi noir sont dans l'ensemble des mouvements d'une ou plusieurs des autres pièces. Codons-le ! https://gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py Nous créons maintenant simplement une variable sous la forme d'un couple de coordonnées. Ensuite, pour chaque pièce, nous créons une instance de sa classe que nous venons de construire et appelons la méthode pour calculer son ensemble complet de mouvements. coordonnées : si elles le sont, nous affichons que le roi est vérifié par cette pièce particulière. Le résultat ici est quelque chose comme ça : blackKing possibleMoves Une fois que nous l'avons, nous vérifions si les blackKing sont présentes dans ces ensembles de mouvements Pawn moves: [(8, 3), (6, 3)] Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)] Check by the tower! Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)] Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)] Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)] Check by the knight! J'ai utilisé l'image désordonnée ci-dessus comme référence, afin que vous puissiez vérifier que le roi est bien contrôlé par la tour et le chevalier. Échec et mat Qu'en est-il si nous voulons également calculer ou s'il est en fait en échec et mat ? À cette fin, nous devons calculer l'ensemble de coups du roi. si le roi a encore des chances de survivre https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py Décrivons-le un peu. Tout d'abord, nous définissons notre classe et nos coordonnées comme précédemment. Après cela, nous créons la méthode et codons les mouvements possibles du roi (encore une fois, je suis presque sûr qu'il existe un moyen plus rapide, mais il n'y a que 8 mouvements possibles donc…). Après cela, et renvoyons uniquement les . possibleMoves nous vérifions quels mouvements sont illégaux (déplacement en dehors du plateau) validMoves Alors maintenant, pour vérifier si le roi a encore une chance de survivre, Pour ce faire, nous faisons simplement une boucle sur les mouvements du roi et les autres mouvements. nous devons vérifier si l'un de ses mouvements possibles n'est pas dans un autre ensemble de mouvements. https://gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py Il y a donc encore de l'espoir pour notre roi de survivre ! Heureusement pour lui je suppose… Complexité temporelle Comme toujours, un bref aperçu de la complexité temporelle de cette solution. Tout d'abord, puisque chaque morceau est une , nous devons considérer le temps d'initialisation de cette instance. instance d'une classe Des pièces comme le n'ont pas de boucle à l'intérieur et ne dépendent d'aucune dimension variable, on peut donc les considérer comme O(1) ; pion ou le cavalier La est un peu délicate : puisqu'elle contient 4 boucles for, vous pourriez instantanément penser que sa complexité temporelle est O(n), n'est-ce pas ? En fait, si nous réfléchissons à la façon dont la tour se déplace, nous remarquerons que aux cas de planche libre sur ses axes verticaux et horizontaux. Et comme le plateau est un carré, nous aurons toujours 14 caisses libres pour déplacer notre tour. Donc sa complexité temporelle devrait en fait être O(1), constante à 14 couples de coordonnées. Voici un exemple graphique : tour peu importe où elle est placée sur le plateau, ses mouvements sont limités Malheureusement, nous ne pouvons pas dire la même chose pour le , dont l'ensemble de mouvements semble être un peu plus complexe. Fondamentalement, il a 7, 9, 11 ou 13 coups selon l'endroit où il est placé sur le plateau. Par conséquent, les étapes nécessaires pour calculer son ensemble de mouvements sont basées sur sa position, nous pouvons donc considérer un tc de O(n). fou La a besoin de l'ensemble des mouvements de la tour et du fou combinés. Étant donné que , le tc de l'évêque prévaut sur le tc de la tour. Ainsi, nous devons considérer un tc de O(n) également pour la reine. reine lors de l'évaluation de la complexité temporelle, nous devons nous concentrer sur le pire scénario Enfin, le dispose d'un ensemble de mouvements codés en dur, mais également d'un . Donc techniquement, même si l'ensemble de coups du roi est relativement petit dans tous les cas, nous devons considérer son tc comme O(n), également en fonction de sa position sur l'échiquier. roi processus de validation impliqué qui utilise une boucle for À ce stade, nous utilisons . Cela ne nous pose aucun problème lorsque le tc est constant (prenons la tour, par exemple : nous calculons ses 14 coups, puis nous les parcourons 14 autres fois au maximum, nous pouvons donc la considérer également comme un temps fixe). Pourtant, nous allons avoir des problèmes lorsque le tc est O(n) ou supérieur, car nous ajoutons une boucle qui augmentera également à mesure que le nombre de mouvements augmentera. une boucle for pour chaque pièce afin de vérifier et d'imprimer l'état de vérification du roi noir Enfin, , qui va certainement être un tc de O(n²), en fonction du nombre de coups du roi et des coups des autres pièces. nous utilisons une boucle for double (interne) pour vérifier le mat C'est ça; voilà ma solution. Je suis bien conscient que certains points ne sont pas aussi efficaces que possible, mais en écrivant, j'aimais davantage l'idée de décrire le processus que de construire la solution parfaite. Que penses-tu de cela? Donnez-moi votre avis à ce sujet et discutons de vos solutions dans les commentaires ! Comme toujours, si vous avez aimé l'article, merci de laisser un applaudissement ou deux et de vous abonner, ou de le partager avec quelqu'un qui pourrait être intéressé par ce genre d'algorithmes, si vous le pouvez ! Merci d'avoir lu jusqu'au bout, cette fois plus que toujours vu la longueur de cette solution ! Comme toujours, merci d'avoir lu.

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Cet audio est produit dans la langue originale de l'histoire !

Trop long; Pour lire

Making security fun one episode at a time

Problème de codage quotidien : utilisez vos compétences en codage pour vérifier l'échec et mat

Trop long; Pour lire

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

ÉTIQUETTES

Languages

CET ARTICLE A ÉTÉ PARU DANS...

Problème de codage quotidien : utilisez vos compétences en codage pour vérifier l'échec et mat

Trop long; Pour lire

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

ÉTIQUETTES

Languages

CET ARTICLE A ÉTÉ PARU DANS...

HISTOIRES CONNEXES