Решение задачи о N ферзях для шахматной доски размером NxN

queens.scala

/**
  * Решает задачу о N ферзях [1] для шахматной доски размером NxN.
  *
  * Возвращает множество возможных расстановок ферзей на шахматной доске,
  * такие, чтобы ни один не находился под боем другого.
  *
  * Реализация основана на материале [2] курса
  * "Functional Programming Principles in Scala" (2016), лекция 6.3.
  *
  * Источники:
  *   1. http://mathworld.wolfram.com/QueensProblem.html
  *   2. https://www.coursera.org/learn/progfun1/lecture/H3cKk/lecture-6-3-combinatorial-search-example
  *
  * @param boardSize размер шахматной доски (N)
  */
def queens(boardSize: Int): Set[List[Int]] = {
  require(boardSize > 0, "Size of the board must be greater than zero")

  def loop(row: Int, prevSolutions: Set[List[Int]]): Set[List[Int]] = {
    if (row >= boardSize)
      prevSolutions
    else {
      val possiblePositions = 0 until boardSize
      val solutions = for {
        prevSolution <- prevSolutions
        possiblePosition <- possiblePositions if isValidPosition(possiblePosition, prevSolution)
      } yield possiblePosition :: prevSolution
      loop(row + 1, solutions)
    }
  }

  loop(0, Set(List.empty))
}

def isValidPosition(pos: Int, solution: List[Int]): Boolean = {
  if (solution.isEmpty)
    true
  else {
    solution.zipWithIndex.forall { case (queenPos, offset) =>
      queenPos != pos &&
        queenPos != (pos - offset - 1) &&
        queenPos != (pos + offset + 1)}
  }
}

def showBoard(boardSize: Int, solution: List[Int]): String = {
  val gridLine = "+" + Seq.fill(boardSize)("-").mkString("+") + "+"
  val rows = for (pos <- solution.reverse)
    yield "|" + Seq.fill(boardSize)(" ").updated(pos, "X").mkString("|") + "|"
  rows.mkString("\n")
}

// Выводим все решения для стандартной доски 8x8
for (solution <- queens(8)) {
  println(showBoard(8, solution))
  println()
}