Scala中的N-queens

Question

  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算法，但是我不理解这段代码的机制。

Answer 1

让我们把它分解一下。

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-loop基于Haskell的do-loop语法，这可能解释了您的一些困惑。阅读这篇文章的方法是：

// 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

这些循环需要一些时间来适应。手动对循环进行去垃圾处理(这也是编译器所做的)，以了解它的含义，这是很有教育意义的。您可以找到转换规则on the Scala website。