Ancora regine

Ed ecco un nuovo post funzionale. Oggi non mi sforzerò più di tanto perché vi propongo la soluzione in Haskell del problema delle regine, di cui avevo già parlato qualche eone fa, ricordate? No, allora ripeto velocemente.

Lo so, non c'entra niente con il post, ma Elisabetta I è la regina par excellence, no?

Avete una scacchiera NxN e dovete piazzare N regine in modo che non si possano catturare a vicenda. Il problema ha zero soluzioni per N minore di 4, una soluzione per N uguale a 4, un numero crescente di soluzioni al crescere di N.

Nello scorso post vi ho chiesto di mettere nei commenti le vostre implementazioni in vari linguaggi di programmazione, e ne sono arriva un po’, da Mathematica a Ruby passando per il Pascal! Grazie al buon Dikiyvolk e a HopfMap! Nessuno però mi ha tolto le soluzioni equivalenti per rotazione e le soluzioni speculari. E allora oggi vi propongo la mia soluzione in Haskell che vi fornisce anche le soluzioni uniche.

Per prima cosa, come rappresento una soluzione? Nel programma C dello scorso post creavo una matrice di caratteri NxN che mi rappresentava la scacchiera. Ma naturalmente non è l’unico modo di rappresentare una soluzione. Un altro modo è di rappresentare la posizione di una regina con le sue coordinate x e y sulla schacchiera; e una soluzione come una lista di N regine. Per cui, ad esempio, nel caso di N = 4, una soluzione è la seguente:

[[(0,2),(1,0),(2,3),(3,1)]]

Le coordinate x e y naturalmente vanno da 0 a N-1. Non è molto accattivante dal punto di vista visivo, ma è una lista, e si tratta molto bene in Haskell!
E allora, bando alle ciance, ecco il programino.

module Main where
import Data.List
import Data.Ord
import Data.Function

dim = 4

main = 
  do putStrLn ("Solutions:     " ++ (show (length queens)) ++ "\n" ++ (show (queens)))
     putStrLn ("No duplicates: " ++ (show (length queensnd)) ++ "\n" ++ (show (queensnd)))

-- true se le due regine non sono in conflitto
noconflict (x1,y1) (x2,y2) = (abs(x1-x2) /= abs(y1-y2)) && (x1 /= x2) && (y1 /= y2)  

-- true se la posizione (x, y) è ammissibile rispetto alla lista di regine
allow l (x,y) = and (map (noconflict (x,y)) l)

-- piazza le regine in tutti i modi possibili nelle righe da 0 a i inclusa
-- restituisce la lista delle soluzioni 
-- (ogni soluzione è una lista di i posizioni)
myqueens :: Int -> [[(Int,Int)]]
myqueens i 
  | i == 0    = all_pos_in_row 0 []
  | otherwise = [ x ++ y | x <- (myqueens (i-1)), y <- (all_pos_in_row i x) ] 
    where all_pos_in_row r list = group(filter (allow list) [ (r,c) | c <- [0..(dim-1)] ])

-- chiama myqueens su dim-1, seleziona (con filter) le soluzioni di lunghezza 
-- dim (quindi quelle in cui ci sono dim regine), 
queens = (filter (\x -> (length x) == dim) (myqueens (dim-1)))

-- e da queste elimina quelle 
-- identiche per rotazioni e riflessioni chiamando la funzione edup definita
-- più sotto 
queensnd = edup queens

-- ruota una soluzione in senso orario di 90 gradi
rotate list = sortBy (compare `on` fst) [(y, dim-1-x) | (x, y) <- list ]
-- produce la soluzione riflessa
spec list = [ (x, dim-1-y) | (x, y) <- list ]
                                        
--- una prova con foldr e scanr                          
edup list = foldr (reflrot) [] (list)
  where reflrot x l = if (rotate x) `elem` l || 
                         (rotate (rotate x)) `elem` l ||
                         (rotate (rotate (rotate x))) `elem` l ||
                         (spec x) `elem` l
                      then l 
                      else l ++ [x]

Allora, al solito per compilare basta scrivere sul terminale:

ghc queens.hs

dove queens.hs è il nome che avrete dato al file. E

./queens

per eseguire.

Il programma ha più commenti che linee di codice. E questa è una delle particolarità di Haskell: il codice viene sempre molto succinto, forse a causa della sintassi particolare, forse a causa del fatto che è un linguaggio funzionale che ti obbliga ad essere succinto!

Brevemente, la funzione che ha bisogno di essere spiegata di più è forse myqueens. Questa si realizza con una serie di funzioni di appoggio:

  • all_pos_in_row: cerca di piazzare in tutti i modi legali possibili delle regine sulla riga r. In output quindi da una lista di soluzioni parziali (con le regine messe fino alla riga r). Quando r è 0, genera dim soluzioni parziali del tipo [(0,0)], [(0,1)], [(0,2)] ecc. Quando r è maggiore di 0, gli vengono passate anche le soluzioni parziali precedenti, e lei seleziona solo quelle ammissibili. Ad esempio per r pari a 1, genera [(0,0),(1,2)], [(0,0),(1,3)], [(0,1), (1,3)], ecc.
  • Per capire quali soluzioni sono legali, si usa la funzione allow, definita più su, che a sua volta usa la funzione noconflict

Ok, adesso, per generare tutte le soluzioni, non resta che chiamare myqueens (dim-1), e selezionare solo quelle che contengono almeno dim regine! E con questo abbiamo già finito.

Ma se vogliamo anche eliminare le soluzioni equivalenti per rotazione e riflessione, beh, quello lo fa la funzione queensnd, che prima calcola tutte le soluzioni chiamando queens, e poi elimina quelle equivalenti. Come? Innanzitutto, mi sono definito le funzioni spec e rotate per fare il riflesso e la rotazione di 90 gradi di una soluzione (notare che dopo una rotazione, riordino le posizioni in base alla riga, ovvero al primo elemento della coppia (x,y)). Dopodiché, la funzione edup fa l’eliminazione, facendo un’operazione di reduce (inversa della map!) tramite la foldr che utilizza la funzione reflrot per eliminare man mano le soluzioni equivalenti.

Alcune considerazioni

  • Nel main, queens viene chiamata 2 volte: direttamente la prima volta, indirettamente dalla queensnd la second volta. Ebbene, Haskell fa il calcolo una volta sola, e memorizza il risultato in una cache, così la seconda volta se lo trova già pronto. Può farlo perché queens è una funzione pura: non ha side effects, quindi ogni volta che la chiami produce sempre lo stesso risultato!
  • questa proprietà che le funzioni pure non influenzano lo stato globale, e quindi ritornano sempre gli stessi valori a parità di parametri, è una proprietà importantissima che rende i linguaggi funzionali estremamente interessanti per la programmazione concorrente e parallela, e in particolare per evitare race conditions e strani errori di concorrenza. Ma di questo ne parlerò in un post futuro.

Ok, per stasera ho chiuso! Se avete dubbi sul programma, chiedete e vi sarà risposto!

About these ads
Posta un commento o usa questo indirizzo per il trackback.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 63 follower

%d blogger cliccano Mi Piace per questo: