El problema de las N Reinas; el proyecto BOINC hecho en Chile
Desde el mundo de las matemáticas y el ajedrez hace su presencia la Universidad de Concepción (Chile), haciendo uso del programa de computación distruida BOINC, la cual nos permite a todos nosotros, colaborar con la resolución del problema de las N reinas (originalmente las ocho reinas) que consiste en colocar sobre un tablero de ajedrez ocho reinas sin que éstas se den jaques entre ellas.
Veamos más a fondo: El problema de las N Reinas
El problema de las 8 reinas original consistía en encontrar una manera de posicionar 8 reinas en un tablero de ajedrez de manera tal que ninguna reina estuviera atacando a otra reina. Otra forma de ver el problema es el poner 8 cosas en una malla de 8×8 de manera tal que ninguna de ellas este sobre la misma fila, columna o diagonal.
Desde hace ya mucho tiempo se conoce que existen 92 soluciones a este problema. De estas 92, hay 12 soluciones únicas. Es decir, todas las 92 soluciones pueden transformarse en una de las 12 únicas mediante rotaciones o reflexiones.
El problema de las N reinas:
Si se desea resolver el problema para un tamaño de tablero arbitrario NxN, entonces se dice que se habla del problema de las N Reinas. Por ejemplo, para N=10 tenemos un tablero de ajedrez de 10×10 el cual tiene 724 soluciones, de las cuales 92 son únicas.
Conocimiento actual:
Actualmente, se conoce el resultado para el problema de las N reinas, hasta N = 25 que tiene 2,207,893,435,808,352 soluciones[1].
Click para ampliar
EL PROYECTO
¿De que trata?
Este proyecto intenta encontrar los resultados al problema de las N reinas a partir del tamaño N=19 utilizando la plataforma de computación distribuida entregada por BOINC.
¿Cómo se calcula?
En el problema de las N reinas el número de soluciones y el tiempo que se requiere para calcular todo un tablero se incrementa en orden n!. Debido a esto, resolver el problema en un solo computador común toma mucho tiempo para tableros mayores a N=19.
Pero, debido a la naturaleza del problema, es un candidato ideal para paralelización. Ésto se realiza poniendo una reina en las diferentes posiciones de la primera columna (o fila dependiendo de la perspectiva) del tablero y luego resolviendo cada uno de los problemas resultantes. Luego la solución del tablero completo es la suma de las soluciones de los sub-problemas antes mencionados.
Por ejemplo para el problema de las 8 Reinas tenemos:
De esta manera, se puede resolver un tablero de tamaño N como N tableros de tamaño N-1 (realmente de tamaño N, pero con una reina ya posicionada como condición inicial). Y de esta misma manera, seguir subdividiendo el problema hasta obtener tableros lo suficientemente pequeños para ser resueltos en un computador común en un tiempo razonable.
Cálculo
Debido a que el problema de las N reinas tiene propiedades de simetría, no es realmente necesario poner una reina en todas las posiciones de la primera columna. El proyecto aprovecha eso y sólo calcula las soluciones de la primera mitad del tablero y luego el total obtenido debe duplicarse para obtener el número de soluciones que tiene el tablero.
Actualmente, el código que utiliza el proyecto para resolver el problema esta basado en el código de Jeff Somers[2], modificado para trabajar con subtableros, checkpointing, y la infraestructura de BOINC.
[1] Soluciones conocidas a la fecha Sloane’s On-Line Encyclopedia of Integer Sequences
[2] Jeff Somers, Programador en C/C++
Página web del proyecto: http://nqueens.ing.udec.cl/
Category: Ciencia en casa
Publicado por Astro Tiare
Atraída por la astronomía a temprana edad, se dedica a esta ciencia a modo amateur y a través de divulgación a nivel escolar. Su búsqueda y exploración constante de nuevas áreas abarca: Fotografía, Traducción y Radioafición: CD4629 en Categoría Aspirante. Su meta es inspirar el desarrollo y curiosidad científica en las nuevas generaciones a través del área educacional en actividades recreativas.
Subscribe
If you enjoyed this article, subscribe to receive more just like it.
ejemplos de n reinas en un tablero de 8 x 8
Buenas, necesitaria saber si hay una formula que me revele la cantidad de soluciones para el problema de las n reinas en un tablero de nxn, tal cual figura en la tabla que se detalla arriba. Como se obtienen esos valores??
Muchas Gracias. Saludos
Hola Marcos, existe el sitio Wolfram Math World que habla sobre el problema de las N Reinas, espero que sea de tu utilidad. ¡Saludos!
soy estudiante del primer semestre EN el IPN mexico,
mi profe de programacion me dejo el programa de las 8 reinas el cual me dijo k lo hiciera con dos funciones una k sak elas permutaciones y otra k evalue cuando se atakan
int evalua(char *numeros)
{
if (condicion)// si la condicion con la k no se comen es cierta regresa el valor 1 y la imprime
printf(“%s”,numeros);
return 1;
}
me gustaria saber si saben algo de la forma de resolver este problema en un tablero de 8×8 para n reinas…