Algoritmo para colocar las torres en un $n\times n$ tablero de ajedrez de tal manera que atacan exactamente $m$ cuadrados

Question

Supongamos que hay un tablero de ajedrez con dimensiones $n\times n$ y pones torres en el tablero de ajedrez de manera que ataquen colectivamente $m$ casillas de ese tablero (una torre también ataca la casilla en la que está). Dado $n$ y $m$ ¿Cómo se puede determinar cuántas torres hay que colocar en el tablero y dónde colocarlas?

Por ejemplo, digamos que las dimensiones del tablero son $3\times 3$ y tienes que cubrir $9$ casillas del tablero colocando torres. Para ello, o simplemente para cubrir el tablero con torres de forma que no haya casillas seguras, puedes poner $3$ torres en las coordenadas $(1,1);(1,2);(1,3)$ en el tablero (el primer número de la coordenada es el número de columna, el segundo es el número de fila). De esta manera, como una torre ataca todas las casillas de la misma fila y columna en la que se encuentra, todas $9$ Las casillas son atacadas.

Pero ¿cómo se pueden encontrar las coordenadas óptimas para cualquier $n$ y $m$ con un algoritmo?

Answer 1

Puedes poner las torres en diagonal con avidez hasta cubrir suficientes casillas. La primera torre cubrirá $2n-1$ cuadrados, el siguiente cubrirá $2n-3$ nuevos, entonces $2n-5$ y así sucesivamente. Para $k$ torres que cubrirá $2kn-k^2$ hasta $k$ se convierte en $n$ . Cualquier forma de colocar las torres que no las tenga en la misma fila o columna conseguirá el mismo número.

Añadido: Si tienes torres en $p$ filas y $q$ columnas que atacará $np+nq-pq$ cuadrados. Para $n=6$ entonces puede cubrir $0,11,16,20,21,24,26,27,28,30,31,32,33,34,35,36$ células