Conceptos de poliominós

El interés de los polióminos radica en que su aparente simplicidad no tiene nada que ver con la potencial fuente de problemas de inteligencia que estos suponen, algunos de los cuales aún sin solución.
Aunque hay distintos tipos de juegos con polióminos (y en especial con pentóminos) la parte principal de este trabajo serán los problemas de recubrimiento de tableros con pentóminos.
No obstante el applet desarrollado comprende tres tipos de problemas: recubrimiento de tableros, rectificado de poliominós y recubrimientos de pentominós a escala, si bien estos últimos se pueden considerar un subtipo de los problemas de recubrimiento.

Introducción
El nombre de poliominós se debe al matemático norteamericano Salomon W. Golomb de quién partió la idea hacia 1954.
Lo que hace radicalmente diferente a este tipo de rompecabezas de otro tipo como los puzzles es que si bien hay puzzles complicadísimos de, pongamos 1.000 piezas, una vez resueltos no hay más que hacer y acaba la diversión.
Este no es el caso de los juegos con poliominós que entrarían en este sentido en la misma familia de juegos que el cubo de Rubik, aunque como se verá más adelante con muchos puntos de contacto con los puzzles.
Otros puntos que distinguen a este tipo de juegos son la carga matemática que contienen y la variedad de problemas que con ellos se pueden plantear.

¿Qué es un poliomonó? Conceptos básicos
Los poliominós son polígonos construidos a base de adosar cuadrados unitarios a lo largo de sus lados.
Puesto que una pieza de dominó se compone, desde el punto de vista geométrico, de la unión de dos cuadros, podemos llamar triminós a la unión de tres cuadrados, tetróminos a la de cuatro y así sucesivamente
Pero de un modo formal se pueden definir como un conjunto de cuadrados conectados entre sí por uno de sus lados de tal modo que no queden huecos en el interior de la estructura resultante.
Así las siguientes piezas (unos posibles heptómino y pentómino) no serían consideradas como tales.

Además sólo se considerarán poliominós distintos a aquellos que no se pueden obtener a partir de otro dado con una simple función de rotación o deinversión/reflexión. Estas funciones se contemplan a continuación. En ambos casos el poliominó obtenido no se considerará distinto del que teníamos, sino una variación del original:

La figura anterior representa un N-poliominó tras aplicarle la función de rotación o inversión que transforma el poliominó dado (parte izquierda del diagrama) en su imagen especular (parte derecha), basándose en el eje dibujado.
La rotación de una pieza es de 90º y el poliominó resultado son la misma pieza.

Es fácil imaginar que el número de piezas irá creciendo exponencialmente pero un tema curioso y a simple vista factible es el de ver cuantos polióminos diferentes existen de orden n.
Con 2 cuadros tenemos un sólo dominó, es lógico y con 3 cuadros tenemos dos posibles triminós, pero generalizando:

¿Cuantos posibles polióminos de n cuadros existen?
Consideremos ahora las siguientes funciones dependientes del orden del poliominó tratado:
G(n).- Número de poliominós de orden n, sin contar rotaciones ni reflexiones/inversiones (2 dominós, 5 tetrominós, ...).
H(n).- Número de poliominós de orden n sin contar los poliominós resultado de rotaciones, pero contando como distintos los poliominós resultados de invertir otros poliominós.
T(n).- Número total de poliominós de orden n, contando como distintos tanto las rotaciones como las reflexiones de otros poliominós.
S(n).- Número de poliominós de orden n que son invariables frente a la función de reflexión (pudiendo aplicar la rotación).
La siguiente tabla muestra los valores de estas funciones para un valor de n entre 1 y 12:

n	G(n)	H(n)	T(n)	S(n)
1	1	1	1	1
2	1	1	2	1
3	2	2	6	3
4	5	7	19	4
5	12	18	63	6
6	35	60	216	10
7	108	196	760	20
8	369	704	2.725	34
9	1.285	2.500	9.910	70
10	4.655	9.189	16.446	121
11	17.073	33.896	135.268	250
12	63.600	126.759	505.861	441

Existen algunas relaciones entre estas funciones. Por ejemplo es fácil ver que S(n) = 2*G(n) – H(n)
Se pueden contemplar más funciones y relaciones entre ellas de las aquí expuestas. En la bibliografía citada se encuentran algunos estudios más profundos sobre este tema, pero como aproximación da una idea de la complejidad del problema.
Si contemplamos la función T(n), nos da una idea del número de combinaciones del que dispondríamos para, en el caso de problemas de recubrimientos, recubrir un tablero de heptominós.

En la figura siguiente se muestra una tabla con las diferentes piezas válidas que existen de orden n (hasta cinco, pentominós). Se corresponde con la funciónG(n) estudiada en el punto anterior, poliominós distintos sin aplicar funciones de rotación o inversión sobre otros poliominós.

Problemas de recubrimiento

Un tipo de problemas muy interesantes son los problemas de recubrimiento de tableros con poliominós: Dado un tablero similar al de ajedrez (resultado de poner o quitar en él más cuadros) que alterna cuadros blancos y negros se debe recubrir con piezas de orden n.

TOMADO DE: http://www.dma.fi.upm.es/docencia/primerciclo/matrecreativa/juegos/poliominos/inicio.html