Los reyes en un tablero de ajedrez

Question

En cuántas formas diferentes pueden seis reyes colocarse en un $6\times 6$ tablero de ajedrez de manera que nadie los ataques de los demás?

Si el problema se preguntó por un $3 \times 3$ junta y $3$ reyes, entonces la respuesta sería de 8.

Traté de encontrar todas las combinaciones de al menos dos reyes están atacando unos a otros. Coloca dos reyes adyacentes vertical, horizontal, diagonal y se contó el número de posibilidades para el resto de las $4$ reyes. Pero no parece ser demasiado muchos solapamientos, lo que significa que me cuentan la misma situación más de una vez. Y yo no podía encontrar una manera de restar todas las situaciones que se dan más de una vez.

Answer 1

Si no he hecho los cálculos, pero puede informarle de cómo se puede hacer para que el problema general de la colocación de $k$ reyes en un $p\times q$ junta.

Deje $I=\{1,\ldots,p\}$ representa a una columna de la tabla. Por simplicidad, suponga que $p\le q$. Deje $\cal{C}$ el conjunto de los subconjuntos de a$I$, de modo que ningún par $x,x+1\in C$ cualquier $C\in\cal{C}$: estos conjuntos representan permitido la colocación de los reyes en una columna.

Ahora vamos a definir una matriz de $A$ con elementos $A_{ij}$$i,j\in\cal{C}$: se pueden enumerar los pone en $\cal{C}$ cualquier manera que te gusta. Podemos definir los elementos $$ A_{ij}=\left\{\begin{array}{l l} 0&\text{if there are %#%#%, %#%#% with %#%#%}\\ x^{|j|}&\text{otherwise, where %#%#% is the number of elements in %#%#%} \end{array}\right. $$ por lo $x\in i$ representa la adición de una columna con los reyes en el $y\in j$ posiciones después de haber tenido una columna con los reyes en el $|x-y|\le1$ posiciones.

Si dejamos $|j|$ representan el estado inicial, es decir, no los reyes a la izquierda de la placa, y añadir, sucesivamente, $j$ columnas, obtenemos $$ e\cdot A^q\cdot 1=\sum_{k} a_kx^k $$ donde el $A_{ij}$ representa el vector $j$ $i$ es el número de maneras de colocar $e=\{\}\in\cal{C}$ reyes en el $q$ junta.

Esto es bastante aceptar para calcular arbitrarias $1$$(1,\ldots,1)$, pero rápidamente se ponen difíciles es $a_k$ aumenta. Es por eso que la selección de $k$ es una ventaja si la mesa es rectangular pero no cuadrada.

Answer 2

Deje $K(n,k)$ el número de maneras de colocar $k$ reyes en un $n \times n$ tablero de ajedrez.

Quiero sugerir una gráfica teórica punto de vista sobre el problema: Se está investigando el número de independientes de k-sets de una cuadrícula gráfico donde los elementos de la diagonal son adyacentes. Equivalentemente, este es el número de k-cliques en el complemento gráfico. Hay algoritmos generales para calcular los números, pero también asintótica resultados y algoritmos para determinar el número máximo de $k$ que $K(n,k)\neq 0$.

Sin embargo, sólo para el cálculo de algunos valores de $K$, creo que un enfoque como el que Einar Rødland sugerido es más eficiente.

He implementado una similar y obtuvo los siguientes valores para $K(n,k)$ donde las filas son $n$ de 2 a 6

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

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

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

EDIT: la máxima $k$ que $K(n,k)\neq 0$ $\lceil \frac{n}{2} \rceil^2$

Answer 3

Hay gran cantidad de información recopilada en "No atacar a las piezas de ajedrez" (sexta edición) libro de Vaclav Kotesovec, http://web.iol.cz/vaclav.kotesovec/ publicado en línea en http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf o en http://members.chello.cz/photos2/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf (escrito en lengua checa)

Reyes posiciones se discutió en la sección 2 de la obra:

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 son unos tableros de ajedrez con uno de dimensión conectado en el cilindro o con ambas dimensiones conectado (toroidal tablero de ajedrez)

de cuántas maneras diferentes puede seis reyes colocarse en un 6×6 tablero de ajedrez de manera que nadie los ataques de los demás?

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

Esta es la copia de A201513 de febrero de 2014:

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

V. Kotesovec, No atacar a las piezas de ajedrez

FÓRMULA: Asymptotics (Vaclav Kotesovec, Nov 29 2011): n^(2n)/n!*e^(-9/2).

AUTOR: Vaclav Kotesovec, Diciembre 02 de 2011

Y de mesa para todas las 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 desea que los números más grandes de n, acaba de pedir, voy a tratar de calcular. Ya he calculado algunos de los más grandes variantes del rey colocar tareas para Kotesovec.

Answer 4

Me encantaría ver una generación de función de enfoque, pero mientras estamos a la espera de que alguien encuentre aquí un esbozo de cómo podemos aprovechar el pequeño tamaño de este problema a enumerar a mano.

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

La junta directiva tiene simetría rotacional, por lo que wlog el rey en el centro de la $2 \times 2$ plaza se encuentra en la parte superior izquierda, y multiplicamos todos los de la junta de cuenta por $4$:

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

Ahora, considere el centro-derecha y el centro-inferior plazas, que son sin restricciones de nuestro primer rey, y tienen una considerable incidencia en la adyacente de tres plazas. Hay 15 posibles ubicaciones de los reyes en estos dos plazas (el 16 se descartó debido a que está en diagonal al lado), pero teniendo en cuenta la simetría a lo largo de la diagonal principal tenemos 9 distintos casos:

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-?

Observar que, en cada caso, de la parte inferior derecha de la plaza es ahora una opción independiente de los restantes sin colocar reyes, y de los espacios disponibles para el resto de los sin colocar reyes ajuste de tan solo 3 patrones:

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

Calcular el número de puestos para cada uno de estos patrones (que es una recta combinatoria-en palabras de problema), y es necesario aplicar las multiplicidades.

Usted todavía necesita para calcular el número de patrones que tienen menos de 9 reyes, pero desde que las restricciones en la colocación de la misma a cada uno de ellos va a ser uno o más de estos patrones con algunos reyes eliminado. No he trabajado a través de los detalles, pero tengo la esperanza de que las técnicas estándar serviría.