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

本文用三种不同的方式求解N皇后问题。通过从三个不同角度的剖析，带您认识F#，进入到F# World！

 

方法一：F# Code，C-Style

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

很显然，这是数据结构里面的经典写法。没有任何特点可言。

注释详细，数据结构没有学好的朋友可以趁此机会复习一遍。对于此算法，就不在讲解。

下面讲解这段F#代码：

1、

let是最常用的关键字，其作用是声明变量、常量、函数。

用来绑定一个值或函数。一个值声明后，默认是不可改变值的。如果要修改某个变量，那一定要声明为mutable。

其官方定义是：A binding associates an identifier with a value or function. You use the let keyword to bind a name to a value or function. 

let的用法举例：

let a = 1  //给a绑定一个整形数“1”

let square x = x*x  //绑定一个求平方函数square

let mutable mut = 10//mut是个可改变值的变量

mut <- 20
2、

for语句有两种形式：

for pattern in enumerable-expression do  //enumerable-expression是枚举表达式

for identifier = start [ to | downto ] finish do  //对应C语言中的for(int start=0;i<=finish;i++)

3、

let a = [|for i in 0..n -> true|]

[||]是用来表示数组(Array)。[|1;2;3;4;5|]代表从1到5的数组。对于连续元素，可以简写为[|1..5|]。访问某个元素用a.[index]。

这里你一定会问，数组里怎么还可以有for语句？

是因为在一个序列当中，可以用yield关键字产生一个新的序列。(They can use the yield keyword to produce values that become part of the sequence.)

上述语句的完整写法是let a = [|for i in 0..n do yield true|]。“do yield”可以用“->”代替。

那么此语句的作用是生成一个从0到n的布尔型数组，里面的值全部为true。

4、

接下来是rec关键字。其作用是表示这是个递归函数。(The rec keyword is used together with the let keyword to define a recursive function.)

5、

if语句。不用说大家都是干什么用的。不过这里还是要说一下。因为if在F#里有点小特别。

if Boolean-expression then expression1 [ else expression2 ] 

else if可以简写为elif。不过elif后面必须跟随一个else，否则会编译错误。

如果if语句用在某个语句中，那一定要保证每个条件路径都有返回值，并且返回值类型相同。

例如：

这样写是正确的

let test x y =
    if x = y then "equals"
    elif x < y then "is less than"
    else "is greater than"

这样写是错误的

let test x y =
    if x = y then "equals"

6、

printf,printfn

打印的语法类似于C。printfn后面会加上一个换行

例子：

printfn "x = %f, y = %s, z = %b" x y z

7、

List.iter是个List迭代器。具体参见这里。

 

 

方法二：不漂亮的写法 

//自定义数据类型 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

不漂亮是因为把一个功能的语句写成了多条语句，用了两层的for循环控制程序流，使用了mutable临时数据。最终结果是程序可读性不强，代码也不够紧凑。

不过这也是下一个方法的“前生”，所以还是有必要了解这个方法用到的东西。

 

1、

function，这里是作为匹配表达式(Match Expressions)使用。其作用类似于C中的switch语句。

function
    | pattern1 [ when condition ] -> result-expression1
    | pattern2 [ when condition ] -> result-expression2
    | ...

上述例子就把x分为等于1和不等于1两种情况处理，并返回结果。注意，这里一样需要保证每个条件路径都有返回值，并且返回值类型相同。

2、

List.exists & List.map 这是List的两种操作，List.exists是判断List当中是否存在某一特殊的数据；List.map是一种集合映射操作。具体请参加这里，这里。

3、

fun ->

这里是一个Lambda表达式，代表一个匿名函数。(The fun keyword is used to define a lambda expression, that is, an anonymous function.)

fun parameter-list -> expression

其中参数表中参数要限定类型，或者编译器不能够正确推断出类型。就需要指定其类型。

参见下列例子：

fun a b c -> ...
fun (a: int) b c -> ...
fun (a : int) (b : string) (c:float) -> ...

4、

@ 这是序列操作符。是将两个List连接成一个(Concatenates two lists.)

另一个序列操作符是“::”，作用是把一个值和一个List连接(Creates a list. The element on the left side is appended to the list on the right side.)。

5、

|>也是一个操作符。这个解释有点拗口，作用是把操作符左边的东西当做右边的参数(Passes the result of the left side to the function on the right side (forward pipe operator).)。

写成函数形式就是 f |> g = g f。

与之对应的是<|操作符。

 

 

方法三：美的F#代码

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)] //将此空间传递给选择器选择哪些是有效的 |> List.choose (fun (sub, y) -> if not(sub |> List.exists (fun (elem: Queen) -> elem.y = y ) //列有效 ||(List.map (fun (elem: Queen) -> elem.x + elem.y) sub) |> List.exists (fun elem -> elem = x + y) //斜负方向有效 ||(List.map (fun (elem: Queen) -> elem.x - elem.y) sub) |> List.exists (fun elem -> elem = x - y)) //斜正方向有效 then Some(sub @ [new Queen(x, y)]) //标记有效值 else None) //不作处理 //求解并返回结果 Solve n //求解并打印结果 NQueens 8 |> List.iteri (fun i elem -> printfn "%d:/t%A" (i + 1) elem) System.Console.ReadKey()|>ignore

这才是美的F#代码，所有数据处理都用一条语句搞定。所有的表达非常清晰。这也是F#之美的地方。

依旧，介绍这里的新玩意。

1、

List.choose 从List中选取某一个处理后的结果(Applies the given function to each element of the list. Returns the list comprised of the results for each element where the function returns Some.)。

2、

Options 可用来标记某一数据是否被choose(The option type in F# is used when an actual value might not exist for a named value or variable. An option has an underlying type and can hold a value of that type, or it might not have a value.)。

被选择用Some标记，反之用None。

Options的实际应用非常宽泛，请参见这里。

 

 

对于三种方法的点评：

方法1：单纯的使用F#语法完成C的翻译。思维还在底层，无法突出F#的优势，也难以写出可读性较强的代码。使用的算法是深度优先搜索(DFS)。

 

方法2：能够使用一些F#元素来处理数据，不过处理方式并不够完美。处理问题的思路是求解x皇后，就要求解x-1皇后的放置，然后再放置x皇后。也就是所谓的“分治”思想。状态的扩展方式近似于广度优先搜索(BFS)。

 

方法3：是对方法2的编码改进。能够体现出更好的逻辑性，更加易于编写和理解。符合“一句话写完整个程序”的思想。

 

 

F#还有许多非常好的特性并没展示出来，或者说只展示出了F#的极少一部分的功能。F#的一大优势就是易于并行计算。有兴趣的朋友可以继续关注本空间。