Return to Question

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 optimised somewhat to avoid investigating redundant combinations.

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.

UPDATE:

I realise that I can use uncurry to clean up notK...

 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.

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 optimised 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:

1. notC removes all spaces in the same column as the new queen.
2. notD removes any spaces on a diagonal from the new queen.
3. notK removes knight moves from the next two lines.

I feel that notK in particular could be implemented more cleanly and idiomatically. 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.

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 optimised 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:

1. notC removes all spaces in the same column as the new queen.
2. notD removes any spaces on a diagonal from the new queen.
3. notK removes 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.