¿Puedes resolver el rompecabezas de las ocho reinas en tiempo de compilación?
Elija cualquier formato de salida adecuado.
Estoy particularmente interesado en una solución de metaprogramación de plantilla C ++, pero puede usar lenguajes que tengan construcciones similares, como, por ejemplo, el sistema de tipos de Haskell.
Idealmente, su metaprograma generaría todas las soluciones. Sin codificación.
puzzle-solver
compile-time
R. Martinho Fernandes
fuente
fuente
Respuestas:
Mi metaprograma encuentra las 92 soluciones. Se imprimen como mensajes de error:
Esto significa que la primera reina debe colocarse en y = 1, la segunda en y = 5, la tercera en y = 8 y así sucesivamente.
Primero, algunas metafunciones útiles:
Luego, dos metafunciones interesantes (tenga en cuenta el singular y el plural):
La variable
queensalmacena las coordenadas y de las reinas colocadas en el tablero hasta ahora. Las siguientes tres variables almacenan las filas y diagonales que ya están ocupadas por reinas.xyydebe explicarse por sí mismo.El primer argumento para
if_then_elseverificar si la posición actual está bloqueada. Si es así, la recursión se detiene devolviendo el resultado (sin sentido) 0. De lo contrario, la reina se coloca en el tablero y el proceso continúa con la siguiente columna.Cuando x alcanza 8, hemos encontrado una solución:
Como la
printplantilla no tiene miembrosolution, el compilador genera un error.Y finalmente, para comenzar el proceso, inspeccionamos al
valuemiembro del tablero vacío:El programa completo se puede encontrar en ideone .
fuente
Se me ocurrió una solución que utiliza el sistema de tipo Haskell. Busqué en Google un poco para una solución existente al problema en el nivel de valor , lo cambié un poco y luego lo elevé al nivel de tipo. Tomó mucho reinventar. También tuve que habilitar un montón de extensiones de GHC.
Primero, dado que los números enteros no están permitidos en el nivel de tipo, necesitaba reinventar los números naturales una vez más, esta vez como tipos:
El algoritmo que adapté hace sumas y restas en naturales, así que tuve que reinventarlas también. Las funciones en el nivel de tipo se definen con el recurso a clases de tipo. Esto requiere las extensiones para múltiples clases de tipos de parámetros y dependencias funcionales. Las clases de tipos no pueden "devolver valores", por lo que usamos un parámetro adicional para eso, de manera similar a PROLOG.
La recursión se implementa con aserciones de clase, por lo que la sintaxis parece un poco hacia atrás.
Lo siguiente fueron los booleanos:
Y una función para hacer comparaciones de desigualdad:
Y listas ...
ifs también faltan en el nivel de tipo ...Y con eso, toda la maquinaria de soporte que usé estaba en su lugar. ¡Es hora de abordar el problema en sí!
Comenzando con una función para probar si agregar una reina a un tablero existente está bien:
Observe el uso de aserciones de clase para obtener resultados intermedios. Debido a que los valores de retorno son en realidad un parámetro adicional, no podemos simplemente llamar a las aserciones directamente entre sí. Nuevamente, si ha usado PROLOG antes, puede encontrar este estilo un poco familiar.
Después de hacer algunos cambios para eliminar la necesidad de lambdas (que podría haber implementado, pero decidí irme para otro día), así es como se veía la solución original:
mapEs una función de orden superior. Pensé que implementar metafunciones de orden superior sería demasiado complicado (nuevamente las lambdas), así que decidí una solución más simple: como sé qué funciones se asignarán, puedo implementar versiones especializadasmappara cada una, de modo que no funciones de orden superior.Y la última metafunción se puede escribir ahora:
Todo lo que queda es algún tipo de controlador para persuadir a la maquinaria de verificación de tipos para encontrar las soluciones.
Se supone que este metaprograma se ejecuta en el verificador de tipo, por lo que se puede iniciar
ghciy solicitar el tipo dequeens eight:Esto excederá el límite de recursión predeterminado bastante rápido (es un mísero 20). Para aumentar este límite, necesitamos invocar
ghcicon la-fcontext-stack=Nopción, dondeNestá la profundidad de pila deseada (N = 1000 y quince minutos no es suficiente). Todavía no he visto esta ejecución completa, ya que lleva mucho tiempo, pero me las he arreglado para hacerloqueens four.Hay un programa completo en ideone con algo de maquinaria para imprimir bonitos los tipos de resultados, pero solo
queens twopuede ejecutarse sin exceder los límites :(fuente
C, a través del preprocesador
Creo que el comité ANSI tomó una decisión consciente de no extender el preprocesador C hasta el punto de ser Turing completo. En cualquier caso, no es lo suficientemente poderoso como para resolver el problema de las ocho reinas. No de ninguna manera general.
Pero se puede hacer si está dispuesto a codificar los contadores de bucle. No hay una forma real de bucle, por supuesto, pero puede usar la auto inclusión (vía
#include __FILE__) para obtener un tipo limitado de recursión.A pesar de la horrible cantidad de contenido repetitivo, déjame asegurarte que realmente está resolviendo el problema de las ocho reinas algorítmicamente. Desafortunadamente, lo único que no pude hacer con el preprocesador es implementar una estructura general de datos de pila push-down. El resultado es que tuve que codificar el valor de
idonde sea que fue utilizado para seleccionar otro valor para establecer. (A diferencia de la recuperación de valores, lo que se puede hacer de forma general. Por eso,#ifen la parte superior del archivo, que es lo que decide si se puede agregar una reina en la posición actual, no es necesario repetirla ocho veces).Dentro del código de preprocesador,
iyjindicar la posición actual que está siendo considerado, mientras quer,pynno perder de vista lo que filas y diagonales están disponibles actualmente para su colocación. Sin embargo,itambién funciona como el contador que marca la profundidad de recursión actual, por lo que realmente todos los demás valores realmente usan i como una especie de subíndice, de modo que sus valores se conservan cuando se reanuda desde una recursividad. (Y también debido a la seria dificultad de modificar el valor de un símbolo de preprocesador sin reemplazarlo por completo).El programa compilado imprime las 92 soluciones. Las soluciones están integradas directamente en el ejecutable; la salida del preprocesador se ve así:
Se puede hacer, aunque claramente no debería.
fuente
Aquí hay una solución C ++ 11 sin ninguna plantilla:
La solución está codificada como dígitos decimales, como en las respuestas de FredOverflow. GCC 4.7.1 compila el archivo anterior en la siguiente fuente de ensamblaje con
g++ -S -std=c++11 8q.cpp:El valor del símbolo
placeses 84136275, es decir, la primera reina está en a8, la segunda en b4, etc.fuente
plantilla c ++, con solo una clase de plantilla definida:
entonces el mensaje de error se verá así:
error C2440: 'type cast': no se puede convertir de 'int' a 'char [15863724]'
fuente