I wrote a Haskell program to solve the N-queens problem by bruteforce. It works and I find it reasonably readable

But it is pretty slow:

• 5 seconds for one solution of 8 queens.
• 1 minute for one solution for 9 queens.

I would like to hear both improvements on readability and performance:

import Control.Monad
import Data.List

-- True indicates that there is a queen, False that there is not.
type QueenBoard = [[Bool]]

count   :: Eq a => a -> [a] -> Int
count x =  length . filter (==x)

fAnd :: (a -> Bool) -> (a -> Bool) -> (a -> Bool)
fAnd = liftM2 (&&)

rotate90 :: [[a]] -> [[a]]
rotate90 = map reverse . transpose

noQueensinSameRow :: QueenBoard -> Bool
noQueensinSameRow board = not (any (\row -> count True row > 1) board)

noQueensinSameColumn :: QueenBoard -> Bool
noQueensinSameColumn = noQueensinSameRow . rotate90

-- Attribution to http://stackoverflow.com/questions/32465776/getting-all-the-diagonals-of-a-matrix-in-haskell
diagonals :: [[a]] -> [[a]]
diagonals []       = []
diagonals ([]:xss) = xss
diagonals xss      = zipWith (++) (map ((:[]) . head) xss ++ repeat [])
                                  ([]:(diagonals (map tail xss)))

allDiagonals :: [[a]] -> [[a]]
allDiagonals xss = (diagonals xss) ++ (diagonals (rotate90 xss))

noQueensinSameDiagonal :: QueenBoard -> Bool
noQueensinSameDiagonal = noQueensinSameRow . allDiagonals

isQueenSolution :: QueenBoard -> Bool
isQueenSolution = (noQueensinSameRow `fAnd` noQueensinSameColumn `fAnd` noQueensinSameDiagonal)

allFalseOneTrue :: Int -> [[Bool]]
allFalseOneTrue length = nub $ permutations ( [True] ++ (replicate (length - 1) False) )

allProduct = sequence :: [[a]] -> [[a]]

allPossibleBoards :: Int -> [QueenBoard]
allPossibleBoards size = allProduct (replicate size (allFalseOneTrue size))

solveQueens :: Int -> [QueenBoard]
solveQueens = (filter isQueenSolution) . allPossibleBoards

main :: IO()
main = mapM_ putStrLn $ map show $ head $ solveQueens 8

I wrote a Haskell program to solve the N-queens problem by bruteforce. It works and I find it reasonably readable

But it is pretty slow:

• 5 seconds for one solution of 8 queens.
• 1 minute for one solution for 9 queens.
• Crash for 10 queens. I fear that allFalseOneTrue gives memory problems as it uses permutations.

I would like to hear both improvements on readability and performance:

import Control.Monad
import Data.List

-- True indicates that there is a queen, False that there is not.
type QueenBoard = [[Bool]]

count   :: Eq a => a -> [a] -> Int
count x =  length . filter (==x)

fAnd :: (a -> Bool) -> (a -> Bool) -> (a -> Bool)
fAnd = liftM2 (&&)

rotate90 :: [[a]] -> [[a]]
rotate90 = map reverse . transpose

noQueensinSameRow :: QueenBoard -> Bool
noQueensinSameRow board = not (any (\row -> count True row > 1) board)

noQueensinSameColumn :: QueenBoard -> Bool
noQueensinSameColumn = noQueensinSameRow . rotate90

-- Attribution to http://stackoverflow.com/questions/32465776/getting-all-the-diagonals-of-a-matrix-in-haskell
diagonals :: [[a]] -> [[a]]
diagonals []       = []
diagonals ([]:xss) = xss
diagonals xss      = zipWith (++) (map ((:[]) . head) xss ++ repeat [])
                                  ([]:(diagonals (map tail xss)))

allDiagonals :: [[a]] -> [[a]]
allDiagonals xss = (diagonals xss) ++ (diagonals (rotate90 xss))

noQueensinSameDiagonal :: QueenBoard -> Bool
noQueensinSameDiagonal = noQueensinSameRow . allDiagonals

isQueenSolution :: QueenBoard -> Bool
isQueenSolution = (noQueensinSameRow `fAnd` noQueensinSameColumn `fAnd` noQueensinSameDiagonal)

allFalseOneTrue :: Int -> [[Bool]]
allFalseOneTrue length = nub $ permutations ( [True] ++ (replicate (length - 1) False) )

allProduct = sequence :: [[a]] -> [[a]]

allPossibleBoards :: Int -> [QueenBoard]
allPossibleBoards size = allProduct (replicate size (allFalseOneTrue size))

solveQueens :: Int -> [QueenBoard]
solveQueens = (filter isQueenSolution) . allPossibleBoards

main :: IO()
main = mapM_ putStrLn $ map show $ head $ solveQueens 8