This is one of my Haskell solutions to a variation of the N-Queens problem, where the queens can move like knights in addition to their normal moves. It has been optimized somewhat to avoid investigating redundant combinations.
place :: Int -> [[Int]] place 0 = [] place n = go $ take n $ repeat [1..n] where go  = [] go (row:rest) = do q <- row qs <- go $ safe q rest return (q : qs) safe q = notK q . notD q . notC q notC q = map (filter (/= q)) notD q = (map (\(x, r) -> filter (\y -> abs(y - q) /= x) r)) . (zip [1..]) notK q = map (\(f, r) -> filter f r) . (zip (kFilters q)) kFilters q = (\x -> abs (x - q) /= 2) : (\x -> abs (x - q) > 1) : (repeat (const True)) solutions = length . place main = do n <- readLn putStrLn $ show $ solutions n
I am satisfied with the performance, but I feel there must be a more elegant way to apply a series of functions (in this case, filters) to a list.
In each iteration of the recursive function
go, the top row of the board is selected and then for each position in sequence a queen is positioned and the function recurs with a filtered copy of the rest of the board, so that each iteration has only safe squares to choose from. The
safe function applies three filters to the board:
notCremoves all spaces in the same column as the new queen.
notDremoves any spaces on a diagonal from the new queen.
notKremoves knight moves from the next two lines.
I feel that
notK in particular could be implemented more cleanly and idiomatically but I couldn't see a better way to apply one function to the first item of a list, another to the second and something else to the rest. And using
zip does save me from having to check for the end of the board.
I wouldn't be surprised if there is a better way to write
notD. So I am looking for more expressive ways to apply a sequence of varying functions to successive list items.
I realise that I can use
uncurry to clean up
notK q = map (uncurry filter) . (zip (kFilters q))
and the two filters in Kfilters can be written in dot notation...
((/= 2) . abs . subtract q) : ((/= 1) . abs . subtract q) : ...
which allows the kFilters line to be rendered as
kFilters = (f 2) : (f 1) : (repeat (const True))
but this doesn't actually change my original question. I'm still looking for a better mechanism for applying a varying sequence of functions to a list.