type Position = { r : int; c : int }

let safe a b =
    match a, b with
    | { r = r1; c = c1 }, { r = r2; c = c2 } when
            r1 = r2 ||
            c1 = c2 ||
            abs((float c1 - float c2) / (float r1 - float r2)) = 1.0 -> false
    | _, _ -> true

let queens size =
    let rec loop positions positionCount availableCols row =
        let totallySafe x = Seq.forall (fun y -> safe x y) positions

        if positionCount = size then Some positions
        else
            seq { for col in availableCols do yield { r = row; c = col } }
            |> Seq.tryPick (fun testPosition ->
                    match totallySafe testPosition with
                    | true -> loop (testPosition::positions) (positionCount + 1) (Set.remove testPosition.c availableCols) (row + 1)
                    | false -> None
                )
    loop [] 0 (set [1..size]) 1

let test n =
    let s = System.Diagnostics.Stopwatch.StartNew()
    let items = queens n
    s.Stop()

    match items with
    | Some(items) ->items |> Seq.iter (fun x -> printf "(%i, %i), " x.r x.c)
    | None -> printfn "No solutions"

    printfn "\nTotal time: %fms" s.Elapsed.TotalMilliseconds

(*
Here are my machine's specs:
- 4 GB memory
- 3.2ghz quad core, AMD Phenom II x4
- Windows Vista 32 bit


> test 8;;
(8, 4), (7, 2), (6, 7), (5, 3), (4, 6), (3, 8), (2, 5), (1, 1), 
Total time: 4.638500ms
val it : unit = ()

> test 13;;
(13, 7), (12, 11), (11, 8), (10, 6), (9, 4), (8, 13), (7, 10), (6, 12), (5, 9), (4, 2), (3, 5), (2, 3), (1, 1), 
Total time: 3.650500ms
val it : unit = ()

> test 20;;
(20, 11), (19, 6), (18, 14), (17, 7), (16, 10), (15, 8), (14, 19), (13, 16), (12, 9), (11, 17), (10, 20), (9, 18), (8, 12), (7, 15), (6, 13), (5, 4), (4, 2), (3, 5), (2, 3), (1, 1), 
Total time: 1765.944600ms
val it : unit = ()
*)