N-queens problem in Haskell by bruteforce

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()

The standard way to solve this is to:

• Only keep track of the positions of the queens - not whether a square has a queen.

• Since only each column may have one queen (and must have one queen), a solution is a [Int] indicating the row positions of the placed queens, e.g. [0,2,4] is a solution for a board having 3 columns (and at least 5 rows) where the queens are at (0,0), (1,2) and (2,4).

So build up the solution iteratively. If you have the placement [r1] how can it be extended to a valid placement [r1, r2]? Clearly r2 can't equal r1 and (0,r1) can't be on the same diagonal as (1,r2). And, of course, r2 has to be a valid row number.

StackExchange Code Review Q#104216, answer score: 3