Scala solution to nQueen using for-comprehension

Question

I have some difficulty in understanding the Scala solution to the n Queens problem, below is the implementation assuming isSafe is defined correctly

def queens(n: Int): Set[List[Int]] = {
    def placeQueens(k: Int): Set[List[Int]] = k match {
        case 0 => Set(List())
        case _ =>
            for {
                queens <- placeQueens(k - 1)
                col <- 0 until n
                if isSafe(col, queens   )
            }yield k :: queens
    }

    placeQueens(n)
  }

The for comprehension, as I have seen, theoretically should return a buffered collection, and I see here it buffers a list of queens with k :: queens, but it indeed returns a Set[List] as defined. Can someone throw some light on how this for comprehension works?

Is my assumption correct that for every time will return a collection of collections and since in this case I deal with a Seq and a Set in the nested for for expression it is returning a Set[List].

The question is more related to the for comprehension in implementing nQueen not nQueen in general.

Answer 1

Recall that a for comprehension is just syntactic sugar for map, flatmap and filter, all three of which you are using in your example. Whatever you yield in the yield block will be added to the mapped collection. You might find this article on how yield works to be interesting.

When you yield k :: queens you are creating a list with k added to the queens list which was generated from a recursive invocation using k-1.

Your assumption is correct. The for comprehension will return the types of lists involved. Since placeQueens returns a Set[List[Int]] so will the for comprehension. The translation of your for comprehension is like this:

placeQueens(k-1).flatMap { queens => 
  (0 until n).withFilter { col => 
    isSafe(col, queens)
  }.map { col => 
    k::queens
  }
}