Dopcn's Blog

life and work

用高阶函数解八皇后问题

Posted at — Dec 5, 2015

八皇后问题是求在八行八列的国际象棋棋盘上放置八个皇后,令她们彼此之间不能相互被吃的所有方法。国际象棋中皇后可以顺着横竖对角线方向行进任意距离。

高阶函数是泛指那些以一个函数(或者称之为一个过程)作为参数的函数,这个问题里用到的标准库里自带的 map flatmap filter reduce

在函数式编程思路中高阶函数在建立抽象和模块化过程中起到了很重要的作用,以 map 为例它将对一个序列的操作抽象出来,使序列本身和对序列的操作分割开来,这样做的好处是方便重用这种操作,也方便更换序列所需要进行的操作,为了实现这两点在常用的命令式写法中都是要整个操作重写才能完成。

高阶函数的组合使用可以更好的体现模块化的思想,高阶函数本身是模块与模块之间的接口,例如得到一个序列中的偶数的平方的序列:

let a = Array(0...100)
let b = a.filter({$0%2 == 0}).map{$0*$0}

模块化的好处自然是替换模块整体结构不变,也就是维护方便。

函数式编程思路解决问题的一般思路都是递归,逐步将问题分解求解。在解八皇后问题过程中递归的思路是 k-1 列已经摆放好 k-1 个皇后,通过 map 得到第 k 列的所有可能解,通过 flatmap 整理解类型,最后 filter 过滤出满足条件的那些解。

reduce 函数用在 filter 的判断是否满足条件的模块中,这个例子里似乎很好的体现了在某些情况中命令式写法可以更高效

struct NQueensProblem {
    private let size: Int
    
    init(boardSize: Int) {
        //size start from 1
        size = boardSize>0 ? boardSize : 1
    }
    
    func solutions() -> [[(Int, Int)]] {
        func isSafe(solution: [(Int, Int)], atColumn column: Int) -> Bool {
            let (colX, colY) = solution[column]
            return solution.reduce(true, combine: { (isSafe, location) -> Bool in
                let (locX, locY) = location
                if locX == colX && locY == colY {
                    return isSafe
                } else {
                    return isSafe &&
                        !(locX == colX || locY == colY || (locX+locY) == (colX+colY) || (locX-locY) == (colX-colY))
                }
            })
        }
        
        //column start from 0
        func queenCols(column: Int) -> [[(Int, Int)]] {
            if column == 0 {
                return Array(0..<size).map{ [(0, $0)] }
            } else {
                return queenCols(column-1).map({ (partSolution) -> [[(Int, Int)]] in
                    return Array(0..<size).map { partSolution + [(column, $0)] }
                }).flatMap({ $0 }).filter{ isSafe($0, atColumn: column) }
            }
        }
        
        return queenCols(size-1)
    }
}

var queen = NQueensProblem(boardSize: 8)
print(queen.solutions())

最后当n等于8时一共有92个解法

最后的最后,在 Swift 2.0 之后 flatmap 有了一个特殊用途:过滤nil

let optionalInts: [Int?] = [1, 2, nil, 4, nil, 5]
 
let ints = optionalInts.flatMap { $0 }
ints // [1, 2, 4, 5]

reference: https://www.natashatherobot.com/swift-2-flatmap/