¿De cuántas formas distintas podemos colocar 4 torres idénticas en el siguiente tablero de ajedrez

Question

¿De cuántas formas distintas podemos colocar 4 torres idénticas en el siguiente tablero de ajedrez para que ninguna se ataque entre sí?

Sé cuando la junta es $n \times n$ y tenemos $n$ entonces la solución es simplemente $n!$

Sin embargo, no estoy seguro de cómo resolver el problema en este caso.

Answer 1

Probablemente haya una forma más inteligente de resolverlo, pero yo lo haría en gran medida por la fuerza bruta, donde lo único "inteligente" que se me ocurre es tener en cuenta que tenemos 4 tamaños de columna diferentes: 2,4,6, y 8. Llamemos a estos tipos de columnas "A", "B", "C" y "D". Ahora, por ejemplo, supongamos que tenemos torres en los tipos de columna A, B, C y D. Éstas se pueden colocar en 2*(4-1) (6-2) (8-3)=2*3*4*5 formas (colócalas siempre empezando por las columnas más cortas). Además, como hay 2 columnas "A", 2 columnas "B", 2 columnas "C" y 1 columna "D", podemos multiplicar esto por 2*2*2*1=8

Bien, esta es la entrada "ABCD" en una tabla que enumera todas las combinaciones de tipos de columnas y cuántos tableros específicos habrá para esa combinación (2*3*4*5*8 en ese caso). Esto es lo que voy a hacer

AABB: 2*1*2*1*1

AABC: 2*1*2*3*4

AABD: 2*1*2*5*2

AACD: 2*1*4*5*2

AACC: 2*1*4*3*1

ABBC: 2*3*2*3*4

ABBD: 2*3*2*5*2

ABCC: 2*3*4*3*4

ABCD: 2*3*4*5*8

ACCD: 2*5*4*5*2

BBCC: 4*3*4*3*1

BBCD: 4*3*4*5*2

BCCD: 4*5*4*5*2

Bien, multiplícalos y súmalos.

Answer 2

Para verificar que la respuesta de Bram28 es correcta, podemos contarla construyendo el grafo cuyos 32 vértices son las posiciones en el tablero, con aristas para los ataques de torre. A continuación, cuente el número de conjuntos independientes de tamaño cuatro.

Aquí está el código de Sage para hacerlo:

from sage.graphs.independent_sets import IndependentSets

posns = [(x,y) for x in range(7) for y in range(max(3-x,x-3),min(5+x,11-x))]
def isedge(a,b):
    return (a[0]==b[0]) != (a[1]==b[1])
G = Graph([posns, isedge])
print(sum(len(x) == 4 for x in IndependentSets(G)))

Y aquí está en SageCell . La respuesta 3532 coincide con la enumeración de Bram28.