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_in_haskell/

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.