1votos

Problema de las ocho reinas en Haskell

por josejuan hace 1 año

Por un poquito más podemos hacerlo eficiente (calcula hasta n~15 en tiempo razonable).

La idea central es colocar ocho reinas en un tablero de ajedrez, sin que se estas se amenacen entre si.

1
reinas n = r n[][]where r 0 x _=[x];r z x u=[1..n]\\x>>=(\t->let w=[t-z,n*(t+z)]in guard(w\\u==w)>>r(z-1)(t:x)(w++u)) 
5 comentarios
0votos

Escrito por josejuan hace 1 año

Por ejemplo, tiempos para encontrar UNA solución de tamaños 11, 20 y 30:
[josejuan@centella Solveet]$ time -f "%e" ./reinas 0 1 11
[10,8,6,4,2,11,9,7,5,3,1]
0.27 segundos

[josejuan@centella Solveet]$ time -f "%e" ./reinas 0 1 20
[11,6,14,7,10,8,19,16,9,17,20,18,12,15,13,4,2,5,3,1]
2.87 segundos

[josejuan@centella Solveet]$ time -f "%e" ./reinas 0 1 30
[19,21,14,17,20,18,6,8,10,12,16,29,27,30,24,22,25,28,26,23,7,15,13,11,9,4,2,5,3,1]
1518.40 segundos
0votos

Escrito por AverageUser hace 1 año

Me esta costando trabajo entenderlo xD. Backtrack?
0votos

Escrito por josejuan hace 1 año

Es básicamente tu mismo filtro, pero para mantener una única variable (y sea más corto) multiplico uno de los índices de diagonal por `n`, luego al trabajar sobre conjuntos (\\) se hace innecesario el `nub`. Por lo demás sí, un backtrack, pero explícitamente sobre la mónada de listas (el =[x] es realmente un `return x` pero así es más corto). `guard` aplica el filtro en la mónada.

Una versión (no probada) legible podría ser:
reinas n = rec n [] [] []
  where rec 0 xs _  _  = return xs                  -- la mónada lista acumula `xs` (más listas)
        rec z xs us vs = do
                            d <- [1..n] \\ xs       -- sobre filas no usadas
                            let u = d - z           -- índice de la diagonal negativa
                                v = d + z           -- índice de la diagonal positiva
                            guard $                 -- diagonal libre o backtrack
                              not (u `elem` us || v `elem` vs)
                            rec (z - 1) (u: us) (v: vs)
0votos

Escrito por AverageUser hace 1 año

Creo comprender, y me gusta. Cual crees que es el coste para solo una solución?
0votos

Escrito por josejuan hace 1 año

Si hubiera un patrón, al ejecutarlo para 1.. habría uniformidad pero no la hay, los tiempos para n=4.. son 0.06, 0.05, 0.35, 0.16, 0.26, 0.35, 0.33, 0.23, 0.28, 0.31, 0.26, 0.30, 0.44, 0.43, 0.84, 0.41, 2.89, 0.51, 26.05, 0.64, 7.62, 1.02 por lo que ya se ve que hay instancias para las que usar [1..n] tarda en encontrar la primera pero en https://en.wikipedia.org/wiki/Eightqueenspuzzle#Explicit_solutions ya nos dicen que es posible encontrar soluciones fijas sin dificultad.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.