lunes, 28 de julio de 2008

Sabías 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 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 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).

Fuente: El Laberinto, de Édouard Lucas.

0 comentarios: