Eight Queens: I couldn't let it go!

If you're not used to functional programming, and I'm not, you may respond with irritation at an FPer's "How few lines of code can I use to solve this problem?" showpiece. A good example would be the textbook problem of transposing a matrix (for which the answer is posted on Jomo Fischer's blog). If you really need to transpose a lot of matrices, you're probably going to be working in an environment where such operations are optimized, e.g. Mathematica. In other words, you're not going to do it yourself. So if anyone is irritated with the following code, let me say that I had to ponder this (on and off, not continuously!) for a few months before I arrived at the "right" solution, and I do feel that it's right. However, trying to implement it in F# gave me some valuable insights into how it ought to be done in other languages. Here's my solution:

> let queens size =
-     let range = [1..size]
-     range |> Seq.fold (fun answers column ->
-         let positions = [for row in range -> (column, row)]
-         [for p in positions for a in answers when all_safe p a -> a@[p]]) [[]]
- ;;

val queens : int -> (int * int) list list

> queens 5;;
val it : (int * int) list list
= [[(1, 4); (2, 2); (3, 5); (4, 3); (5, 1)];
 [(1, 3); (2, 5); (3, 2); (4, 4); (5, 1)];
 [(1, 5); (2, 3); (3, 1); (4, 4); (5, 2)];
 [(1, 4); (2, 1); (3, 3); (4, 5); (5, 2)];
 [(1, 5); (2, 2); (3, 4); (4, 1); (5, 3)];
 [(1, 1); (2, 4); (3, 2); (4, 5); (5, 3)];
 [(1, 2); (2, 5); (3, 3); (4, 1); (5, 4)];
 [(1, 1); (2, 3); (3, 5); (4, 2); (5, 4)];
 [(1, 3); (2, 1); (3, 4); (4, 2); (5, 5)];
 [(1, 2); (2, 4); (3, 1); (4, 3); (5, 5)]]
> queens 4;;
val it : (int * int) list list
= [[(1, 3); (2, 1); (3, 4); (4, 2)]; [(1, 2); (2, 4); (3, 1); (4, 3)]]

First, I did not use a for loop. Not because that would just be too imperative, but because I realized that the range (e.g. from 1..8, for an 8 x 8 chessboard) was actually an (immutable) object that I needed to use in several ways. To generate all the positions on a chessboard, I would then use a "sequence comprehension" such as { for column_number in range for row_number in range -> (column_number, row_number) }. I've begun to see this as more natural than nested for loops. I'm not doing with side effects in a loop; I'm asking for a single object (a collection of board positions) to be created for me. So the comprehension, a declarative construct, is more natural: "Here's what I want; give it to me. I'm not interested in putting it together piece by piece; that's your job." In comparison, the idiom 1, create a list, 2, go through several loops, appending on each innermost iteration, 3, finally do something with the collection (which is probably mutable, even though it really shouldn't be), obscures the intention, and is error-prone.

Then I iterate over that range (now treating it as the sequence of column numbers), and for every column I take the sequence of answers so far (i.e., each such answer is a sequence of one position each from the columns I've seen so far) and extend each one with each position in the current column (i.e. the current element of the range) that's safe. Below, I defined the functions safe() and all_safe(). I can easily generate board positions for the current column by means of another comprehension (let positions = etc.). Then I take the Cartesian product of the answers so far and this new column, filter all these new candidates through all_safe, and pass this new collection on to the next iteration, via fold(). For obvious reasons, Seq.fold starts with the collection of known 0-length answers, which is of course [[]].

If I were (re)doing it in Scheme, I'd rip off Kent Dybvig's comprehension macro, first off. I'd also rip off an implementation of fold, if I didn't already have one. I'd generate a range 1..n just as I do above. Then, on every iteration (I believe it is an iteration, if I'm folding from the left) I create the Cartesian product of the answers so far and the current column (which I just generated), (filter) these pairs through (all-safe), and continue. Something like that.