Viernes

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/