Resolución de $n$-queens con determinantes

Question

Sigo leyendo sobre un método propuesto de encontrar soluciones para el problema de $n$-queens utilizando determinantes, pero no encuentro ningún detalle específico en cualquier lugar. ¿Puede alguien explicarme cómo encontrar soluciones a $n$-queens usando determinantes o señalarme en la dirección correcta?

Answer 1

Es en Glaisher del documento mencionado en el primer comentario por J. M., pero lo dejo aquí para los que no pueden acceder al papel. Vamos a hacer el ejemplo de la $8 \times 8$ de los casos, y se debe tener claro cómo generalizar a $n \times n$.

Construir la siguiente matriz, observando cómo el patrón de letras y números que ir.
$$A = \begin{bmatrix} a_1 & c_2 & e_3 & g_4 & i_5 & k_6 & m_7 & o_8 \\ b_2 & a_3 & c_4 & e_5 & g_6 & i_7 & k_8 & m_9\\ d_3 & b_4 & a_5 & c_6 & e_7 & g_8 & i_9 & k_{10}\\ f_4 & d_5 & b_6 & a_7 & c_8 & e_9 & g_{10} & i_{11}\\ h_5 & f_6 & d_7 & b_8 & a_9 & c_{10} & e_{11} & g_{12}\\ j_6 & h_7 & f_8 & d_9 & b_{10} & a_{11} & c_{12} & e_{13}\\ l_7 & j_8 & h_9 & f_{10} & d_{11} & b_{12} & a_{13} & c_{14}\\ n_8 & l_9 & j_{10} & h_{11} & f_{12} & d_{13} & b_{14} & a_{15}\\ \end{bmatrix}$$

Si usted construye $\det(A)$, y la huelga de todos los términos en que la misma letra o un número que aparezca más de una vez, a continuación, los términos que siguen dan exactamente las soluciones a las 8 reinas problema.

Así que, ¿por qué es esto? Así, cada término en $\det(A)$ tiene exactamente un elemento de cada fila y de cada columna, así que, usando el determinante inherentemente elimina la tabla de posiciones en la que usted tiene más de una reina en una fila o columna. Ponchó a todos los términos que tienen la misma letra o número elimina de la tabla de posiciones en la que usted tiene más de una reina en la misma diagonal. Lo que queda se debe colocar 8 reinas en el que ninguno está en la misma fila, columna o diagonal. (Probablemente hay una mejor manera de establecer la matriz anterior, pero esta es la forma en Glaisher hace. Además, no va a ser $n!$ términos en el determinante, lo que computacionalmente desagradable, pero Glaisher da algunas formas de simplificar el proceso.)

Si utiliza la permanente , más que el factor determinante, la huelga de términos como arriba, y dejar todas las variables 1, entonces usted tendría el número de soluciones a la $n$ queens problema.

Agregado: he encontrado una búsqueda de Libros de Google enlace a Glaisher del papel de los mencionados anteriormente y en J. M. el primer comentario.