El problema de las N reinas

gistfile1.txt

El problema de las N reinas consiste en situar N reinas en un tablero de ajedrez de N x N sin que se amenacen entre ellas.
*Cosas por considerar:
-Una reina amenaza a otra si esta en la misma fila, la misma columna o en la misma diagonal.
-Solamente N=2 y N=3 no tienen soluciones.


El programa debe aceptar como entrada el valor de N, y debe regresar el numero de soluciones posibles y las soluciones representadas del alguna manera (una matriz con 1’s representando a las reinas, un vector con las posiciones de las reinas,
o cualquier forma que quieras elegir y sea eficiente)

Para probar el numero de soluciones validas aquí esta el resultado esperado para los primeros 10 tamaños:
N = 1 Soluciones posibles 1
N = 2 Soluciones posibles 0
N = 3 Soluciones posibles 0
N = 4 Soluciones posibles 2
N = 5 Soluciones posibles 10
N = 6 Soluciones posibles 4
N = 7 Soluciones posibles 40
N = 8 Soluciones posibles 92
N = 9 Soluciones posibles 352
N = 10 Soluciones posibles 724

Como un tip” Muchas soluciones son solo la rotación o vista espejo de una de las soluciones ya obtenidas, consideren evaluar
de esa manera para hacer mas eficiente el tiempo de respuesta.

Referencias utiles:
-El problema en si es simple, pero si queda alguna duda pueden leer mas detalles aquí https://developers.google.com/optimization/puzzles/queens#setup
Cuidado porque viene una posible solución en python en la sección de Solving N-queens para que tengan cuidado si leen esta
referencia.
-EL problema de las 8 reinas https://en.wikipedia.org/wiki/Eight_queens_puzzle tiene muchos años y es muy famoso, si juegan
ajedrez seguramente han escuchado al respecto.

This is not optimized

object Nqueen {

  case class Queen(x: Int, y: Int) // Queen with its position

  type Solution = List[Queen] // List of queens placed in the board
  type Solutions = List[Solution] // List of solutions

  def main(args: Array[String]): Unit = {
    solveNqueen(1)
    solveNqueen(2)
    solveNqueen(3)
    solveNqueen(4)
    solveNqueen(5)
    solveNqueen(6)
    solveNqueen(7)
    solveNqueen(8)
    solveNqueen(9)
    solveNqueen(10)
  }

  def solveNqueen(size: Int) {
    def placeQueens(n: Int): Solutions = n match {
      case 0 => List(Nil) // cannot be empty
      case _ => for {
        queens <- placeQueens(n - 1) // DFS recursive call, current solution
        y <- 1 to size
        queen = Queen(n, y) // creates a queen for each x,y combination (checks all the board)
        if isSafe(queen, queens) // if the queen is in a safe position
      } yield queen :: queens // it is added to the current solution, yields to Solutions
    }

    val solutions = placeQueens(size)
    println(s"N=$size, ${solutions.size} solutions found")

//    for (currentSol <- solutions) {
//      printSolution(size, currentSol)
//      println()
//    }
  }

  def isSafe(currentQueen: Queen, others: List[Queen]) =
    others forall (!isAttacked(currentQueen, _)) // others don't attack current

  def isAttacked(currentQueen: Queen, otherQueen: Queen) =
    currentQueen.x == otherQueen.x || // attacked in same row
      currentQueen.y == otherQueen.y || // attacked in same column
      (otherQueen.x - currentQueen.x).abs ==
        (otherQueen.y - currentQueen.y).abs // attacked in diagonal

  /*
  print the solutions in the form:
         ---> y
        |
        v
        x
  */
  def printSolution(size: Int, currentSol: Solution): Unit = {
    for (queen <- currentSol; y <- 1 to size) {
      if (queen.y == y) print("Q ") else print(". ")
      if (y == size) println()
    }
  }
}

Output:

N=2, 0 solutions found
N=3, 0 solutions found
N=4, 2 solutions found
N=5, 10 solutions found
N=6, 4 solutions found
N=7, 40 solutions found
N=8, 92 solutions found
N=9, 352 solutions found
N=10, 724 solutions found