Scala 中的 N 皇后

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

我不明白这段代码是如何工作的，即使我在 Eclipse 中调试得很困难。你能一步一步解释这段代码吗？顺便说一句，代码工作正常。我也了解n-queens算法，但我不明白这段代码的机制。

让我们来分解一下。

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

这些循环需要一些时间来适应。手动对循环进行脱糖（编译器无论如何都会这样做）以了解其含义是很有教育意义的。你可以找到翻译规则在斯卡拉网站上.