Compruebe el jaque mate Bienvenido bienvenido con otro problema por resolver! Si te gusta jugar al ajedrez y : ¡este es para ti! Hoy ayudaremos al rey a sobrevivir un día más en el campo de batalla, también escribiendo un montón de código bastante grande. programar Entonces, sin más preámbulos, veamos nuestro problema. Sin embargo, antes de comenzar, como siempre, dos descargos de responsabilidad: Estos problemas son proporcionados por el maravilloso boletín Daily Coding Problem, al que puede suscribirse : ¡compruébalo y trata de resolver tu desafío diario también! aquí No soy un programador experto, solo un tipo al que le gusta compartir sus intentos (y fracasos). Si tienes una mejor idea o solución, eres más que bienvenido a compartirla: ¡me encantaría verte abordarla! El problema Oracle planteó inicialmente el problema de hoy. matriz de Se le presenta una 8 por 8 que representa las posiciones de las piezas en un tablero de ajedrez. Las únicas piezas en el tablero son el rey negro y varias piezas blancas. Dada esta matriz, determina si el rey está en jaque. Para obtener detalles sobre cómo se mueve cada pieza, consulte aquí . Por ejemplo, dada la siguiente matriz: ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q.. Debería devolver True , ya que el alfil está atacando al rey en diagonal. El problema es bastante claro, por lo que no daremos más detalles al respecto. Sin embargo, solo necesitamos algunas especificaciones iniciales: Estamos en un gráfico, no en un tablero: . El resultado es el mismo; consideraremos cada punto dado por el problema como el centro de un caso en el tablero El rey blanco se ha ido de vacaciones con otros 7 peones: el rey y los peones son las piezas más aburridas de todas y quitarlas no va a cambiar mucho nuestra solución; Necesitamos , lo que significa que en el próximo turno de las blancas se tomará si no se mueve; verificar si el rey está en jaque en este mismo turno : no entraré en la verificación de piezas superpuestas o posiciones iniciales incorrectas. Las posiciones son dadas inicialmente por el juego La solución En primer lugar, un resumen rápido de piezas y conjuntos de movimientos: Dada la posición inicial de cada pieza y su conjunto de movimientos, podemos . calcular "fácilmente" todos los próximos movimientos posibles de cada pieza Y dado que todos están interesados en capturar al rey lo más rápido posible, podemos suponer que . Por lo tanto, dado que también conocemos la posición del rey negro, . Si es así, durante el próximo turno de las blancas, la pieza blanca se moverá allí para capturar al rey negro. su próximo movimiento será capturar al rey negro solo tenemos que comprobar si la posición del rey negro es uno de los posibles próximos movimientos de las otras piezas La situación se parece a esto: En la imagen de arriba puedes ver (…Eso espero, perdón por la confusión…) en el lado blanco, coloreado con diferentes colores, y el rey negro arriba esperando ser capturado. Entonces, por ejemplo, el alfil, comenzando en (2,7), puede moverse a (1,6), (1,8), (3,8), (3,6), (4,5), (5, 4) y así sucesivamente. cada movimiento posible de cada pieza Decidí al azar las posiciones iniciales de estas piezas ya que esto no afecta el resultado final. Como estamos en un gráfico de 8x8 (para ser claros, cualquier otra dimensión funcionará de la misma manera) y tenemos las coordenadas iniciales de cada pieza, podemos construir una serie de coordenadas que serán los próximos movimientos de nuestras piezas. Para hacer esto, primero definimos una definimos sus coordenadas y luego x,y clase para cada pieza, definimos las reglas para calcular todos los movimientos posibles a partir de ahí. Las piezas — El peón Comencemos de manera simple con el Peón. Por cierto, estoy construyendo esto en , ya que es uno de los lenguajes más populares en este momento y posiblemente el más legible para cualquiera. Aún así, para poder seguir a partir de ahora. una explicación bastante clara de este concepto. Python necesitarás saber qué clase es Aquí está https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py Expliquemos brevemente: primero definimos la clase y sus coordenadas . Después de eso, definimos el método para calcular las jugadas posibles del peón a partir de ahí. Los movimientos de peón son relativamente fáciles, así que simplemente los agregamos a la variable , después de verificar que no se mueve fuera de nuestra cuadrícula, y devolvemos la matriz . Dos cosas a tener en cuenta aquí, específicamente para el peón: class Pawn __init__ x,y possibleMoves moves moves Consideramos que el peón blanco se mueve de abajo hacia arriba, como si fuéramos el jugador blanco moviendo nuestro peón hacia nuestro oponente. Esto realmente no cambia nada, solo mantiene las cosas en orden. Nos , ya que nos interesa capturar el rey negro: dado que el peón solo puede capturar en diagonal y no nos importa mover las piezas en otras direcciones, podemos saltarnos su movimiento normal. saltamos intencionadamente el movimiento normal Ahora podemos simplemente verificar los movimientos del peón dándole sus coordenadas y llamando al método , así: y deberíamos obtener algo como . possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] Además, puede ver en la parte superior que , por lo que posiblemente podamos cambiarlas para ejecutar el algoritmo en tableros de otras dimensiones. definimos nuestras dimensiones de cuadrícula como variables Ahora pasemos a la torre. La Torre https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py Nuevamente, iniciamos la clase Torre con sus coordenadas y definimos la función . Para recopilar todos los movimientos posibles aquí variables, que se devolverán después de todos los bucles. Como antes, para verificar los movimientos de la torre, simplemente y deberíamos obtener algo como esto: . possibleMoves , clasificamos todos los puntos en los dos ejes de la torre y agregamos cada coordenada individual a los moves print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)] El obispo Ahora es el turno del obispo. https://gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py Los movimientos de Bishop son más complejos que los de la torre, así que podríamos explicar un poco lo que está pasando aquí. Básicamente . Después de declarar la clase y el método init, creamos dos variables: , como antes, y , que se usarán para realizar un seguimiento de los puntos que recolectamos mientras nos movíamos a lo largo de sus ejes. Ahora, usando el ciclo , y verificando que no nos estamos moviendo fuera de nuestra cuadrícula, e . Por ejemplo, si queremos movernos hacia arriba a la izquierda desde sus posiciones iniciales, necesitaremos disminuir el valor de mientras incrementamos el valor de . Si queremos movernos hacia abajo a la derecha, necesitaremos incrementar el valor de mientras disminuimos el valor de y así sucesivamente. Finalmente, simplemente devolvemos una vez más. , necesitamos recopilar puntos en los dos ejes diagonales a partir de su posición inicial moves currentPos while aumentamos y disminuimos x y de acuerdo a donde queremos movernos x y x y moves La reina Ahora podrías pensar: si los movimientos de la torre son complejos y el alfil lo es aún más, ¿cómo diablos vamos a codificar la dama? En realidad, los movimientos de la dama son los más fáciles de codificar, solo con la ayuda de un truco simple. Veamos a la reina entonces. https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py Muy bien, ¿qué está pasando aquí? Bueno, si lo pensamos bien, . Se parece más a un robot mecánico de obispo en forma de torre que a una reina. Por esta razón, codificar sus movimientos es realmente simple. Después de declarar su clase, simplemente definimos sus como la . la dama tiene los mismos movimientos del alfil y la torre combinados possibleMoves matriz de unión de los movimientos resultantes de los posibles movimientos del alfil y la torre Tenga en cuenta que al llamar a las instancias de las clases y en la función , sus parámetros e se dan como , por lo que en realidad son las coordenadas de las reinas. Bishop Tower possibleMoves x y self.x, self.y El caballero ¡Ahora al caballero! https://gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py El caballero es el más particular para mí. Su conjunto de movimientos es extraño, como en forma de "L", por lo que no encontré una forma particularmente inteligente o rápida de codificarlo y terminé codificando sus movimientos simplemente calculando . cada uno de los 8 movimientos posibles que tiene desde su posición inicial El rey Un par de breves conceptos sobre el rey. Dado que no estamos obligados a mover al rey, solo informamos si está marcado o no, . Sin embargo, también veremos una breve implementación al final del artículo. Además, codificarlo no es tan simple como debilitar el conjunto de movimientos de la reina, como veremos más adelante. Entonces, por ahora, saltemos sus movimientos y veamos la solución. en realidad no necesitamos implementar su conjunto de movimientos El código de la solución Dado que tenemos las posiciones posibles para cada pieza, la solución ahora es bastante simple: solo necesitamos verificar si las coordenadas del rey negro están en el conjunto de movimientos de una o más de las otras piezas. ¡Vamos a codificarlo! https://gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py Ahora simplemente creamos una variable como un par de coordenadas. Luego, para cada pieza, creamos una instancia de su clase que acabamos de crear y llamamos al método para calcular su conjunto completo de movimientos. coordenadas del : si lo están, imprimimos que el rey está controlado por esa pieza en particular. El resultado aquí es algo como esto: blackKing possibleMoves Una vez que lo tenemos, comprobamos si las blackKing están presentes en esos conjuntos de movimientos 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! Utilicé la imagen desordenada de arriba como referencia, para que puedas comprobar que el rey está controlado por la torre y el caballero. jaque mate ¿Qué pasa si también queremos calcular o si en realidad está en jaque mate? Para este propósito, necesitamos calcular el conjunto de movimientos del rey. si el rey todavía tiene algunas posibilidades de sobrevivir https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py Vamos a describirlo un poco. En primer lugar, definimos nuestra clase y coordenadas como antes. Después de eso, creamos el método y codificamos las jugadas posibles del rey (de nuevo, estoy bastante seguro de que hay una forma más rápida, pero solo hay 8 jugadas posibles, así que...). Después de eso, y devolvemos solo los . possibleMoves verificamos qué movimientos son ilegales (movimiento fuera del tablero) validMoves Así que ahora, para comprobar si el rey aún tiene posibilidades de sobrevivir, Para hacer esto, simplemente hacemos un bucle sobre los movimientos del rey y los otros movimientos. tenemos que comprobar si alguno de sus posibles movimientos no está en otro conjunto de movimientos. https://gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py ¡Así que todavía hay esperanza de que nuestro rey sobreviva! Por suerte para él, supongo… Complejidad del tiempo Como siempre, una breve mirada a la complejidad temporal de esta solución. En primer lugar, dado que cada pieza es una , debemos considerar el tiempo para inicializar esa instancia. instancia de una clase Piezas como el no tienen ningún bucle en su interior y no dependen de ninguna dimensión variable, por lo que podemos considerarlas O(1); peón o el caballo La es un poco complicada: dado que contiene 4 bucles for, podría pensar instantáneamente que su complejidad de tiempo es O (n), ¿verdad? En realidad, si pensamos en cómo se mueve la torre, notaremos que a los casos libres del tablero en sus ejes vertical y horizontal. Y como el tablero es un cuadrado, siempre tendremos 14 cajas libres para mover nuestra torre. Entonces, su complejidad de tiempo debería ser O(1), constante a 14 pares de coordenadas. He aquí un ejemplo gráfico: torre no importa dónde se coloque en el tablero, sus movimientos se limitan Desafortunadamente, no podemos decir lo mismo del , cuyo conjunto de movimientos parece ser un poco más complejo. Básicamente, tiene 7, 9, 11 o 13 movimientos dependiendo de dónde se coloque en el tablero. Por lo tanto, los pasos necesarios para calcular su conjunto de movimientos se basan en su posición, por lo que podemos considerar un tc de O(n). alfil La necesita el conjunto de movimientos de la torre y el alfil combinados. Ya que , el tc del alfil prevalece sobre el tc de la torre. Así, debemos considerar un tc de O(n) también para la reina. dama al evaluar la complejidad del tiempo debemos enfocarnos en el peor escenario Por fin, el tiene un conjunto de movimientos codificados, pero también un . Entonces, técnicamente, incluso si el conjunto de movimientos del rey es relativamente pequeño en cualquier caso, debemos considerar su tc como O(n), también dependiendo de su posición en el tablero. rey proceso de validación involucrado que usa un bucle for En este punto, usamos . Esto no nos da problemas donde el tc es constante (tome la torre, por ejemplo: calculamos sus 14 movimientos y luego giramos otras 14 veces sobre ellos como máximo, por lo que podemos considerarlo también como tiempo fijo). Aún así, vamos a tener problemas donde el tc es O(n) o superior, ya que estamos agregando un bucle que también crecerá a medida que crezca el número de movimientos. un bucle for para cada pieza para verificar e imprimir el estado de verificación del rey negro Finalmente, , que definitivamente será un tc de O(n²), dependiendo del número de movimientos del rey y los movimientos de las otras piezas. usamos un bucle for doble (interno) para verificar el jaque mate Eso es todo; ahí está mi solución. Soy muy consciente de que algunos puntos no son lo más eficientes posible, pero mientras escribía me gustó más la idea de describir el proceso que construir la solución perfecta. ¿Qué piensas sobre esto? ¡Dame tu opinión al respecto y discutamos tus soluciones en los comentarios! Como siempre, si te ha gustado el artículo, deja un par de aplausos y suscríbete, o compártelo con alguien que pueda estar interesado en este tipo de algoritmos, ¡si puedes! ¡Gracias por leer hasta el final, esta vez más que siempre dada la longitud de esta solución! Como siempre, gracias por leer.

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.

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Making security fun one episode at a time

Problema diario de codificación: use sus habilidades de codificación para verificar el jaque mate

Demasiado Largo; Para Leer

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

ETIQUETAS

Languages

ESTE ARTÍCULO FUE PRESENTADO EN...

Problema diario de codificación: use sus habilidades de codificación para verificar el jaque mate

Demasiado Largo; Para Leer

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

ETIQUETAS

Languages

ESTE ARTÍCULO FUE PRESENTADO EN...

HISTORIAS RELACIONADAS