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

Compruebe el jaque mate

Bienvenido bienvenido con otro problema por resolver! Si te gusta jugar al ajedrez y programar : ¡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.

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 aquí : ¡compruébalo y trata de resolver tu desafío diario también!
• 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.

Se le presenta una matriz de 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:

1. Estamos en un gráfico, no en un tablero: consideraremos cada punto dado por el problema como el centro de un caso en el tablero . El resultado es el mismo;
2. 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;
3. Necesitamos verificar si el rey está en jaque en este mismo turno , lo que significa que en el próximo turno de las blancas se tomará si no se mueve;
4. Las posiciones son dadas inicialmente por el juego : no entraré en la verificación de piezas superpuestas o posiciones iniciales incorrectas.

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 su próximo movimiento será capturar al rey negro . Por lo tanto, dado que también conocemos la posición del 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 . Si es así, durante el próximo turno de las blancas, la pieza blanca se moverá allí para capturar al rey negro.

La situación se parece a esto:
En la imagen de arriba puedes ver (…Eso espero, perdón por la confusión…) cada movimiento posible de cada pieza 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.

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 x,y que serán los próximos movimientos de nuestras piezas. Para hacer esto, primero definimos una clase para cada pieza, definimos sus coordenadas y luego 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 Python , ya que es uno de los lenguajes más populares en este momento y posiblemente el más legible para cualquiera. Aún así, necesitarás saber qué clase es para poder seguir a partir de ahora. Aquí está una explicación bastante clara de este concepto.

Expliquemos brevemente: primero definimos la class Pawn clase y __init__ sus coordenadas x,y . Después de eso, definimos el método possibleMoves 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 moves , después de verificar que no se mueve fuera de nuestra cuadrícula, y devolvemos la matriz moves . Dos cosas a tener en cuenta aquí, específicamente para el peón:

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

2. Nos saltamos intencionadamente el movimiento normal , 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.

   
   

Ahora podemos simplemente verificar los movimientos del peón dándole sus coordenadas y llamando al método possibleMoves , así: print(Pawn(7,2).possibleMoves()) y deberíamos obtener algo como [(6,3),(8,3)] .

Además, puede ver en la parte superior que definimos nuestras dimensiones de cuadrícula como variables , por lo que posiblemente podamos cambiarlas para ejecutar el algoritmo en tableros de otras dimensiones.

Ahora pasemos a la torre.

La Torre

Nuevamente, iniciamos la clase Torre con sus coordenadas y definimos la función possibleMoves . Para recopilar todos los movimientos posibles aquí , clasificamos todos los puntos en los dos ejes de la torre y agregamos cada coordenada individual a los moves variables, que se devolverán después de todos los bucles. Como antes, para verificar los movimientos de la torre, simplemente print(Tower(5,3).possibleMoves()) y deberíamos obtener algo como esto: [(1,3), (2,3), (3,3), ..., (5,8)] .

El obispo

Ahora es el turno del obispo.

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 , necesitamos recopilar puntos en los dos ejes diagonales a partir de su posición inicial . Después de declarar la clase y el método init, creamos dos variables: moves , como antes, y currentPos , 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 while , y verificando que no nos estamos moviendo fuera de nuestra cuadrícula, aumentamos y disminuimos x e y de acuerdo a donde queremos movernos . Por ejemplo, si queremos movernos hacia arriba a la izquierda desde sus posiciones iniciales, necesitaremos disminuir el valor de x mientras incrementamos el valor de y . Si queremos movernos hacia abajo a la derecha, necesitaremos incrementar el valor de x mientras disminuimos el valor de y y así sucesivamente. Finalmente, simplemente devolvemos moves una vez más.

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.

Muy bien, ¿qué está pasando aquí? Bueno, si lo pensamos bien, la dama tiene los mismos movimientos del alfil y la torre combinados . 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 possibleMoves como la 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 Bishop y Tower en la función possibleMoves , sus parámetros x e y se dan como self.x, self.y , por lo que en realidad son las coordenadas de las reinas.

El caballero

¡Ahora al caballero!

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, en realidad no necesitamos implementar su conjunto de movimientos . 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.

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!

Ahora simplemente creamos una variable blackKing como un par de coordenadas. Luego, para cada pieza, creamos una instancia de su clase que acabamos de crear y llamamos al método possibleMoves para calcular su conjunto completo de movimientos. Una vez que lo tenemos, comprobamos si las coordenadas del blackKing están presentes en esos conjuntos de movimientos : si lo están, imprimimos que el rey está controlado por esa pieza en particular. El resultado aquí es algo como esto:

 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 si el rey todavía tiene algunas posibilidades de sobrevivir o si en realidad está en jaque mate? Para este propósito, necesitamos calcular el conjunto de movimientos del rey.

Vamos a describirlo un poco. En primer lugar, definimos nuestra clase y coordenadas como antes. Después de eso, creamos el método possibleMoves 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, verificamos qué movimientos son ilegales (movimiento fuera del tablero) y devolvemos solo los validMoves .

Así que ahora, para comprobar si el rey aún tiene posibilidades de sobrevivir, tenemos que comprobar si alguno de sus posibles movimientos no está en otro conjunto de movimientos. Para hacer esto, simplemente hacemos un bucle sobre los movimientos del rey y los otros movimientos.

¡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 instancia de una clase , debemos considerar el tiempo para inicializar esa instancia.

• Piezas como el peón o el caballo no tienen ningún bucle en su interior y no dependen de ninguna dimensión variable, por lo que podemos considerarlas O(1);
• La torre 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 no importa dónde se coloque en el tablero, sus movimientos se limitan 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:

• Desafortunadamente, no podemos decir lo mismo del alfil , 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).

• La dama necesita el conjunto de movimientos de la torre y el alfil combinados. Ya que al evaluar la complejidad del tiempo debemos enfocarnos en el peor escenario , el tc del alfil prevalece sobre el tc de la torre. Así, debemos considerar un tc de O(n) también para la reina.

• Por fin, el rey tiene un conjunto de movimientos codificados, pero también un proceso de validación involucrado que usa un bucle for . 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.

  
  

En este punto, usamos un bucle for para cada pieza para verificar e imprimir el estado de verificación del rey negro . 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.

Finalmente, usamos un bucle for doble (interno) para verificar el jaque mate , que definitivamente será un tc de O(n²), dependiendo del número de movimientos del rey y los movimientos de las otras piezas.

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.