Reyes en un tablero de ajedrez

Si no he hecho los cálculos, pero puedo decirte cómo se pueden hacer para el problema general de colocar$k$reyes en un$p\times q$junta.

Dejar$I=\{1,\ldots,p\}$representan una columna del tablero. Por simplicidad, suponga que$p\le q$. Dejar$\cal{C}$Sea el conjunto de subconjuntos de$I$para que no haya pareja$x,x+1\in C$para cualquier$C\in\cal{C}$: estos conjuntos representan las ubicaciones permitidas de los reyes en una columna.

Ahora definimos una matriz$A$con elementos$A_{ij}$para$i,j\in\cal{C}$: puede enumerar los conjuntos en$\cal{C}$como quieras. Definimos los elementos

$$A_{ij}=\left\{\begin{array}{l l} 0&\text{if there are $x\in i$, $y\in j$ with $|x-y|\le1$}\\ x^{|j|}&\text{otherwise, where $|j|$ is the number of elements in $j$} \end{array}\right.$$ entonces $A_{ij}$representa la adición de una columna con reyes en el $j$posiciones después de haber tenido una columna con reyes en el $i$posiciones.

si dejamos$e=\{\}\in\cal{C}$representar el estado inicial, es decir, no hay reyes a la izquierda del tablero, y sucesivamente agregar$q$columnas, obtenemos

$$e\cdot A^q\cdot 1=\sum_{k} a_kx^k$$ donde el $1$representa el vector $(1,\ldots,1)$y $a_k$es el número de formas de colocar $k$reyes en el $p\times q$junta.

Esto está bastante bien para calcular arbitrariamente$k$y$q$, pero rápidamente se pone difícil es$p$aumenta Por eso seleccionando$p\le q$es una ventaja si el tablero es rectangular pero no cuadrado.

Dejar$K(n,k)$Sea el número de formas de colocar$k$reyes en un$n \times n$tablero de ajedrez

Quiero sugerir un punto de vista teórico de gráficos sobre el problema: está investigando el número de k-conjuntos independientes de un gráfico de cuadrícula donde los elementos diagonales son adyacentes. De manera equivalente, este es el número de k-camarillas en el gráfico complementario. Hay algoritmos generales para calcular esos números, pero también resultados asintóticos y algoritmos para determinar el número máximo de$k$para cual$K(n,k)\neq 0$.

Sin embargo, por solo calcular algunos valores para$K$, Creo que un enfoque como el que sugirió Einar Rødland es más eficiente.

Implementé uno similar y obtuve los siguientes valores para$K(n,k)$donde estan las filas$n$del 2 al 6

1 King     2 Kings     3 Kings    4 Kings     5 Kings     6 Kings   
4         
9          16          8         
16         78          140        79         
25         228         964        1987        1974       
36         520         3920       16834       42368       62266     

y aquí está la secuencia OEIS que está buscando:

http://oeis.org/search?q=8%2C79%2C1974%2C62266&sort=&language=german&go=Suche

EDITAR: el máximo$k$para cual$K(n,k)\neq 0$es$\lceil \frac{n}{2} \rceil^2$

Hay mucha información recopilada en el libro "Piezas de ajedrez que no atacan" (sexta edición) de Vaclav Kotesovec, http://www.kotesovec.cz/ publicado en línea en http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed. pdf (escrito en idioma checo)

Las posiciones de los reyes se discuten en la sección 2 del trabajo:

2.1   k Kings on an n x n chessboard 
2.1.1   k Kings on a 1 x n and 2 x n chessboard 
2.1.2   n Kings on an n x n chessboard
2.2   k Kings on an k x n chessboard 
2.3   m x n Kings on a 2m x 2n chessboard
2.3.1   n Kings on a 2 x 2n chessboard 
2.3.2   2n Kings on a 4 x 2n chessboard 
2.3.3   3n Kings on a 6 x 2n chessboard 
2.3.4   4n Kings on a 8 x 2n chessboard 
2.3.5   5n Kings on a 10 x 2n chessboard 
2.3.6   6n Kings on a 12 x 2n chessboard
2.3.7   7n Kings on a 14 x 2n chessboard 
2.3.8   8n Kings on a 16 x 2n chessboard 
2.3.9   more kings on a 2m x 2n chessboard 
2.3.10   Largest and smallest root 
2.4   n^2  Kings on a 2n x 2n chessboard

2.5-2.9 se trata de tableros de ajedrez con una dimensión conectada al cilindro o con ambas dimensiones conectadas (tablero de ajedrez toroidal)

¿De cuántas maneras diferentes se pueden colocar seis reyes en un tablero de ajedrez de 6×6 para que ninguno ataque a los demás?

Su tarea es "2.1.2 n Reyes en un tablero de ajedrez nxn" y hay un enlace a OIES "n reyes nxn, A201513" - http://oeis.org/A201513

Aquí está la copia de A201513 a partir de febrero de 2014:

ENLACES: Andrew Woods, Tabla de n, a(n) para n = 1..20

V. Kotesovec, Piezas de ajedrez no atacantes

FÓRMULA: Asintóticas (Vaclav Kotesovec, 29 de noviembre de 2011): n^(2n)/n!*e^(-9/2).

AUTOR: Vaclav Kotesovec, 02 de diciembre de 2011

Y tabla para todos n:

1 1
2 0
3 8
4 79
5 1974
6 62266
7 2484382
8 119138166
9 6655170642
10 423677826986
11 30242576462856
12 2390359529372724
13 207127434998494421
14 19516867860507198208
15 1986288643031862123264
16 217094567491104327256049
17 25357029929230564723578520
18 3151672341378566296926684684
19 415294220890662636616927907958
20 57824201125787566041674560880632

Si quiere números para n más grandes, solo pregunte, intentaré calcularlos. Ya calculé algunas de las variantes más importantes de tareas de colocación de reyes para Kotesovec.

Me encantaría ver un enfoque de función generadora, pero mientras esperamos que alguien lo encuentre, aquí hay un bosquejo de cómo podemos aprovechar el pequeño tamaño de este problema para enumerar a mano.

Vamos a usar la propiedad de que no$2\times 2$cuadrado puede contener más de un rey. Entonces dividimos el$6\times 6$rejilla en un$3\times 3$rejilla de$2 \times 2$cuadrícula. Supongamos por el momento que estamos colocando un máximo de 9 reyes en el tablero: por lo tanto, cada uno de estos cuadrados contiene un rey.

El tablero tiene simetría rotacional, así que coloca al rey en el centro.$2 \times 2$el cuadrado está en la parte superior izquierda, y multiplicamos todos los conteos de tableros por$4$:

4x
??????    Key:
?---??      K  King
?-K-??      -  No king
?---??      ?  Uncertain
??????
??????

Ahora considere los cuadrados del centro a la derecha y al centro de la parte inferior, que no están restringidos por nuestro primer rey y tienen efectos colaterales considerables en los tres cuadrados adyacentes. Hay 15 ubicaciones posibles de reyes en estos dos cuadrados (el 16 se descarta porque son adyacentes en diagonal), pero teniendo en cuenta la simetría a lo largo de la diagonal principal, tenemos 9 casos distintos:

4x        8x        8x        8x        8x        4x        8x        8x        4x
??????    ??????    ??????    ??????    ??????    ??????    ??????    ??????    ??????
?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?---??    ?---??
?-K-K-    ?-K-K-    ?-K-K-    ?-K--K    ?-K--K    ?-K--K    ?-K--K    ?-K---    ?-K---
?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?-----    ?---K-    ?----K
?-K-??    ??-K-?    ?---??    ?-K-??    ??-K-?    ?---??    ??---?    ?-----    ??----
?---??    ??---?    ?-K-??    ?---??    ??---?    ?-K-??    ??-K-?    ?-K-??    ??-K-?

Observe que en cada caso, el cuadrado inferior derecho ahora es una elección independiente de los reyes restantes sin colocar, y los espacios disponibles para los reyes restantes sin colocar se ajustan a solo 3 patrones:

96x       64x       4x
??????    ??????    ??????
?         ?         ?   ??
?         ?         ?     
?         ?         ?     
?         ??        ??    
?         ??        ??    

Calcule la cantidad de ubicaciones para cada uno de estos patrones (que es un problema directo de combinatoria en palabras) y solo necesita aplicar las multiplicidades apropiadas.

Aún debe calcular la cantidad de patrones que tienen menos de 9 reyes, pero dado que las restricciones de ubicación son las mismas, cada uno de ellos tendrá uno o más de estos patrones con algunos reyes eliminados. No he trabajado en los detalles, pero espero que las técnicas estándar sirvan.