Following is a code snippet for solving NQueen problem;
type Queen = (Int, Int)
type Solutions = List[List[Queen]]
def placeQueens(n: Int): Solutions = n match {
case 0 => {
List(Nil)
}
case _ => for {
queens ← placeQueens(n -1)
y ← 1 to size
queen = (n, y)
if (isSafe(queen, queens)) // isSafe checks safe positioning
} yield queen :: queens
}
placeQueens(size) // size is board size
How does this code traverse all the possible solutions?
Note that y is iterated until size not until n, so placeQueens(n) will give you all possible solutions for a n * size field, not a square, i.e. for all rows up to n. The size value is missing in your example, but the important part is that it is constant over all recursion steps.
This means, that placeQueens(1) will give you size lists, with a single queen each ((1, 1) to (1, size)).
Now for placeQueens(2), you take each of these lists, and for each you try all possible positions for a queen in the second row. For each position, that is safe, yield queen :: queens will return a list with that new position added, so you get several new lists per solution from queens (at most 2 * size, if each position was valid) and so on, until you reach the last row and have all possible solutions.
It uses the constraint that each Queen has to have a different x-coordinate.