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 =&gt; a -&gt; [a] -&gt; Int
count x =  length . filter (==x)

fAnd :: (a -&gt; Bool) -&gt; (a -&gt; Bool) -&gt; (a -&gt; Bool)
fAnd = liftM2 (&amp;&amp;)

rotate90 :: [[a]] -&gt; [[a]]
rotate90 = map reverse . transpose

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

noQueensinSameColumn :: QueenBoard -&gt; Bool
noQueensinSameColumn = noQueensinSameRow . rotate90

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

allDiagonals :: [[a]] -&gt; [[a]]
allDiagonals xss = (diagonals xss) ++ (diagonals (rotate90 xss))

noQueensinSameDiagonal :: QueenBoard -&gt; Bool
noQueensinSameDiagonal = noQueensinSameRow . allDiagonals

isQueenSolution :: QueenBoard -&gt; Bool
isQueenSolution = (noQueensinSameRow `fAnd` noQueensinSameColumn `fAnd` noQueensinSameDiagonal)

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

allProduct = sequence :: [[a]] -&gt; [[a]]

allPossibleBoards :: Int -&gt; [QueenBoard]
allPossibleBoards size = allProduct (replicate size (allFalseOneTrue size))

solveQueens :: Int -&gt; [QueenBoard]
solveQueens = (filter isQueenSolution) . allPossibleBoards

main :: IO()
main = mapM_ putStrLn $ map show $ head $ solveQueens 8
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.