Scala 中的 N 皇后 [英] N-queens in Scala

问题描述

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

I don't understand how this code works, even tough I debugged in Eclipse. Can you explain step by step this code? By the way, code works correctly. I also understand the n-queens algorithm but I don't understand the mechanism of this code.

推荐答案

让我们分解一下.

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 的内部函数.

We define a function queens(n: Int) which returns every possible placement of n queens on an n*n chessboard. The functions queens itself is very simple; it just delegates to an inner function, called placeQueens.

placeQueens 首先列出了一个基本情况:如果我们在 0*0 棋盘上操作并放置 0 个皇后，那么只有一种(非常简单的)方法可以做到.现在，这个函数的核心在 for 循环中.

placeQueens has a base case listed first: if we are operating on a 0*0 chessboard and placing 0 queens, there is exactly one (very trivial) way to do it. Now, the meat of this function is in the for-loop.

for {
  queens <- placeQueens(k - 1)
  column <- 1 to n
  queen = (k, column)
  if isSafe(queen, queens)
} yield queen :: queens

其中的一部分可以像传统的"for 循环一样阅读，但其中一些并不那么简单.Scala 的 for 循环基于 Haskell 的 do-loop 语法，这可能解释了您的一些困惑.阅读方式是:

Parts of this can be read like a "traditional" for-loop, but some of it is not so straightforward. Scala's for-loop is based on Haskell's do-loop syntax, which probably explains some of your confusion. The way to read this is:

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

这些循环需要一些时间来适应.手动对循环(编译器就是这样做的)进行脱糖以了解其含义是很有教育意义的.您可以在 在 Scala 网站上找到翻译规则.

These loops take some getting used to. It can be educational to desugar the loop (which is what the compiler does anyway) by hand to see what it means. You can find the translation rules on the Scala website.

这篇关于Scala 中的 N 皇后的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！