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

Vérifier l'échec et mat

Bienvenue bienvenue avec un autre problème à résoudre ! Si vous aimez jouer aux échecs et coder : 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.

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 ici : jetez-y un coup d'œil et essayez également de résoudre votre défi quotidien !
• 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.

On vous présente une matrice 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 :

1. On est sur un graphe, pas sur un plateau : on considérera chaque point donné par le problème comme le centre d'une case sur le plateau . Le résultat est le même;
2. 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 ;
3. Nous devons vérifier si le roi est en échec à ce tour précis , ce qui signifie qu'au prochain tour blanc, il sera pris s'il ne bouge pas ;
4. Les positions sont initialement données par le jeu : je n'entrerai pas dans la vérification des pièces qui se chevauchent ou des mauvaises positions de départ.

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 leur prochain coup sera celui de capturer le roi noir . Par conséquent, puisque nous connaissons également la position du roi noir, il nous suffit de vérifier si la position du roi noir est l'un des prochains coups possibles des autres pièces . Si c'est le cas, lors du prochain tour blanc, la pièce blanche s'y déplacera pour capturer le roi noir.

La situation ressemble à ceci :
Dans l'image ci-dessus, vous pouvez voir (… je l'espère, désolé pour la confusion…) tous les mouvements possibles de chaque pièce 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.

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 x,y qui seront nos prochains mouvements. Pour ce faire, nous définissons d'abord une classe pour chaque pièce, définissons ses coordonnées puis 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 Python , car c'est l'un des langages les plus populaires en ce moment et sans doute le plus lisible par quiconque. Néanmoins, vous aurez besoin de savoir ce qu'est une classe pour pouvoir suivre à partir de maintenant. Voici une explication assez soignée de ce concept.

Expliquons brièvement : nous définissons d'abord la class Pawn class et __init__ ses coordonnées x,y . Après cela, nous définissons la méthode possibleMoves pour calculer les mouvements possibles du pion à partir de là. Les mouvements de pion sont relativement faciles, nous les ajoutons donc simplement à la variable moves , après avoir vérifié qu'il ne sort pas de notre grille, et renvoyons le tableau moves . Deux choses à noter ici, spécifiquement pour le pion :

1. 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.

2. Nous sautons intentionnellement le mouvement normal , 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.

   
   

Maintenant, nous pouvons simplement vérifier les mouvements du pion en lui donnant ses coordonnées et en appelant la méthode possibleMoves , comme ceci : print(Pawn(7,2).possibleMoves()) et nous devrions obtenir quelque chose comme [(6,3),(8,3)] .

De plus, vous pouvez voir en haut que nous avons défini nos dimensions de grille en tant que variables , nous pouvons donc éventuellement les modifier pour exécuter l'algorithme sur des cartes d'autres dimensions.

Passons maintenant à la tour.

La tour

Encore une fois, nous initialisons la classe Tower avec ses coordonnées et définissons la fonction possibleMoves . Pour collecter tous les mouvements possibles ici , nous rangeons tous les points sur les deux axes de la tour et ajoutons chaque coordonnée unique aux moves 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 print(Tower(5,3).possibleMoves()) et nous devrions obtenir quelque chose comme ceci : [(1,3), (2,3), (3,3), ..., (5,8)] .

L'évêque

C'est maintenant au tour de l'évêque.

Les mouvements de Bishop sont plus complexes que la tour, nous pourrions donc expliquer un peu ce qui se passe ici. Fondamentalement, nous devons collecter des points sur les deux axes diagonaux à partir de sa position de départ . Après avoir déclaré la classe et la méthode init, nous créons deux variables : moves , comme précédemment, et currentPos , 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 while et en vérifiant que nous ne nous déplaçons pas en dehors de notre grille, nous augmentons et diminuons x et y en fonction de l'endroit où nous voulons nous déplacer . 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 x tout en incrémentant la valeur y . Si nous voulons descendre vers la droite, nous devrons incrémenter la valeur x tout en décrémentant la valeur y et ainsi de suite. Enfin, nous retournons simplement moves une fois de plus.

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.

D'accord, que se passe-t-il ici ? Eh bien, si nous y réfléchissons, la reine a les mêmes mouvements que le fou et la tour combinés . 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 possibleMoves comme le 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 Bishop et Tower dans la fonction possibleMoves , leurs paramètres x et y sont donnés sous la forme self.x, self.y , ce sont donc en fait les coordonnées des reines.

Le chevalier

Maintenant au chevalier !

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, nous n'avons pas vraiment besoin d'implémenter son move-set . 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.

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 !

Nous créons maintenant simplement une variable blackKing 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 possibleMoves pour calculer son ensemble complet de mouvements. Une fois que nous l'avons, nous vérifions si les coordonnées blackKing sont présentes dans ces ensembles de mouvements : 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 :

 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 si le roi a encore des chances de survivre ou s'il est en fait en échec et mat ? À cette fin, nous devons calculer l'ensemble de coups du roi.

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 possibleMoves 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, nous vérifions quels mouvements sont illégaux (déplacement en dehors du plateau) et renvoyons uniquement les validMoves .

Alors maintenant, pour vérifier si le roi a encore une chance de survivre, nous devons vérifier si l'un de ses mouvements possibles n'est pas dans un autre ensemble de mouvements. Pour ce faire, nous faisons simplement une boucle sur les mouvements du roi et les autres mouvements.

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 instance d'une classe , nous devons considérer le temps d'initialisation de cette instance.

• Des pièces comme le pion ou le cavalier 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) ;
• La tour 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 peu importe où elle est placée sur le plateau, ses mouvements sont limités 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 :

• Malheureusement, nous ne pouvons pas dire la même chose pour le fou , 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).

• La reine a besoin de l'ensemble des mouvements de la tour et du fou combinés. Étant donné que lors de l'évaluation de la complexité temporelle, nous devons nous concentrer sur le pire scénario , 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.

• Enfin, le roi dispose d'un ensemble de mouvements codés en dur, mais également d'un processus de validation impliqué qui utilise une boucle for . 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.

  
  

À ce stade, nous utilisons une boucle for pour chaque pièce afin de vérifier et d'imprimer l'état de vérification du roi noir . 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.

Enfin, nous utilisons une boucle for double (interne) pour vérifier le mat , qui va certainement être un tc de O(n²), en fonction du nombre de coups du roi et des coups des autres pièces.

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.