The ``N Queens'' problem in Scala.

epfl_wk_6_3.scala

def queens(n: Int): Set[List[Int]] = {
  
  def isSafe(col: Int, queens: List[Int]): Boolean = {
    val row = queens.length
    val queensWithRow = queens zip (row - 1 to 0 by -1)
    queensWithRow.forall {
      case (c, r) => c != col && (math.abs(col - c) != row - r)
    }
  }
  
  def isSafe2(col: Int, queens: List[Int]): Boolean = {
    val row = queens.length
    def isSafe2Rec(queens: List[(Int, Int)]): Boolean = {
      queens match {
        case (c, r) :: xs => c != col && (math.abs(col - c) != row - r) && isSafe2Rec(xs)
        case _ => true
      }
    }
    isSafe2Rec(queens zip (row - 1 to 0 by -1))
  }
  
  def queensRec(k: Int): Set[List[Int]] = {
    if (k == 0) Set(List())
    else for {
      queens <- queensRec(k - 1)
      col <- 0 until n
      if isSafe2(col, queens)
    } yield col :: queens
  }
  
  queensRec(n)
}