# NQueen problem solution traversal

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.

OT, but since this isnâ€™t your code you should reference the author