Problema de dominación de tablero de ajedrez para una nueva pieza (llamada Wazir)

Question

Estoy tratando de resolver un tablero de ajedrez de la dominación problema, pero para una pieza nueva, que se llama Wazir (gracias a @bof por señalarlo) que amenaza a los vecinos de las plazas que significa los que comparten un borde de unos con otros. También el tamaño del tablero de ajedrez no es $8\times 8$ pero es arbitraria; $M\times N$. Lo que me he encontrado hasta ahora es el cálculo para el pequeño de los casos, por prueba y error para$4\times 2,4\times 3,4\times 4, 4\times 5, 4\times 6, 4\times 7$$5\times 2,5\times 3,5\times 4, 5\times 5, 5\times 6$.

Gráfico actualizado:

    1   2   3   4   5   6   7
4   2   3   4   4   6   7   7
5   2   3   4   6   7   8   9(thanks to @bof)

Puedo conseguir alguna sugerencia para esto?

Este problema se supone para ser una de matemáticas proyecto para un estudiante universitario, y la idea que tengo en mi mente es compleja para el colegio de matemáticas de nivel:

Uno puede ver la definición de una cuadrícula gráfico correspondiente a un tablero de ajedrez de tamaño $(M-1)\times (N-1)$ mediante la conexión de los asociados a los vértices de los cuadrados del tablero de ajedrez si son vecinos de tablero de ajedrez.

ACTUALIZACIÓN:

El conjunto que nos interesa es la que domina conjunto de la cuadrícula gráfico. Parece que los problemas que está abierto no sólo existen límites para: http://www.emis.de/journals/EJC/Volume_18/PDF/v18i1p141.pdf

Yo sería muy feliz si alguien pudiera reconocer lo que estoy diciendo aquí.

Answer 1

El área cubierta por esta pieza (la "wazir") es la forma de un signo más. Es sencillo para embaldosar el plano con cinco cuadrados signos más, por lo que su "pieza de la fracción" enfoques $0.2$ como la junta se vuelve grande. Cada cuadrado es atacado por exactamente una de estas piezas bien lejos de uno de los bordes. Estos wazirs sería dispuestos en un cuadrado inclinado red que podría ser atravesado por una chess knight.

La periodicidad de este mosaico patrón es $5 \times 5$. En otras palabras, si usted desplazar el patrón completo por $5a \hat{x} + 5b \hat{y}$, que el mapa en sí mismo.

Los bordes de la junta, donde las desviaciones suceder. Extra wazirs tiene que ser puesto a cubrir las plazas donde el infinito del plano de simetría se rompe. Específicamente, cada quinta plaza en el borde tendrá que ser el "tapado" por un wazir porque dejó unattacked.

El problema ahora es minimizar la suma de la cantidad de borde de las plazas de la necesidad de estar conectado, más el número de no-borde de las plazas que deben ser ocupados por un wazir.

Dado que el patrón se repite por el desplazamiento de un múltiplo de $5$ plazas en cualquier dirección, sólo tenemos que considerar el tamaño de la cuadrícula modulo $5$ a determinar las desviaciones en el borde.

La respuesta será de la forma

$$K(M,N) = \lfloor\frac{MN + 2(M+N)}{5}\rfloor + E(M (\text{mod } 5), N (\text{mod } 5)),$$

donde $E(M (\text{mod } 5), N (\text{mod } 5)) = E(N (\text{mod } 5), M (\text{mod } 5))$ es una función de ajuste.

Así que para un tamaño de cuadrícula de $M \times N$ veamos los casos. Por simetría, se puede considerar sólo aquellos que $M \leq N$ (mod $5$).

El cálculo explícito de $M = 10 ... 14, N = 10 ... 14,$ me encontré:

$$E(0,0) = E(1,0) = E(2,0) = E(3,0) = E(4,0) = 0;$$

$$E(1,1) = E(1,2) = E(1,3) = E(1,4) = -1;$$

$$E(2,2) = -2; E(2,3) = E(2,4)= -1;$$

$$E(3,3) = E(3,4) = -1;$$

$$E(4,4) = -2.$$

Esto probablemente se rompe para un pequeño $M, N$. Yo estaba buscando más para arrojar luz sobre el caso general, anteriormente.

Para pequeñas tablas, hay otros comportamientos. $M=1$ es interesante que la wazirs puede tener dos espacios en blanco entre ellos en las configuraciones óptimas para $N > 3$. (Deben de $N > 5$.) Esto está relacionado con el hecho de que el tamaño de la junta directiva de los límites de su ataque campo para dos plazas. Por lo tanto la pieza fracción $\geq 1/3.$ $K(M, 1) = \lceil M/3 \rceil.$

Para $M=2$, el tamaño de la junta directiva limita el ataque de campo para tres plazas, y la pieza de la fracción de ahí $\geq 1/4$. A partir de mis observaciones, para $M \geq 2$, $K(M,2) = \lceil (M+1)/2 \rceil.$