¿Sabía que…

…el problema de las ocho reinas puede resolverse a partir del problema de las ocho torres y el problema de los ocho alfiles?

Vamos a explicar un poco el asunto. El llamado problema de las ocho reinas (que ya se comentó en este post) consiste en colocar en un tablero de ajedrez ocho reinas de forma que ninguna amenace a otra (vamos, que ninguna pueda comerse a otra). Se conoce que hay 92 soluciones de las que, eliminando simetrías, rotaciones y traslaciones, 12 de ellas son esencialmente distintas. En este artículo de la Wikipedia (en español) podéis ver esas 12 soluciones.

El problema de las torres es exactamente igual que el anterior pero con torres. Es decir: colocar ocho torres en un tablero de ajedrez de forma que ninguna amenace a otra. Éste es mucho más sencillo ya que, teniendo en cuenta el movimiento de la torre (horizontal y vertical), para encontrar una solución simplemente tenemos que colocar cada torre en una fila y una columna distinta.

Vamos a ponerle números al asunto:

Supongamos que tenemos un tablero de ajedrez:

Tablero de ajedrez

(La imagen la he tomado de Kalipedia)

Tomando las columnas como referencia asignaremos un número a cada torre en función de la posición que ocupa en esa columna contando de abajo a arriba. Es decir, el número 36641234 nos dice que la torre de la columna 1 está colocada en la posición 3 de esa columna, la de la 2 en la posición 6, … , la de la columna 5 en la posición 1 de esa columna, y así sucesivamente.

Con esta notación es claro que las soluciones del problema de las torres salen de todas las permutaciones de los números 1, 2, 3, 4, 5, 6, 7 y 8, es decir, todos los números de ocho cifras con todas las cifras distintas que no contengan ningún cero, ya que así conseguimos que ninguna pareja de torres estén en la misma columna o en la misma fila y por tanto evitamos que alguna de ellas pueda comerse a otra.

Teniendo en cuenta el movimiento de la reina (horizontal, vertical y diagonal) es evidente que las soluciones del problema de las ocho reinas podemos obtenerlas a partir de las soluciones del problema de las ocho torres. Solamente habría que desechar las soluciones de las ocho torres en las que algún par de ellas esté en la misma diagonal. Si formulamos un problema de este tipo para alfiles (pieza que mueve en diagonal) es fácil ver que las soluciones del problema de las ocho reinas son las soluciones del problema de las ocho torres que también son solución del problema de los ocho alfiles.

¿Cómo describir numéricamente el problema de los ocho alfiles? Pues muy sencillo: para que dos alfiles colocados en el tablero no se amenacen necesitamos que no estén en la misma diagonal. Eso lo conseguimos imponiendo que la diferencia (en valor absoluto) entre los números que indican la columna de cada uno de ellos sea distinta de la diferencia entre los números que indican la fila de los mismos. Un ejemplo:

Supongamos que tenemos dos alfiles colocados en las dos primeras columnas en las siguientes posiciones de las mismas: 45. En ese casos los alfiles se amenazan (se puede comprobar en un tablero). Si restamos las columnas obtenemos \mid 1-2 \mid =1 y si restamos las filas obtenemos \mid 4-5 \mid =1.

Si los colocamos en las posiciones 46 no se amenazan. Restando las columnas obtenemos \mid 1-2 \mid =1 y restando las filas \mid 4-6 \mid =2.

Mezclando los dos problemas (torres y alfiles) obtenemos condiciones para encontrar las soluciones del problema de las ocho reinas:

Las soluciones del problema de las ocho reinas, que consiste en colocar ocho reinas en un tablero de ajedrez sin que ninguna de ellas amenace a otra, se obtienen de todas las permutaciones de las cifras 1, 2, 3, 4, 5, 6, 7 y 8 (es decir, de los números de ocho cifras que tengan todas las cifras distintas y que no tengan ningún cero) tomando únicamente las que cumplan que la diferencia en valor absoluto entre cualesquiera dos de ellos sea distinta de la diferencia en valor absoluto entre las posiciones que ocupan en la permutación (o de la posición que ocupan en el número).

A ver si alguien se anima y nos programa un algoritmo que nos dé esas soluciones.

Fuente: El Laberinto, de Édouard Lucas.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

9 Comentarios

  1. Esto es obvio. Cualquier algorimo implementado que encuentres por ahí, incluso de estudiantes de primero de informática resolverán el problema de esta forma.
    1º Lo de hacer las permutaciones no es más que comprobar que no hay una fila o columna ocupada por otra pieza.
    2º El tema de las diagonales también es obvio…
    Vamos que no por representar la solución del problema de otra manera que parece simple o expresable de forma matemáticamente simple la hace simple desde el punto de vista computacional. El numero de comprobaciones es exactamente el mismo y el algorimo idem.

    Publica una respuesta
  2. Cuando se dibuja un tablero de ajedrez se acostumbra colocarlo de tal manera que la casilla blanca (o el escaque blanco) de la esquina quede ubicada a la derecha.

    Publica una respuesta
  3. Si Guille, claro que es obligatorio ubicar el tablero de ajedrez con el escaque blanco a la derecha de cada jugador. Pero notarás que sobre el tablero dibujado por DiAmOnD no hay trebejos, por lo tanto no se sabe dónde están ubicados los jugadores.
    Sabemos que se acostumbra actualmente, por convención, a ubicar al judador de las blancas en la parte inferior del dibujo y al judador de las negras en la parte superior. Pero también existen representaciones en donde los jugadores están a la izquierda y a la derecha del tablero, como en algunas ilustraciones de la edad media. Como en este caso los jugadores no aparecen creo que cabe el beneficio de la duda.
    Aún así, me parece que lo mejor es respetar la convención actual y ubicar el tablero con la casilla blanca en la esquina inferior derecha.

    Publica una respuesta
  4. En el problema de las 8 reinas se utiliza el tablero de ajedrez y 8 reinas. Sin embargo no es un verdadero problema del juego de ajedrez.

    Publica una respuesta
  5. Habrán notado que el enunciado del problema tiene una falla muy sutil: En el juego de ajedrez las piezas del mismo bando no se “amenazan” entre sí.
    Entonces creo que sería mejor decir que el problema consiste en ubicar a las 8 reinas de tal forma que ninguna de ellas impida el paso de las otras.

    Publica una respuesta
  6. RESUELTO PROBLEMA N REINAS MANDO DE 30 REINAS

    OBVIAMENTE EL ALGORITMO ES GENERAL Y LO PASE A 20 POR 20
    OBTENIENDO LOS RESULTADOS Y VERIFICANDO EN DIBUJO Y
    AHORA ENTREGO SOLUCIONES DE 30 POR 30 QUEDANDO EL
    ALGORITMO DE FORMA GENERAL DE N POR N OBVIO QUE A MAYOR
    EL VALOR N ES MAYOR EL NUMERO DE COMBINACIONES Y EL TIEMPO
    PARA EJECUTARLA LA RESPUESTA.

    ME SIENTO ORGULLOSO DE PRESENTAR UNA SOLUCION A ESE PROBLEMA
    Y ME AGRADARIA QUE LAS PERSONAS INTERESADAS DIBUJARAN O
    CON OTRO PROCEDIMIENTO REVISARAN LOS DATOS

    LOS VALORES ESTAN EN EL PROCEDIMIENTO CLASICO DE LAS MATRICES
    LA ESQUINA SUPERIOR IZQUIERDA ES EL VALOR A(1,1) Y SE FORMA ASI
    A(FILA, COLUMNA)

    A (1,1) , A (1,2) ……….A(1,30)
    A (2,1)


    A(30,1),…. A(30,30)

    EN LOS DATOS EL PRIMER VALOR ES A(1,1) Y EL TREINTA DE LA FILA ES A(1,30)
    Y ASI SUCESIVAMENTE HASTA LLEGAR A LA FILA 30 Y EL PROCESO SE REPITE

    ES UN TEMA INTERESANTE Y ME ALEGRA COMPARTIRLO CON TODOS UDS
    Y QUE SE DIVIERTAN HACIENDO LAS FIGURAS
    ANEXO DE DATOS SON MILES LES DEJO ALGUNOS OK

    EJEMPLO DEL PRIMERO
    A(1,1)=1
    A(1,2)=3
    ..

    A(1,29)=19

    A(1,30)=12

    *** 1 3 5 2 4 9 11 13 15 17 27 24 26 23 25 30 28 10 6 14 29 8 18 20 22 7 16 21 19 12
    *** 1 3 5 2 4 9 11 13 15 18 20 26 24 29 27 23 30 28 7 16 8 12 17 6 10 19 22 25 21 14
    *** 1 3 5 2 4 9 11 13 15 18 22 24 26 29 25 30 14 27 6 12 28 8 19 17 10 21 7 16 23 20
    *** 1 3 5 2 4 9 11 13 15 18 23 21 26 28 30 27 24 7 29 17 14 10 6 16 19 12 22 8 25 20
    *** 1 3 5 2 4 9 11 13 15 18 24 21 25 29 26 30 27 12 6 17 28 7 16 10 20 14 23 8 19 22
    *** 1 3 5 2 4 9 11 13 15 18 24 28 25 23 8 30 27 29 26 10 6 17 20 12 16 22 7 14 21 19
    *** 1 3 5 2 4 9 11 13 15 18 25 23 20 30 28 26 29 27 8 10 17 19 16 7 12 14 21 6 24 22
    *** 1 3 5 2 4 9 11 13 15 18 26 21 29 27 25 23 28 30 16 7 10 14 6 8 19 12 22 24 17 20
    *** 1 3 5 2 4 9 11 13 15 18 27 22 24 26 29 25 30 14 12 7 28 17 20 6 10 16 19 8 23 21
    *** 1 3 5 2 4 9 11 13 15 18 28 25 23 21 27 30 26 29 12 7 17 10 6 16 20 8 24 22 19 14
    *** 1 3 5 2 4 9 11 13 15 19 21 27 25 28 26 24 30 8 14 17 7 29 12 6 18 10 23 16 20 22
    *** 1 3 5 2 4 9 11 13 15 19 22 26 23 29 27 24 30 12 16 6 28 10 18 7 14 8 17 20 25 21
    *** 1 3 5 2 4 9 11 13 15 19 23 25 28 24 29 27 8 14 26 7 18 30 17 12 10 21 6 20 22 16
    *** 1 3 5 2 4 9 11 13 15 19 23 28 24 22 29 26 30 25 6 10 14 16 18 8 21 7 12 17 20 27
    *** 1 3 5 2 4 9 11 13 15 19 24 26 21 30 27 6 28 25 29 16 7 10 14 17 8 20 12 23 18 22
    *** 1 3 5 2 4 9 11 13 15 19 24 28 25 22 26 30 6 14 29 27 12 17 7 21 18 8 10 16 23 20
    *** 1 3 5 2 4 9 11 13 15 19 25 23 20 27 30 26 29 8 12 28 6 18 7 10 14 17 22 16 21 24
    *** 1 3 5 2 4 9 11 13 15 19 25 28 24 21 27 7 30 26 29 14 10 17 20 6 8 12 23 18 16 22
    *** 1 3 5 2 4 9 11 13 15 19 26 23 21 28 25 29 6 30 12 27 18 10 7 20 8 17 14 22 24 16
    *** 1 3 5 2 4 9 11 13 15 19 26 28 20 25 23 29 27 30 16 6 10 12 7 18 21 17 14 8 24 22
    *** 1 3 5 2 4 9 11 13 15 19 27 24 21 25 29 26 30 7 16 12 28 8 14 17 20 22 6 18 23 10
    *** 1 3 5 2 4 9 11 13 15 19 29 20 26 24 27 30 28 25 7 16 14 6 8 10 12 23 17 22 18 21
    *** 1 3 5 2 4 9 11 13 15 20 22 25 28 21 27 30 26 10 8 14 29 7 16 12 6 23 18 24 19 17
    *** 1 3 5 2 4 9 11 13 15 20 22 30 28 26 24 29 10 25 27 14 16 7 12 8 6 23 17 19 21 18
    *** 1 3 5 2 4 9 11 13 15 20 23 26 29 27 22 24 28 10 16 7 30 17 8 12 18 6 21 19 25 14
    *** 1 3 5 2 4 9 11 13 15 20 24 21 27 29 22 28 25 7 30 12 8 19 16 14 6 10 18 23 17 26
    *** 1 3 5 2 4 9 11 13 15 20 24 27 25 23 26 30 12 14 7 28 6 29 17 10 22 16 18 8 21 19
    *** 1 3 5 2 4 9 11 13 15 20 25 19 26 30 27 24 28 14 8 29 16 6 10 17 22 12 7 18 23 21

    ESCRIBIR A rafael57p@gmail.com

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *