The N Queen is the problem of placing N chess queens on anN×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem. The expected output is a binary matrix which has 1s for the blocks where queens are placed. http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

Using Sets and for-expressions with Scala we can reach a solution very directly:

def queens(n: Int): Set[List[Int]] = {

  def placeQueens(k: Int): Set[List[Int]] =
    if (k == 0) Set(List())
    else //en general tenemos que poner k queens para lo que primero tenemos que poner k-1
      for {
        sol <- placeQueens(k - 1)
        elem <- 0 until n - 1
        if libre(elem, sol)

      } yield (elem :: sol)

  placeQueens(n)

}

In this algorithm we are given an n parameter which represent how many queens we are going to place at the same time as how many rows and columns do we have in the board.

With that in mind we calculate a set of lists and each of these lists has a column position for each row in every position of the list.

The head of the list represent the row n-1 while the end of the list represents the row 0.

We use a recursive algorithm with the auxiliary function placeQueens which uses a for-expresions that takes every solution of placeQueens for k-1 elements by means of a smart recursive call

Knowing the solutions for placing k-1 queens in a (k-1)* N board we try the possible places of a queen in the k row in the possible N columns

In the top level we call this auxiliary function with placeQueens(n) and so we obtain the solution.

We have also to implement a function that tells us if a queen is safe in a given column of the k row having the partial solution for k-1 queens, this is quite simple as follows:


def isSafe(col: Int, queens: List[Int]): Boolean = {

  val row = queens.length
  val queensWithRow = (row - 1 to 0 by -1) zip queens
  queensWithRow forall {
    //comprobar que no está en check con la nueva
    case (r, c) => (col != c) && math.abs(col - c) != row - r
  }

}

We could also beautifully visualize the a solution with the following method:

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

I hope this have been helpful,

Peace