Dividir la matriz en 8 direcciones PUZZLE

Question

Tengo un problema que me ha estado molestando durante el último mes, hay una matriz con cuadrados de 8x8, por lo tanto 64 cuadrados, y con 8 bolas colocadas al azar cada una en un cuadrado. Necesito encontrar la solución de cómo se debe dividir la matriz en 8 partes de manera que cada bola esté en una parte diferente y cada parte tenga exactamente 8 cuadrados. Por cierto, cada "puzzle" puede tener varias, una o ninguna solución.

Antes:

Después:

Answer 1

No creo que haya una solución fácil. En principio se podría hacer, pero en la práctica dudo que sea realista: Para cada bola $b$ , dejemos que $S_b$ sea el conjunto de todos los conjuntos conexos de cardinalidad $8$ que contiene $b$ y ninguna otra bola. Tome las variables binarias $x_i$ para todos los miembros $i$ de todos $S_b$ . Entonces quiere satisfacer las condiciones $$\eqalign{\sum_{i \in S_b} x_i &= 1\ \text{for each $ b $}\cr x_i + x_j &\le 1 \ \text{if $ x_i \Nen S_b $ and $ x_j en S_{b'} $ with $ b \ne b' $ and $ i \cap j \ne \\\N - vacía $}\cr} $$ Utilice un solucionador SAT o una programación lineal entera.

En los casos en los que existe una solución, puede encontrarla utilizando métodos heurísticos como la búsqueda tabú o el recocido simulado.

Answer 2

Se puede modelar esto como un problema de partición de conjuntos de la siguiente manera. Sea $S$ sea el conjunto de todos los conjuntos conectados de cardinalidad 8 que contienen exactamente 1 bola. Para el ejemplo de rompecabezas anterior, resulta que $|S|=23617$ . Sea $N=\{1,\dots,8\}$ . Para $(i,j) \in N \times N$ , dejemos que $S_{i,j} \subset S$ sea el subconjunto de conjuntos que contienen la célula $(i,j)$ . Para $s\in S$ y la variable de decisión binaria $x_s$ indican si el conjunto $s$ está seleccionado. Las restricciones son: $$\sum_{s\in S_{i,j}} x_s = 1 \quad \text{for $ (i,j)\Nen N \Nveces N $}$$

Existen múltiples soluciones, entre ellas ésta: