Scala中的N-queens

object NQueens {
  def solveNQueens(n: Int): List[List[String]] = {
    def placeQueens(k: Int): List[List[String]] =
      if (k == 0) List(List())
      else
        for {
          queens <- placeQueens(k - 1)
          col <- 0 until n
          if isSafe(col, queens)
        } yield col :: queens

    def isSafe(col: Int, queens: List[Int]): Boolean = {
      val row = queens.length
      val queensWithRow = (row - 1 to 0 by -1) zip queens
      queensWithRow.forall {
        case (r, c) => col != c && math.abs(col - c) != row - r
      }
    }

    val solutions = placeQueens(n)
    solutions.map { queens =>
      queens.map(col => "." * col + "Q" + "." * (n - col - 1))
    }
  }

  def main(args: Array[String]): Unit = {
    val n = 4
    val solutions = solveNQueens(n)
    solutions.foreach { solution =>
      solution.foreach(println)
      println()
    }
  }
}