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.