让我们来分解一下。
def queens(n: Int): List[List[(Int, Int)]] = {
def placeQueens(k: Int): List[List[(Int, Int)]] =
if (k == 0)
List(List())
else
for {
queens <- placeQueens(k - 1)
column <- 1 to n
queen = (k, column)
if isSafe(queen, queens)
} yield queen :: queens
placeQueens(n)
}
我们定义一个函数queens(n: Int)
返回 n*n 棋盘上 n 个皇后的所有可能位置。功能queens
本身很简单;它只是委托给一个内部函数,称为placeQueens
.
placeQueens
首先列出了一个基本情况:如果我们在 0*0 棋盘上操作并放置 0 个皇后,则只有一种(非常简单的)方法可以做到这一点。现在,这个函数的核心部分在 for 循环中。
for {
queens <- placeQueens(k - 1)
column <- 1 to n
queen = (k, column)
if isSafe(queen, queens)
} yield queen :: queens
其中部分内容可以像“传统”for 循环一样阅读,但其中一些内容并不那么简单。 Scala 的 for 循环基于 Haskell 的 do 循环语法,这可能解释了您的一些困惑。阅读本文的方法是:
// We're starting a for-loop
for {
// Call placeQueens recursively. placeQueens returns a list of
// all possible results, so iterate over them.
queens <- placeQueens(k - 1)
// Iterate over each column that the kth queen could go in.
column <- 1 to n
// Assign the queen to that position.
queen = (k, column)
// If the position is safe, keep going. More precisely, if the position
// is NOT safe, stop.
if isSafe(queen, queens)
// Put our new queen assignment at the beginning of the recursively computed list.
} yield queen :: queens
这些循环需要一些时间来适应。手动对循环进行脱糖(编译器无论如何都会这样做)以了解其含义是很有教育意义的。你可以找到翻译规则在斯卡拉网站上.