Este equipo de redactores ha pasado mucho tiempo buscando la resolución a tu pregunta, te dejamos la respuestas por esto deseamos servirte de gran ayuda.
Solución:
Mi metaprograma encuentra las 92 soluciones. Se imprimen como mensajes de error:
error: ‘solution’ is not a member of ‘std::integral_constant’
Esto significa que la primera reina debe colocarse en y = 1, la segunda en y = 5, la tercera en y = 8 y así sucesivamente.
El metaprograma consta de dos metafunciones recursivas entre sí put_queen y put_queens:
#include
template
struct put_queen;
template
struct put_queens : std::integral_constant::value
| put_queen::value
| put_queen::value
| put_queen::value
| put_queen::value
| put_queen::value
| put_queen::value
| put_queen::value
> ;
template
struct put_queen : std::conditional<
// if blocked
rows & (1 << y)
|| sums & (1 << (x + y))
|| difs & (1 << (x - y + 8)),
// then backtrack
std::integral_constant,
// else recurse
put_queens
>::type ;
La variable queens almacena las coordenadas y de las reinas colocadas en el tablero hasta el momento. Las siguientes tres variables almacenan las filas y diagonales que ya están ocupadas por reinas.
x y y debe ser autoexplicativo.
El primer argumento para conditional comprueba si la posición actual está bloqueada. Si es así, retrocedemos devolviendo el resultado (sin sentido) 0. De lo contrario, la reina se coloca en el tablero y la recursión continúa con la siguiente columna.
Cuando x llega a 8, hemos encontrado una solución:
template
struct put_queens
// print solution as error message by accessing non-existent member
enum value = std::integral_constant::solution ;
;
Ya que integral_constant no tiene miembro solution, el compilador imprime queens como mensaje de error.
Para iniciar la recursividad, inspeccionamos el value miembro del tablero vacío:
int go = put_queens<0, 0, 0, 0, 0>::value;
El programa completo se puede encontrar en ideone.
Se me ocurrió una solución que utiliza el sistema de tipos Haskell. Busqué un poco en Google para encontrar una solución existente al problema a nivel de valor, lo cambió un poco y luego lo elevó al nivel de tipo. Fue necesario reinventarlo mucho. También tuve que habilitar un montón de extensiones 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:
data Zero -- type that represents zero
data S n -- type constructor that constructs the successor of another natural number
-- Some numbers shortcuts
type One = S Zero
type Two = S One
type Three = S Two
type Four = S Three
type Five = S Four
type Six = S Five
type Seven = S Six
type Eight = S Seven
El algoritmo que adapté hace sumas y restas en naturales, así que tuve que reinventarlos también. Las funciones a nivel de tipo se definen recurriendo 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 una manera similar a PROLOG.
class Add a b r | a b -> r -- last param is the result
instance Add Zero b b -- 0 + b = b
instance (Add a b r) => Add (S a) b (S r) -- S(a) + b = S(a + b)
class Sub a b r | a b -> r
instance Sub a Zero a -- a - 0 = a
instance (Sub a b r) => Sub (S a) (S b) r -- S(a) - S(b) = a - b
La recursividad se implementa con aserciones de clase, por lo que la sintaxis parece un poco al revés.
Los siguientes fueron los booleanos:
data True -- type that represents truth
data False -- type that represents falsehood
Y una función para hacer comparaciones de desigualdad:
class NotEq a b r | a b -> r
instance NotEq Zero Zero False -- 0 /= 0 = False
instance NotEq (S a) Zero True -- S(a) /= 0 = True
instance NotEq Zero (S a) True -- 0 /= S(a) = True
instance (NotEq a b r) => NotEq (S a) (S b) r -- S(a) /= S(b) = a /= b
Y listas …
data Nil
data h ::: t
infixr 0 :::
class Append xs ys r | xs ys -> r
instance Append Nil ys ys -- [] ++ _ = []
instance (Append xs ys rec) => Append (x ::: xs) ys (x ::: rec) -- (x:xs) ++ ys = x:(xs ++ ys)
class Concat xs r | xs -> r
instance Concat Nil Nil -- concat [] = []
instance (Concat xs rec, Append x rec r) => Concat (x ::: xs) r -- concat (x:xs) = x ++ concat xs
class And l r | l -> r
instance And Nil True -- and [] = True
instance And (False ::: t) False -- and (False:_) = False
instance (And t r) => And (True ::: t) r -- and (True:t) = and t
ifs también faltan en el nivel de tipo …
class Cond c t e r | c t e -> r
instance Cond True t e t -- cond True t _ = t
instance Cond False t e e -- cond False _ e = e
Y con eso, toda la maquinaria de apoyo que usé estaba en su lugar. ¡Es hora de abordar el problema en sí!
Comenzar con una función para probar si agregar una reina a un tablero existente está bien:
-- Testing if it's safe to add a queen
class Safe x b n r | x b n -> r
instance Safe x Nil n True -- safe x [] n = True
instance (Safe x y (S n) rec,
Add c n cpn, Sub c n cmn,
NotEq x c c1, NotEq x cpn c2, NotEq x cmn c3,
And (c1 ::: c2 ::: c3 ::: rec ::: Nil) r) => Safe x (c ::: y) n r
-- safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
Observe el uso de aserciones de clase para obtener resultados intermedios. Debido a que los valores devueltos son en realidad un parámetro adicional, no podemos simplemente llamar a las aserciones directamente entre sí. Nuevamente, si ha usado PROLOG antes, puede que este estilo le resulte un poco familiar.
Después de realizar algunos cambios para eliminar la necesidad de lambdas (que podría haber implementado, pero decidí dejarlo para otro día), así es como se veía la solución original:
queens 0 = [[]]
-- The original used the list monad. I "unrolled" bind into concat & map.
queens n = concat $ map f $ queens (n-1)
g y x = if safe x y 1 then [x:y] else []
f y = concat $ map (g y) [1..8]
map es una función de orden superior. Pensé implementar metafunciones de orden superior sería demasiado complicado (de nuevo las lambdas), así que opté por una solución más simple: como sé qué funciones se asignarán, puedo implementar versiones especializadas de map para cada uno, de modo que no sean funciones de orden superior.
-- Auxiliary meta-functions
class G y x r | y x -> r
instance (Safe x y One s, Cond s ((x ::: y) ::: Nil) Nil r) => G y x r
class MapG y l r | y l -> r
instance MapG y Nil Nil
instance (MapG y xs rec, G y x g) => MapG y (x ::: xs) (g ::: rec)
-- Shortcut for [1..8]
type OneToEight = One ::: Two ::: Three ::: Four ::: Five ::: Six ::: Seven ::: Eight ::: Nil
class F y r | y -> r
instance (MapG y OneToEight m, Concat m r) => F y r -- f y = concat $ map (g y) [1..8]
class MapF l r | l -> r
instance MapF Nil Nil
instance (MapF xs rec, F x f) => MapF (x ::: xs) (f ::: rec)
Y la última metafunción se puede escribir ahora:
class Queens n r | n -> r
instance Queens Zero (Nil ::: Nil)
instance (Queens n rec, MapF rec m, Concat m r) => Queens (S n) r
Todo lo que queda es algún tipo de controlador para convencer a la maquinaria de verificación de tipos para que resuelva las soluciones.
-- dummy value of type Eight
eight = undefined :: Eight
-- dummy function that asserts the Queens class
queens :: Queens n r => n -> r
queens = const undefined
Se supone que este metaprograma se ejecuta en el verificador de tipos, por lo que se puede iniciar ghci y pregunte por el tipo de queens eight:
> :t queens eight
Esto excederá el límite de recursividad predeterminado bastante rápido (es un miserable 20). Para aumentar este límite, necesitamos invocar ghci con el -fcontext-stack=N opción, donde N es 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 arreglé para correr hasta queens four.
Hay un programa completo en ideone con algo de maquinaria para imprimir bastante los tipos de resultados, pero solo hay queens two se puede ejecutar sin exceder los límites 🙁
C, a través del preprocesador
Creo que el comité ANSI tomó la decisión consciente de no extender el preprocesador C hasta el punto de ser Turing completo. En cualquier caso, no es lo suficientemente poderoso para resolver el problema de las ocho reinas. No de una manera generalizada.
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 autoinclusión (a través de #include __FILE__) para obtener un tipo limitado de recursividad.
#ifdef i
# if (r_(i) & 1 << j_(i)) == 0 && (p_(i) & 1 << i + j_(i)) == 0
&& (n_(i) & 1 << 7 + i - j_(i)) == 0
# if i == 0
# undef i
# define i 1
# undef r1
# undef p1
# undef n1
# define r1 (r0 | (1 << j0))
# define p1 (p0 | (1 << j0))
# define n1 (n0 | (1 << 7 - j0))
# undef j1
# define j1 0
# include __FILE__
# undef j1
# define j1 1
# include __FILE__
# undef j1
# define j1 2
# include __FILE__
# undef j1
# define j1 3
# include __FILE__
# undef j1
# define j1 4
# include __FILE__
# undef j1
# define j1 5
# include __FILE__
# undef j1
# define j1 6
# include __FILE__
# undef j1
# define j1 7
# include __FILE__
# undef i
# define i 0
# elif i == 1
# undef i
# define i 2
# undef r2
# undef p2
# undef n2
# define r2 (r1 | (1 << j1))
# define p2 (p1 | (1 << 1 + j1))
# define n2 (n1 | (1 << 8 - j1))
# undef j2
# define j2 0
# include __FILE__
# undef j2
# define j2 1
# include __FILE__
# undef j2
# define j2 2
# include __FILE__
# undef j2
# define j2 3
# include __FILE__
# undef j2
# define j2 4
# include __FILE__
# undef j2
# define j2 5
# include __FILE__
# undef j2
# define j2 6
# include __FILE__
# undef j2
# define j2 7
# include __FILE__
# undef i
# define i 1
# elif i == 2
# undef i
# define i 3
# undef r3
# undef p3
# undef n3
# define r3 (r2 | (1 << j2))
# define p3 (p2 | (1 << 2 + j2))
# define n3 (n2 | (1 << 9 - j2))
# undef j3
# define j3 0
# include __FILE__
# undef j3
# define j3 1
# include __FILE__
# undef j3
# define j3 2
# include __FILE__
# undef j3
# define j3 3
# include __FILE__
# undef j3
# define j3 4
# include __FILE__
# undef j3
# define j3 5
# include __FILE__
# undef j3
# define j3 6
# include __FILE__
# undef j3
# define j3 7
# include __FILE__
# undef i
# define i 2
# elif i == 3
# undef i
# define i 4
# undef r4
# undef p4
# undef n4
# define r4 (r3 | (1 << j3))
# define p4 (p3 | (1 << 3 + j3))
# define n4 (n3 | (1 << 10 - j3))
# undef j4
# define j4 0
# include __FILE__
# undef j4
# define j4 1
# include __FILE__
# undef j4
# define j4 2
# include __FILE__
# undef j4
# define j4 3
# include __FILE__
# undef j4
# define j4 4
# include __FILE__
# undef j4
# define j4 5
# include __FILE__
# undef j4
# define j4 6
# include __FILE__
# undef j4
# define j4 7
# include __FILE__
# undef i
# define i 3
# elif i == 4
# undef i
# define i 5
# undef r5
# undef p5
# undef n5
# define r5 (r4 | (1 << j4))
# define p5 (p4 | (1 << 4 + j4))
# define n5 (n4 | (1 << 11 - j4))
# undef j5
# define j5 0
# include __FILE__
# undef j5
# define j5 1
# include __FILE__
# undef j5
# define j5 2
# include __FILE__
# undef j5
# define j5 3
# include __FILE__
# undef j5
# define j5 4
# include __FILE__
# undef j5
# define j5 5
# include __FILE__
# undef j5
# define j5 6
# include __FILE__
# undef j5
# define j5 7
# include __FILE__
# undef i
# define i 4
# elif i == 5
# undef i
# define i 6
# undef r6
# undef p6
# undef n6
# define r6 (r5 | (1 << j5))
# define p6 (p5 | (1 << 5 + j5))
# define n6 (n5 | (1 << 12 - j5))
# undef j6
# define j6 0
# include __FILE__
# undef j6
# define j6 1
# include __FILE__
# undef j6
# define j6 2
# include __FILE__
# undef j6
# define j6 3
# include __FILE__
# undef j6
# define j6 4
# include __FILE__
# undef j6
# define j6 5
# include __FILE__
# undef j6
# define j6 6
# include __FILE__
# undef j6
# define j6 7
# include __FILE__
# undef i
# define i 5
# elif i == 6
# undef i
# define i 7
# undef r7
# undef p7
# undef n7
# define r7 (r6 | (1 << j6))
# define p7 (p6 | (1 << 6 + j6))
# define n7 (n6 | (1 << 13 - j6))
# undef j7
# define j7 0
# include __FILE__
# undef j7
# define j7 1
# include __FILE__
# undef j7
# define j7 2
# include __FILE__
# undef j7
# define j7 3
# include __FILE__
# undef j7
# define j7 4
# include __FILE__
# undef j7
# define j7 5
# include __FILE__
# undef j7
# define j7 6
# include __FILE__
# undef j7
# define j7 7
# include __FILE__
# undef i
# define i 6
# elif i == 7
printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)n",
j0 + 1, j1 + 1, j2 + 1, j3 + 1, j4 + 1, j5 + 1, j6 + 1, j7 + 1);
# endif
# endif
#else
#include
#define _cat(a, b) a ## b
#define j_(i) _cat(j, i)
#define n_(i) _cat(n, i)
#define p_(i) _cat(p, i)
#define r_(i) _cat(r, i)
int main(void)
# define i 0
# define j0 0
# include __FILE__
# undef j0
# define j0 1
# include __FILE__
# undef j0
# define j0 2
# include __FILE__
# undef j0
# define j0 3
# include __FILE__
# undef j0
# define j0 4
# include __FILE__
# undef j0
# define j0 5
# include __FILE__
# undef j0
# define j0 6
# include __FILE__
# undef j0
# define j0 7
# include __FILE__
# undef j0
return 0;
#endif
A pesar de la horrible cantidad de contenido repetitivo, permítanme asegurarles 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 de datos de pila desplegable general. El resultado es que tuve que codificar el valor de i donde sea que se utilizó para seleccionar otro valor para establecer. (A diferencia de la recuperación de valores, que podría hacerse de forma completamente general. Por eso #if en la parte superior del archivo, que es lo que decide si se puede agregar una reina en la posición actual, no necesitaba repetirse ocho veces).
Dentro del código del preprocesador, i y j indicar la posición actual que se está considerando, mientras r, p, y n Realice un seguimiento de los rangos y diagonales que actualmente no están disponibles para su ubicación. Sin embargo, i también funciona como el contador que marca la profundidad actual de la recursividad, por lo que realmente todos los demás valores 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í:
/* ... #included content from ... */
int main(void)
printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)n",
0 + 1, 4 + 1, 7 + 1, 5 + 1, 2 + 1, 6 + 1, 1 + 1, 3 + 1);
printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)n",
0 + 1, 5 + 1, 7 + 1, 2 + 1, 6 + 1, 3 + 1, 1 + 1, 4 + 1);
printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)n",
0 + 1, 6 + 1, 3 + 1, 5 + 1, 7 + 1, 1 + 1, 4 + 1, 2 + 1);
/* ... 88 more solutions ... */
printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)n",
7 + 1, 3 + 1, 0 + 1, 2 + 1, 5 + 1, 1 + 1, 6 + 1, 4 + 1);
return 0;
Se puede hacer, aunque claramente no debería.
Reseñas y calificaciones
Recuerda que puedes dar difusión a esta crónica si si solucionó tu problema.