let NQueens n =  
    let a = [|for i in 0..n -> true|]   //某列是否使用的标志  
    let b = [|for i in 0..(2 * n - 1) -> true|] //斜负方向上是否使用的标志  
    let c = [|for i in 0..(2 * n - 1) -> true|] //斜正方向上是否使用的标志  
    let path = [|for i in 0..n -> 0|]   //记录当前路径  
    //Solve n j 求解规模为n，第j行的解  
    let rec Solve n j =  
        if j > n then   //已经把当前状态的n行都求解完毕，可打印当前路径  
            printfn "%A" path.[1..] //打印当前结果  
        else    //否则，要继续向下求解  
            for i in 1..n do    //枚举当前行的所有列  
                //如果当前位置的列、斜正、斜负方向都可用，则使用  
                if (a.[i] && b.[i + j - 1] && c.[n - i + j]) then  
                    //标记状态  
                    a.[i] <- false  
                    b.[i + j - 1] <- false  
                    c.[n - i + j] <- false  
                    path.[j] <- i   //记录当前路径  
                    do Solve n (j + 1)  //求解下一行  
                    //还原状态  
                    a.[i] <- true  
                    b.[i + j - 1] <- true  
                    c.[n - i + j] <- true  
    do Solve n 1    //从第一行开始求解  
    printfn ""  
  
List.iter NQueens [1..10]   //求1到10皇后的所有解  
System.Console.ReadKey()|>ignore

//自定义数据类型  
type Queen =  
    struct  
        val x: int  
        val y: int  
        //构造函数  
        new(x: int, y: int) = { x = x; y = y }  
        //重载Object.ToString()  
        override this.ToString() =  
            //字符串打印函数  
            sprintf "(%d,%d)" this.x this.y  
    end  
  
let NQueens n =  
    //对子问题求解  
    let rec Solve = function  
        //第一行每一个位置都可以放置  
        | x when x = 1 ->  
            [for y in 1..n -> [new Queen(1,y)]]  
        //其他情况  
        | x ->  
            //构造一个临时存放结果的变量  
            let mutable t = [[new Queen(0,0)]].Tail  
            //枚举当前子问题的解  
            for i in Solve (x - 1) do  
                //逐一尝试是否可以放置  
                for y in 1..n do  
                    if not((List.exists (fun (elem: Queen) -> elem.y = y ) i)   //列可放置  
                            ||(List.exists (fun elem -> elem = x + y) (List.map (fun (elem: Queen) -> elem.x + elem.y) i))  //斜负方向可放置  
                            ||(List.exists (fun elem -> elem = x - y) (List.map (fun (elem: Queen) -> elem.x - elem.y) i))) //斜正方向可放置  
                    then  
                        //把当前可行解放入临时空间  
                        t <- t @ ([i @ [new Queen(x, y)]])  
            //返回当前可行解  
            t  
    //求解并返回  
    Solve n  
  
//打印结果  
NQueens 8 |> List.iteri (fun i elem -> printfn "%d:\t%A" (i + 1) elem)  
System.Console.ReadKey()|>ignore  

type Queen =   
     struct   
         val x: int   
         val y: int   
         new(x: int, y: int) = { x = x; y = y }   
         override this.ToString() =   
             sprintf "(%d,%d)" this.x this.y   
     end   
    
 let NQueens n =   
     let rec Solve = function   
         | x when x = 1 ->   
             [for y in 1..n -> [new Queen(1,y)]]   
         | x ->   
             //求出当前子问题解集与要测试是否能放置的点的空间   
             [for sub in Solve (x - 1) do   
                 for y in 1..n -> (sub, y)]