Declaratieve Talen/Oplossing haskell nqueens

Ga naar: navigatie, zoeken

Mogelijke oplossing

nqueens::Int->[Int]
-------------------
nqueens n = let
		list = [1..n]
		permlist = perms list
	     in
		getoklist permlist


getoklist::[[Int]]->[Int]
------------------------
getoklist [] = error "geen oplossing"
getoklist (x:xs) | listok x = x
		 | otherwise = getoklist xs


listok::[Int]->Bool
-------------------
listok [] = True
listok (a:as) = if (listok2 a as 1) == False then False
		else listok as
				
listok2::Int->[Int]->Int->Bool
------------------------------
listok2 _ [] _ = True
listok2 a (b:bs) kol | a == (b+kol) = False
		     | a == (b-kol) = False
		     | otherwise =  listok2 a bs (kol+1)
				 
					 
					 
--Permuteer de lijst
perms :: [k] -> [[k]]
---------------------
perms [] = [[]]
perms (x:xs) = concat (map (tussen x) (perms xs)) where 
            tussen e [] = [[e]]
            tussen e (y:ys) = (e:y:ys) : map (y:) (tussen e ys)

Een alternatief

nqueens::Int->[Int]
nqueens n =
	let
		permutaties = permuteer [1..n]
		oplossingen = [p | p<-permutaties, (mog_oplossing p) == True]
	in head oplossingen

permuteer::[Int]->[[Int]]
permuteer [] = [[]]
permuteer rij = [x:xs | x<-rij, xs<-permuteer (filter (/=x) rij)]

mog_oplossing::[Int]->Bool
mog_oplossing rij =
	let
		indexen = get_indexen rij 1
	in voldoet indexen []

-- nog af te gaan, reeds afgegaan
voldoet::[Int]->[Int]->Bool
voldoet [] _ = True
voldoet (x:xs) rij =
	if (elem x rij) then False
	else if ((check_diagonaal (x-2) rij) == False) then False
	     else voldoet xs ([x]++rij)

get_indexen::[Int]->Int->[Int]
get_indexen [] _ = []
get_indexen (x:xs) w =
	let
		n_x = x + w
	in [n_x] ++ (get_indexen xs (w+1))

check_diagonaal::Int->[Int]->Bool
check_diagonaal _ [] = True
check_diagonaal n (x:xs) =
	if n == x then False
	else check_diagonaal (n-2) xs

nog een alternatief

(alle oplossingen)

nqueens::Int->[[Int]]
nqueens n = [opl | opl<-(permuteer [1..n]), (safe opl) == True]
	
permuteer::[Int]->[[Int]]
permuteer [] = [[]]
permuteer rij = [x:xs | x<-rij, xs<-permuteer (filter (/=x) rij)]

safe [] = True
safe (x:xs) = (no_attack x xs 1) && (safe xs)

no_attack _ [] _ = True
no_attack x (l:ls) n = not (x == n + l) && not (l==x+n) && not (x==l) && no_attack x ls (n+1)

Ik heb nog iets korters gevonden

--Eerste argument is het aantal queens, het tweede de grootte van het bord
queens 0 _ = [[]]
queens n b = [x:y | y <- queens (n-1) b, x <- [1..b], safe x y 1]
	where 	safe x [] n = True
		safe x (c:y) n = and [x/=c,x/=c+n,x/=c-n,safe x y (n+1)]