N-queens in Haskell without list traversal

Question

I searched the web for different solutions to the n-queens problem in Haskell but couldn't find any that could check for unsafe positions in O(1) time, like that one that you keep an array for the / diagonals and one for the \ diagonals.

Most solutions I found just checked each new queen against all the previous ones. Something like this: http://www.reddit.com/r/programming/comments/62j4m/nqueens%5Fin%5Fhaskell/

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

What would be the best way to implement such an "O(1) approach" in Haskell? I am not looking for anything "super-optimized". Just some way to produce the "is this diagonal already used?" array in a functional manner.

UPDATE:

Thanks for all the answers, folks! The reason I originally asked the question is because I wanted to solve a harder backtracking problem. I knew how to solve it in an imperative language but could not readily think of a purely functional data structure to do the job. I figured that the queens problem would be a good model (being the backtracking problem :) ) for the overall data-structure problem, but it isn't my real problem though.

I actually want to find a data structure that allows O(1) random access and holds values that are either on a "initial" state (free line/diagonal, in the n-queens case) or in a "final" state (occupied line/diagonal), with transitions (free to occupied) being O(1). This can be implemented using mutable arrays in an imperative language but I feel that the restriction of updating values only allows for a nice purely functional data structure (as opposed to Quicksort, for example, that really wants mutable arrays).

I figure that sth's solution is as good as you can get using immutable arrays in Haskell and the "main" function looks like what I wanted it to be:

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

The main problem seems to be finding a better data structure though, as Haskell Arrays have O(n) updating. Other nice suggestions fall short of the mythical O(1) holy grail:

• DiffArrays come close but mess up in the backtracking. They actually get super slow :( .
• STUArrays conflict with the pretty functional backtracking approach so they are discarded.
• Maps and Sets have only O(log n) updating.

I am not really sure there is a solution overall, but it seems promising.

UPDATE:

The most promising data structure I found where Trailer Arrays. Basically a Haskell DiffArray but it mutates back when you backtrack.

Answer 1

Probably the most straightforward way would be to use a UArray (Int, Int) Bool to record safe/unsafe bits. Although copying this is O(n²), for small values of N this is the fastest method available.

For larger values of N, there are three major options:

• Data.DiffArray removes copy overhead as long as you never use the old values again after modifying them. That is, if you always throw away the old value of the array after mutating it, the modification is O(1). If, however, you access the old value of the array later (even for only a read), the O(N²) is paid then in full.
• Data.Map and Data.Set allow O(lg n) modifications and lookups. This changes the algorithmic complexity, but is often fast enough.
• Data.Array.ST's STUArray s (Int, Int) Bool will give you imperative arrays, allowing you to implement the algorithm in the classic (non-functional) manner.

Answer 2

The basic potential problem with this approach is that the arrays for the diagonals need to be modified every time a queen is placed. The small improvement of constant lookup time for the diagonals might not necessarily be worth the additional work of constantly creating new modified arrays.

But the best way to know the real answer is to try it, so I played around a bit and came up with the following:

import Data.Array.IArray (array, (//), (!))
import Data.Array.Unboxed (UArray)
import Data.Set (Set, fromList, toList, delete)

-- contains sets of unoccupied columns and lookup arrays for both diagonals
data BoardState = BoardState (Set Int) (UArray Int Bool) (UArray Int Bool)

-- an empty board
board :: Int -> BoardState
board n
   = BoardState (fromList [0..n-1]) (truearr 0 (2*(n-1))) (truearr (1-n) (n-1))
   where truearr a b = array (a,b) [(i,True) | i <- [a..b]]

-- modify board state if queen gets placed
occupy :: BoardState -> (Int, Int) -> BoardState
occupy (BoardState c s d) (a,b)
   = BoardState (delete b c) (tofalse s (a+b)) (tofalse d (a-b))
   where tofalse arr i = arr // [(i, False)]

-- get free fields in a row
freefields :: BoardState -> Int -> [(Int, Int)]
freefields (BoardState c s d) a = filter freediag candidates
   where candidates = [(a,b) | b <- toList c]
         freediag (a,b) = (s ! (a+b)) && (d ! (a-b))

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

-- all possibilities to place n queens on a n*n board
queens :: Int -> [[(Int, Int)]]
queens n = place (board n) n

This works and is for n=14 roughly 25% faster than the version you mentioned. The main speedup comes from using the unboxed arrays bdonian recommended. With the normal Data.Array it has about the same runtime as the version in the question.

It might also be worth it to try the other array types from the standard library to see if using them can further improve performance.

Answer 3

In general you are probably going to be stuck paying the O(log n) complexity tax for a functional non-destructive implementation or you'll have to relent and use an (IO|ST|STM)UArray.

Strict pure languages may have to pay an O(log n) tax over an impure language that can write to references by implementing references through a map-like structure; lazy languages can sometimes dodge this tax, although there is no proof either way whether or not the extra power offered by laziness is sufficient to always dodge this tax -- even if it is strongly suspected that laziness isn't powerful enough.

In this case it is hard to see a mechanism by which laziness could be exploited to avoid the reference tax. And, after all that is why we have the ST monad in the first place. ;)

That said, you might investigate whether or not some kind of board-diagonal zipper could be used to exploit locality of updates -- exploiting locality in a zipper is a common way to try to drop a logarithmic term.