Existe una familia de problemas de ajedrez en la que se intenta dominar un tablero con el menor número posible de copias de una pieza determinada. El tablero está dominado si cada casilla contiene una pieza o es atacada por una.
Por ejemplo, para dominar un tablero de ajedrez habitual con 8 torres, simplemente coloca una torre en cada casilla de una diagonal. Se puede comprobar fácilmente que esto es óptimo, es decir, no 7 las torres pueden dominar un tablero de ajedrez. Este resultado se extiende fácilmente a un n×n de la junta, para cualquier n .
También puedes preguntar por el dominio de las torres en tres dimensiones, donde las torres pueden deslizarse a la izquierda/derecha, atrás/adelante o arriba/abajo. Este problema es más difícil, pero tiene una buena solución: ⌈n2/2⌉ Las torres son necesarias y suficientes para dominar un n×n×n tablero. Ver aquí para una prueba.
Mi pregunta es sobre el caso de cuatro dimensiones. Aquí, hay cuatro ejes, y las torres pueden deslizarse a lo largo de cualquier eje. Específicamente,
¿Cuántas torres se necesitan para dominar un 4×4×4×4 ¿pizarra?
Me preguntaba si alguien había estudiado este problema antes, o tenía alguna buena idea de ataque.
Sé que 32 las torres son suficientes, mientras que 22 las torres son insuficientes. He llenado páginas tratando de tener éxito con 31 torres, en vano. Si tienes curiosidad, el número óptimo para un tablero de 2 x 2 x 2 x 2 es de 4 torres, y para un tablero de 3 x 3 x 3 x 3 es de 9 torres.
0 votos
Probablemente escribiría un simple programa de ordenador. Dadas las posiciones de las torres, comprobaría cada una de las 256 cuadrados si está controlado por 0 , 1 o varias torres. Esto ayuda a evitar errores y puede indicar qué posiciones de torre pueden mejorarse.
0 votos
Esta es una buena idea, pero para comprobar si 31 torres es suficiente, el programa tendría que comprobar todas \binom{256}{31}\approx 2^{132} posibles colocaciones de 31 torres. Incluso usando el control de simetría del tablero (4^!)^5 casos a la vez, esto es demasiado grande para la fuerza bruta.
0 votos
Claro que sí. Pero no me refiero a un programa inteligente que optimice la configuración. Sólo un programa muy básico donde tú, el usuario, introduces una configuración y el ordenador te dice el resultado. Entonces puedes mover una torre a otra casilla y ver si mejora la dominación o no.
0 votos
Los términos de la expansión del determinante dan las posiciones de las torres para el n por n matriz. Así que, posiblemente se necesite dar sentido a un determinante 4D para resolver el problema...