- https://en.wikipedia.org/wiki/Eight_queens_puzzle
- Jak rozestavit šachové dámy na šachovnici n × n tak aby se nemohly vzít?
- Řešení budeme kódovat seznamy čísel a to tak, že čísla v seznamu určují pozice dam v odpovídajících sloupcích.
- Zavedeme funkci
da m n :: Int -> Int -> [[Int]], která bude počítat všechna řešení pro obdélníkovou matice s m sloupky a n řádky (m < n).
- Nová funkce bude řešení počítat rekurzivně, a to s využitím řešení pro šachovnici s (m-1) sloupky a
n řádky.
- Šachovnice s nula sloupky, má jedno triviální řešení:
[], tj. da 0 n = [[]]
- Rozhodnout, které pozice při rozšíření o jeden sloupek jsou při stávajícím rozložení dam nevyhovující.
hrozba :: [Int] -> [Int]
hrozba p = p ++ zipWith (+) p [1..] ++ zipWith (-) p [1..]
type Reseni = [Int]
damy :: Int -> [Reseni]
damy n = da n n
da :: Int -> Int -> [Reseni]
da 0 _ = [[]]
da m n = [ k:p | p <- da (m-1) n, k <- [1..n], nh k p] -- nh = neni hrozba
where nh k p = k `notElem` ( p
++ zipWith (+) p [1..]
++ zipWith (-) p [1..]
- Backtracking - rekurzivní generování všech možných řešení.
- Prořezávání - časná eliminace neplatných řešení (zde realizováno funkcí
nh k p)
- Tabulka adresovatelných míst pro uložení dat.
- Klíčovou vlastností je časově konstantní operace pro přístup k hodnotě na zadané adrese.
- Důležitá datová struktura v imperativním světě.
import Data.Array
- Binární typový konstruktor:
Array :: *->*->*
Array I A je typ všech polí, která jsou indexovaná hodnotami typu I a obsahují prvky A.- Typ použitý pro indexaci musí být instancí typové třídy
Ix.
array (1,4) [(1,'a'),(2,'b'),(3,'a'),(4,'b')] :: (Num i, Ix i) => Array i Char
- Instance typové třídy
Ix umožňují efektivní implementaci pole.
class (Ord) => Ix a where
range :: (a,a) -> [a]
index :: (a,a) -> a -> Int
inRange :: (a,a) -> a -> Bool
- Uspořádaná dvojice indexů tvoří meze pole.
(!) :: Ix i => Array i e -> i -> e
array (5,6) [(5,"ANO!"),(6,"NE1")] ! 5 ~>* "ANO!"
- Operace
// zkopíruje původní pole a při kopírování aktualizuje uvedený seznam dvojic (index, hodnota).
- –> Není konstantní operace!!!
(//) :: Ix i => Array i e -> [(i,e)] -> Array i e
array (1,2) [(1,1),(2,2)] // [(1,3),(2,3)] ~>* array (1,2) [(1,3),(2,3)]
-- Meze pole
bounds :: Ix i => Array i e -> (i,i)
-- Seznam indeců pole
indices :: Ix i => Array i e -> [i]
-- Převody mezi poli a seznamy
elems :: Ix i => Array i e -> [e]
listArray :: Ix i => (i,) -> [e] -> Array i e
-- Převody mezi poli a seznamy dvojic
assocs :: Ix i => Array i e -> [(i,e)]
array :: Ix i => (i,i) -> [(i,e)] -> Array i e
- Vytváří pole ze seznamu dvojic
(index,hodnota) a navíc akumuluje (funkcí foldl) prvky seznamu se stejným indexem.
accumArray :: Ix i => (e -> a -> e) -> e
-> (i, i) -> [(i, a)] -> Array i e
- Je-li akumulační funkce konstantní, pracuje v lineárním čase.
accumArray (+) 0 (1,2) [(1,1),(1,1),(1,1)]
~>* (1,2) [(1,3),(2,0)]
- Jsou-li čísla v seznamu z omezeného rozsahu, je možné tento seznam setřídit v lineárním čase.
max = 1000
countlist :: [Int] -> Array Int Int
countlist s = accumArray (+) 0 (0,max) (zip s (repeat 1))
sortBoundedList s = concant [ replicate k x | (x,k) <- assocs (countlist s) ]