Rompecabezas de tabla antisimétrica donde las filas/columnas suman cero

Question

Me he encontrado con un problema que parece muy sencillo, pero que ha resultado ser simplemente frustrante, y ahora busco expertos en matemáticas para que me ayuden. Tengo una tabla cuadrada con Azul claro , Blanco , Rojo y Verde bloques.

El Azul claro bloques corta la mesa en dos partes iguales en diagonal desde la parte superior izquierda a la inferior derecha. La mitad inferior izquierda de la mesa es un espejo de la superior derecha, pero la Rojo/Verde las cajas son invertidas / opuestas.

Reglas del rompecabezas:

1. Sólo se permiten números enteros y sólo se pueden poner números en los bloques rojos y verdes.
2. Los bloques rojos deben contener números negativos
3. Los bloques verdes deben contener números positivos
4. Todos los bloques blancos y celestes cuentan como 0 y esto no se puede cambiar
5. Las cajas que son opuestas en el espejo deben sumar 0

Objetivo del rompecabezas:

Al final todas las columnas deben sumar 0 y todas las filas deben sumar 0

Agradecería las soluciones a este acertijo, pero lo que realmente me gustaría es que algún experto en matemáticas por ahí me diera la solución del número entero más pequeño.

Lo que quiero decir es: Si tengo dos soluciones, y sumo los números de todos los bloques verdes de ambas, entonces la solución con la suma más baja sería "más pequeña".

Mejor aún sería que alguien me explicara cómo encontrar la solución del número entero más pequeño para otras tablas, con diferentes configuraciones rojo/verde o diferentes tamaños, que funcionen de la misma manera.

Me gustaría encontrar una solución óptima general, si es que tal solución existe en la realidad.

He aquí un intento de solución:

Estas son las soluciones que he encontrado hasta ahora:

Solución 1:

Solución 2:

Se agradecería cualquier ayuda.

Answer 1

Esto puede formularse como un Programación de números enteros o Programación con restricciones problema. Dejemos que $x_{ij} \in \mathbb{Z}$ sea el valor de la celda $(i,j)$ entonces

$$\begin{align} &x_{i,j} = 0 && \text{white and blue cells}\\ &x_{i,j} \ge 1 && \text{green cells}\\ &x_{i,j} \le -1 && \text{red cells}\\ &x_{i,j}= -x_{j,i} && \forall i<j\\ &\sum_i x_{i,j} = 0 &&\forall j\\ &\sum_j x_{i,j} = 0 &&\forall i\\ \end{align}$$

Todas estas son restricciones lineales. (El modelo puede reformularse omitiendo todas las celdas blancas/azules: eso haría el problema más pequeño).

Probé tu problema, y si no cometí errores al transcribir los datos, el problema no tiene una solución factible. (Bueno, cometí algunos errores. Ver abajo los resultados actualizados).

Actualización

Después de arreglar mis datos de entrada, y añadir el objetivo: $$\min \sum_{(i,j) \in Green} x_{i,j}$$ Lo entiendo:

El valor total de las celdas verdes es 87 (este es el valor óptimo: no existe ninguna solución mejor). Esta solución se encontró en 0,28 segundos.

Answer 2

Tras un tedioso proceso de prueba y error, encontré dos soluciones:

Solución 1:

Solución 2:

La solución 1 es mejor porque cuando sumo todos los valores del bloque verde, obtengo 520, que es menor que los 565 de la solución 2.

Lo que es realmente interesante es el número más bajo utilizado en Solución 1 es 2 y el número más bajo utilizado en Solución 2 es 1, pero Solución 1 es una solución "más pequeña".

Así que, o bien Solución 1 es la solución "más pequeña" / óptima (lo que dudo mucho) o hay una solución "más pequeña" por ahí.

Agradecería mucho cualquier ayuda/comentario.

Answer 3

Ahora he escrito un software que puede encontrar soluciones a este tipo de problemas. Me ha llevado a encontrar esta solución:

El número entero más alto que utiliza esta solución es 5