¿Cómo resolver una cuadrícula 5x5 con 16 diagonales?

Question

Tengo una cuadrícula 5x5 y tengo que llenar 16 cuadraditos con una diagonal

Reglas

• No puedes colocar más de una diagonal en cada cuadrado
• Las diagonales no pueden tocarse entre sí (ejemplo abajo)

Haz clic aquí para ver la solución

Pero lo que busco aquí es una solución matemática para este rompecabezas, ni siquiera sé por dónde empezar a buscar información.

¿Alguien puede explicar cómo resolver este rompecabezas utilizando ecuaciones?

Answer 1

Imagínalo de esta manera: Tienes una matriz de 5x5, y necesitas llenarla con valores 0, 1 o -1, con tres restricciones:

1. Las celdas que comparten un borde con una celda con un $\pm 1$ no pueden contener un $\mp 1$.
2. Si una celda contiene un 1, las celdas adyacentes arriba a la izquierda y abajo a la derecha tampoco pueden contener un 1.
3. Si una celda contiene un -1, las celdas adyacentes abajo a la izquierda y arriba a la derecha tampoco pueden contener un -1.

Aquí, las celdas que contienen un "1" tienen una diagonal que va de arriba a la izquierda a abajo a la derecha, y las celdas que contienen un "-1" tienen una diagonal en la otra dirección. Las celdas que contienen 0 no tienen diagonal en absoluto.

Entonces, para la cuadrícula de ejemplo que proporcionas, comienzas con la cuadrícula:

$$ \begin{matrix}0&0&-1&0&0\\0&-1&0&-1&1\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{matrix} $$

No creo que haya "una solución matemática" para esto, es decir, dudo que se pueda encontrar la "respuesta correcta" de inmediato sin cierto nivel de prueba y error. Pero sí proporciona un buen punto de partida para automatizar la búsqueda, si quieres intentar resolverlo computacionalmente.

Answer 2

He escrito una búsqueda por fuerza bruta, que parece funcionar. Pero tomaría días inspeccionar las $3^{25} = 847,288,609,443$ configuraciones o reimplementar algunas partes en C.

Algunas soluciones factibles de una caminata aleatoria:

[ 45.33%] [1100201102001021010210022] encontrado: len = 14 [max = 14]

 / / . . \
 . / / . \
 . . / . \
 / . / . \
 / . . \ \

[ 41.74%] [1020210202102021101001001] encontrado: len = 14 [max = 14]

 / . \ . \
 / . \ . \
 / . \ . \
 / / . / .
 . / . . /

[ 99.59%] [2222200000102011000011111] encontrado: len = 14 [max = 14]

 \ \ \ \ \
 . . . . .
 / . \ . /
 / . . . .
 / / / / /

[ 38.82%] [1011110001111010000011111] encontrado: len = 15 [max = 15]

 / . / / /
 / . . . /
 / / / . /
 . . . . .
 / / / / /

Answer 3

Entre dos filas adyacentes de cuadrados hay una fila de seis esquinas. Cada diagonal utiliza una de ellas, por lo que como máximo hay seis diagonales en dos filas adyacentes.
Como máximo seis diagonales en filas 1-2, seis en filas 3-4, por lo que al menos cuatro en la fila 5 para hacer dieciséis. De la misma manera, las filas 3 y 1 tienen al menos cuatro diagonales.
Entonces las filas 2 y 4 tienen como máximo dos diagonales, o de lo contrario tendrías más de seis en dos filas adyacentes.

Diecisiete es imposible: dado que la Fila1+Fila2 tiene como máximo seis diagonales, al igual que la Fila3+Fila4, necesitas cinco diagonales en la Fila5. Por la misma razón, necesitas cinco en la Fila3 y Fila1. Pero entonces necesitas una en la Fila2 o Fila4, y las únicas esquinas libres no permiten que una diagonal las una.

La Fila3 no puede tener cinco diagonales: si las tuviera, la Fila2 y la Fila4 solo podrían tener una cada una. Eso hace siete, dejando nueve más entre la Fila1 y la Fila5. Entonces la Fila1 o la Fila5 también tiene cinco. Pero, igual que para el caso de 'diecisiete', si la Fila1 y la Fila3 tienen cinco entonces la Fila2 debe estar vacía; por lo que la Fila4 y la Fila5 tienen seis entre ellas para hacer dieciséis; entonces la Fila5 tiene cinco diagonales; por lo que la Fila4 está vacía; y solo tenemos quince diagonales.

Entonces la Fila3 tiene como máximo 4. La Fila1 y la Fila2 tienen como máximo seis entre ellas, al igual que la Fila4 y la Fila5. Por lo tanto, para hacer dieciséis en total, la Fila1 y la Fila2 tienen exactamente seis entre ellas, al igual que la Fila4 y la Fila5. No hay esquinas libres entre la Fila1 y la Fila2, ni entre la Fila4 y la Fila5. Por lo tanto, una vez que se elige la Fila1, hay como máximo cuatro opciones para la Fila2; y similar para la Fila5 y la Fila4.

Hay 18 posibles Filas1 con al menos cuatro diagonales. Hay 16 posibles Filas3 con exactamente cuatro diagonales.

Toma las 18 posibles Filas1, emparéjalas con sus posibles Filas2 para obtener algunas docenas de pares Filas1Filas2. Para cada par, verifica cuál de las dieciséis posibles Filas3 encaja con la fila2 particular. Después de haber revisado todos los pares Filas1Filas2, tienes un subconjunto de las dieciséis que pueden ser parte de un triple Filas1Filas2Filas3.
Para verificar si esa Fila3 puede unirse a una Fila4 y Fila5, solo tienes que reflejarla en un espejo para que las diagonales ascendentes se conviertan en diagonales descendentes, y verificar si esa reflexión puede ser parte de un triple Filas1Filas2Filas3.

Esto son unas cientos de comparaciones, que podrían llevar diez minutos a mano.

Answer 4

Las soluciones son (generadas por computadora, la diagonal principal codificada como +1): costo = 16 $$ \begin{matrix}1&0&-1&-1&-1\\1&0&-1&0&0\\1&1&0&1&1\\0&0&-1&0&1\\-1&-1&-1&0&1\end{matrix} $$ y $$ \begin{matrix}1&1&1&0&-1\\0&0&1&0&-1\\-1&-1&0&-1&-1\\-1&0&1&0&0\\-1&0&1&1&1\end{matrix} $$ Ver también A264041 (costo de las soluciones), A264667 (número de soluciones)

Answer 5

Si codificamos la cuadrícula de solución ($5 \times 5$) como un vector (de longitud $25$) y denotamos las diagonales / como 1 y \ como -1, por ejemplo, con un espacio en blanco en una celda como 0, podemos usar el retroceso para resolver el problema de las 16 diagonales.

Comenzando desde un vector de solución vacío, la solución puede ser extendida de forma recursiva con el retroceso, en cada etapa comprobando si la solución parcial es válida (es decir, ninguna de las diagonales se toca) con la función can_be_extended_to_solution() como se muestra en el siguiente fragmento de código, de lo contrario se descarta la solución actual.

La siguiente figura muestra lo que la función can_be_extended_to_solution() debe comprobar para asegurar que no haya diagonales que se toquen en la solución.

La función num_diag() cuenta el número de diagonales presentes en la solución hasta ahora, podemos terminar si tenemos $16$ diagonales.

def can_be_extended_to_solution(solution_vector):
    # comprobar si alguna de las diagonales se toca en la solución hasta ahora
    if ∃ un par de diagonales que se tocan en la solución:
       return False
    return True

def extend_solution_with_backtracking(solution_vector, n):
  if len(solution_vector) == 25 and num_diag(solution_vector) == 16:
      # ¡encontrada la solución!
      print(solution_vector) 
      exit()
  for k in range(-1,2): 
    # intentar /, \ o espacio en blanco en la siguiente posición
    solution_vector.append(k)
    if can_be_extended_to_solution(solution_vector):
        extend_solution_with_backtracking(grid_vec, n)            
    solution_vector.pop()

def num_diag(solution_vector):
    # devolver el número de diagonales / o \ presentes en la solución
    return sum([1 for x in solution_vectorif x != 0])

La siguiente figura muestra una solución obtenida con el algoritmo de retroceso anterior.

La siguiente animación muestra cómo las soluciones parciales pueden ser extendidas usando el retroceso: