[Programación] Generar cartones de Bingo

[Pablito]

Gente:
Me quede pensando el problema. Me parece muy interesante. Porque es
fácil de entender, parece simple de resolver, pero no lo es. Me hace
acordar al problema del circuito hamiltoniano. Esta bueno intentar
resolver el problema por cuenta propia, pero si nuestra solución es
aparentemente ineficiente, no nos con vence o tal vez no la tenemos, es
mejor pedir ayuda. Las personas apropiadas para resolver este problema
son los matemáticos. No traté de ofender a nadie con lo que dije en el
mail anterior.

Rafael:
Al problema lo intenté pensar de varias maneras buscando una solucion,
pero sin tener exito, les paso a comentar un enfoque, a ver si a alguien
se le prende la lamparita.

Supongan que tienen generados todos los cartones. Es más supongan que
tienen un grafo, en donde los vértices son los cartones, y dos vertices
se unen si no tienen ninguna cifra en común.
Por lo tanto tengo un grafo de C(20 5)=15504 vertices donde cada uno se
une con C(15 5)=3003 vertices.
Cada solución posible del problema se puede ver como un "coloreo" de
grupo de 4 vertices que se unen todos con todos entre ellos (un completo
de 4). (¿se entiende?)

Para entenderlo mejor se pueden construir un super-mini-bingo. Supongan
que los cartones tienen solo 2 números y los numeros van del 1 al 6.
(entonces C(6 2)=15 vertices). Y los cartones se agrupan de a 3. (Cada
vertice tiene C(4 2)=6 aristas).

En este caso hay que pintar con colores diferentes triangulos (un
completo de 3).

Creo que el mini-modelo es bueno ya que se cumple lo siguiente:

agrupacion de cartones*cantidad de numeros por carton= cantidad de
numeros posibles.

en el Bingo:

4*5=20.

en el mini-modelo:

2*3=6.

Por ahi alguien conoce algún algoritmo para hacer este coloreo.

Qué les parece si proponemos una manera (así sea fuerza bruta) y la
tratamos de mejorar. Tal vez lleguemos a alguna euristica simpática.

Saludos.
Pablito.