Small example from Oderskys "Scala By Example" Book extended by a customized filter-approach. Find the test-file in another Gist

Nqueen.scala

package nqueens

object Nqueens extends App {

  println((nQueens(100) map show) mkString "\n")

  def isValid(partialSolution: List[Int], col: Int, n: Int): Boolean = {
    val partialSolutionCoords = (0 until partialSolution.length) zip partialSolution.reverse
    val partial = partialSolutionCoords.toSet

    val negSeqK = partialSolution.length-1 to 0 by -1
    val negSeqCol = col-1 to 0 by -1
    val posSeqCol = col+1 to n

    val neg = (negSeqK zip negSeqCol).toSet
    val pos = (negSeqK zip posSeqCol).toSet
    !((neg union pos).exists(x => partial.contains(x))) && !partialSolution.contains(col)
  }

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

  def nQueens(n: Int): Set[List[Int]] = {
    def placeQueen(k: Int): Set[List[Int]] = {
      if(k==0) Set(List())
      else {
        for {
          partialSolution <- placeQueen(k - 1)
          col <- 0 until n
          if (isValid(partialSolution, col, n))
          //if(isSafe(col, partialSolution))
        } yield col :: partialSolution
      }
    }
    placeQueen(n)
  }

  def show(queens: List[Int]) = {
    val lines =
      for(col <- queens.reverse)
        yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString
    "\n" + (lines mkString "\n")
  }

}