queens.fsx

let check rows =
    // test if any queens are threatening each other
    let n = rows |> Seq.length
    let areDistinct = Seq.distinct >> Seq.length >> (=) n
    let forwardDiagonals = rows |> Seq.mapi (+)
    let backDiagonals = rows |> Seq.mapi (-)
    rows |> areDistinct && forwardDiagonals |> areDistinct && backDiagonals |> areDistinct

let solve n =
    // solve n-queens problem by generating random solutions
    match n with
    | 2 | 3 -> None // known to be impossible
    | _ ->
        let r = System.Random()
        let permute =
            let projection _ = r.Next()
            List.sortBy projection
        Seq.initInfinite (fun _ -> permute [0..n-1]) |> Seq.tryFind check

let mutable verbose = false
let solve2 n =
    // solve n-queens problem by backtracking
    let rec inner state = 
        match state with 
        | Some rows when List.length rows < n ->
            if verbose then printfn "%A" rows 
            let prepend x = x :: rows
            let partials = [0..n-1] |> Seq.map prepend |> Seq.filter check
            partials |> Seq.map (Some >> inner) |> Seq.tryFind Option.isSome |> Option.flatten
        | _ -> state
    Some [] |> inner