…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:
(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 
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
y si restamos las filas obtenemos
.
Si los colocamos en las posiciones 46 no se amenazan. Restando las columnas obtenemos
.
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.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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.
Aqui esta el algoritmo, lo programé yo y en este post explico como se resuelve http://blog.amarelloartis.com/2006/11/25/8-reinas-en-un-tablero-de-ajedrez-sin-que-se-ataquen-entre-si/
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.
No es que se acostumbre, es forzosamente necesario por el orden de las piezas. Si no pones la casilla blanca la derecha, nunca podrás colocar bien las piezas. La reina va en una casilla del mismo color que la pieza.
http://descargas.mundijuegos.com/gfx/iconos/ajedrez/tablero-ajedrez.png
Con el escaque negro a la derecha, la reina blanca cae en un escaque negro, y esto es incorrecto.
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.… Lee más »
Es un clásico problema cuya solución más eficiente es un algoritmo recursivo, como podéis ver en http://es.wikipedia.org/wiki/Las_ocho_reinas
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.
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.
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… Lee más »