N-королевы в 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)
}

Мы определяем функцию 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, но некоторые из них не так прямолинейны. Цикл for в Scala основан на синтаксисе do-loop в Haskell, что, вероятно, объясняет некоторые ваши затруднения. Вот как это читать:

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