F#(FSharp)用三种方法解N皇后有关问题，剖析F#之美

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)]