Fuera de mi cabeza, realmente no puedo pensar en una aplicación particular para este tipo de problema de teoría de grafos. Puede ser útil en los cálculos en los que desea evitar algún tipo de conteo doble.
Por otro lado, ha habido algunos intentos de modelar el problema de n-Queens como un problema de mecánica estadística (SM) [1,2], de modo que parte de la maquinaria teórica familiar desarrollada para SM pueda aplicarse a la solución de o al menos caracterizar el problema. Entonces, es más como aplicar la teoría de la materia condensada al problema de n-Queens.
Dean y Parisi (un gran nombre en física teórica) mapearon el problema a un sistema de gas reticular bidimensional con una forma peculiar de interacción de largo alcance en un artículo que tiene casi dos décadas de antigüedad. Cito de su artículo:
- Tengo 28 años, estoy desempleado, tengo 17 meses de tiempo libre y quiero ser Red Topcoder para el final. Si es posible, ¿cómo debo hacerlo?
- ¿Cuál es la diferencia entre la simulación de Monte Carlo y la simulación estocástica?
- ¿Un algoritmo 'clásico' de Shor esencialmente destruiría el interés en las computadoras cuánticas?
- ¿Por qué las matemáticas son importantes para la inteligencia artificial y el aprendizaje automático?
- ¿Existe un algoritmo para contar el número de subcadenas cuya suma es divisible por 3?
El espacio del modelo es una red [matemática] L \ veces L [/ matemática] con condiciones de límite periódicas impuestas para facilitar un análisis analítico y numérico más fácil, el problema original, por supuesto, no tiene condiciones de límite periódicas. En este retículo hay partículas [matemáticas] N [/ matemáticas], la energía de una configuración dada es dada por el hamiltoniano
[matemáticas] H = \ sum_ {i \ neq j} ^ {N} \ delta ^ {L} _ {x_i, x_j} + \ delta ^ {L} _ {y_i, y_j} + \ delta ^ {L} _ {x_i-y_i, x_j-y_j} + \ delta ^ {L} _ {x_i + y_i, x_j + y_j} [/ math]
donde la posición de la i- ésima partícula se denota por el par ([matemáticas] x_i
, y_i [/ matemáticas]). El superíndice [matemática] L [/ matemática] en [matemática] \ delta [/ matemática] indica que son las funciones estándar delta de Kronecker pero con módulo aritmético [matemática] L [/ matemática]. Se puede ver que para un tablero de ajedrez periódico, la solución del problema de las ocho reinas tiene las configuraciones de energía cero del sistema hamiltoniano anterior, los dos primeros términos en el hamiltoniano representan las restricciones de fila y columna y los segundos dos representan la restricción en el De izquierda a derecha y de derecha a izquierda diagonales respectivamente.
Si está interesado en saber más, puede leer el documento de Dean y Parisi (‘Mecánica estadística de un sistema bidimensional con interacción de largo alcance’) en [cond-mat / 9711057v1] Mecánica estadística de un sistema bidimensional con sistema largo Interacción de rango.
Referencias
[1] Enfoque de Monte Carlo de conjunto extendido para problemas apenas relajantes
[2] [cond-mat / 9711057v1] Mecánica estadística de un sistema bidimensional con interacción de largo alcance.
