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.

import java.util.ArrayList;
import java.util.List;

class NQueensProblem {
    static int calculateSolutions(int n) {
        int[] arr = createZeroToNIntArray(n - 1);
        List<List<Integer>> validSolutions = new ArrayList<>();// The Integer Lists represent the positions of the
        // queens. The indexes are the x positions, and the values are the y positions.
        populateValidSolutions(arr, validSolutions, new ArrayList<>());
        return validSolutions.size();
    }

    private static int[] createZeroToNIntArray(int n) {
        int[] arr = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            arr[i] = i;
        }
        return arr;
    }

    static void populateValidSolutions(int[] arr, List<List<Integer>> validSolutions, List<Integer> queensYPosition) {
        /*
         *  Getting the permutations of the vertical positions of the queens, using DFS algorithm.
         */
        if (queensYPosition.size() == arr.length && !areDiagonalThreatens(queensYPosition)) {
            validSolutions.add(new ArrayList<>(queensYPosition));
        }
        for (int i : arr) {
            if (!queensYPosition.contains(i)) {
                queensYPosition.add(i);
                populateValidSolutions(arr, validSolutions, queensYPosition);
                queensYPosition.remove(queensYPosition.size() - 1);
            }
        }
    }

    static boolean areDiagonalThreatens(List<Integer> queensYPosition) {
        int n = queensYPosition.size();
        for (int i = 0; i < n; i++) {
            int min = Math.min(i, queensYPosition.get(i));
            int x = i - min;
            int y = queensYPosition.get(i) - min;
            while(x < n && y < n) {
                if(x != i && queensYPosition.get(x) == y) {
                    return true;
                }
                x++;
                y++;
            }
            x = n;
            y = queensYPosition.get(i) - n + i;
            while(x > 0 && y < n - 1) {
                x--;
                y++;
                if(x != i && queensYPosition.get(x) == y) {
                    return true;
                }
            }
        }
        return false;
    }
}

*aun planeo refactorizar en una oportunidad, pero ya funciona..
https://github.com/JannethAmaya/CodeChallenges/blob/master/NQueens.cs

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