Aquí tienes la explicación línea por línea del código:
Clase Main
import java.util.Scanner;
Importa la clase Scanner para leer la entrada del usuario.
public class Main {
Define la clase principal Main.
public static void main(String[] args) {
Método principal donde comienza la ejecución del programa.
Scanner scanner = new Scanner(System.in);
System.out.print("Ingrese el valor de N (máximo 8): ");
int N = scanner.nextInt();
scanner.close();
Crea un objeto Scanner para leer la entrada del usuario.
Solicita al usuario ingresar un valor para N (tamaño del tablero).
Cierra el Scanner después de leer el valor.
if (N > 8 || N < 1) {
System.out.println("N debe estar entre 1 y 8.");
return;
}
Verifica que N esté entre 1 y 8. Si no es válido, muestra un mensaje de
error y finaliza el programa.
NQueens queens = new NQueens(N);
queens.solve();
Crea un objeto NQueens con el valor N proporcionado.
Llama al método solve() para resolver el problema.
Clase NQueens
class NQueens {
Define la clase NQueens, que implementa el algoritmo de backtracking.
private int N;
private int board[][];
private int solutionCount;
private final int MAX_SOLUTIONS = 10;
N: Tamaño del tablero (N x N).
board[][]: Matriz para representar el tablero.
solutionCount: Contador de soluciones encontradas.
MAX_SOLUTIONS: Límite de soluciones a mostrar (10).
public NQueens(int N) {
this.N = N;
board = new int[N][N];
solutionCount = 0;
}
Constructor de la clase NQueens. Inicializa N, board y solutionCount.
Método solve()
public void solve() {
solveNQUtil(0);
if (solutionCount == 0) {
System.out.println("No hay solución");
} else {
System.out.println("Número total de soluciones mostradas: " +
solutionCount);
}
}
Llama al método solveNQUtil(0) para empezar a colocar reinas desde la
columna 0.
Si no encuentra soluciones, muestra un mensaje.
Si encuentra soluciones, imprime la cantidad encontrada.
Método solveNQUtil(int col) (Backtracking)
private void solveNQUtil(int col) {
if (solutionCount >= MAX_SOLUTIONS) {
return;
}
Si ya se encontraron 10 soluciones, detiene la búsqueda.
if (col >= N) {
printSolution();
solutionCount++;
return;
}
Si todas las reinas han sido colocadas (col >= N), imprime la solución y
aumenta el contador.
for (int i = 0; i < N; i++) {
if (isSafe(i, col)) {
board[i][col] = 1;
solveNQUtil(col + 1);
board[i][col] = 0;
}
}
}
Intenta colocar una reina en cada fila de la columna col.
Usa isSafe() para verificar si la posición es válida.
Si es segura, coloca la reina (board[i][col] = 1).
Llama recursivamente a solveNQUtil(col + 1).
Deshace la colocación (board[i][col] = 0) para probar otras opciones.
Método isSafe(int row, int col)
private boolean isSafe(int row, int col) {
Verifica si es seguro colocar una reina en la posición (row, col).
for (int i = 0; i < col; i++)
if (board[row][i] == 1) return false;
Verifica que no haya otra reina en la misma fila.
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1) return false;
Verifica la diagonal superior izquierda.
for (int i = row, j = col; i < N && j >= 0; i++, j--)
if (board[i][j] == 1) return false;
Verifica la diagonal inferior izquierda.
return true;
}
Si ninguna de las condiciones anteriores falló, la posición es segura.
Método printSolution()
private void printSolution() {
System.out.println("Solución " + (solutionCount + 1) + ":");
Imprime el número de la solución.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print((board[i][j] == 1 ? "Q " : "- "));
}
System.out.println();
}
System.out.println();
}
Recorre la matriz board[][] e imprime el tablero.
Usa "Q " para representar una reina y "- " para una celda vacía.
Resumen
1. Lee N del usuario (máximo 8).
2. Inicializa el tablero y empieza el proceso con solveNQUtil(0).
3. Usa backtracking para colocar reinas columna por columna.
4. Verifica si es seguro colocar cada reina con isSafe().
5. Encuentra hasta 10 soluciones y las imprime con printSolution().
Ejemplo de Ejecución
Entrada:
plaintext
CopiarEditar
Ingrese el valor de N (máximo 8): 4
El usuario elige N = 4, por lo que el programa intentará colocar 4 reinas en un
tablero de 4x4.
Paso a Paso de la Ejecución
1. Se inicializa el tablero:
plaintext
CopiarEditar
----
----
----
----
(Cada "-" representa una celda vacía).
2. El algoritmo coloca la primera reina (Q) en la primera columna
(col = 0):
o Intenta la primera fila (row = 0) y la coloca porque el tablero está
vacío.
plaintext
CopiarEditar
Q---
----
----
----
3. Pasa a la segunda columna (col = 1):
o row = 0 no es seguro (ya hay una reina en esa fila).
o row = 1 tampoco es seguro (diagonal superior izquierda).
o row = 2 es seguro → coloca la reina aquí:
plaintext
CopiarEditar
Q---
----
-Q--
----
4. Pasa a la tercera columna (col = 2):
o row = 0 y row = 1 no son seguros.
o row = 2 no es seguro (misma fila).
o row = 3 es seguro → coloca la reina aquí:
plaintext
CopiarEditar
Q---
----
-Q--
--Q-
5. Pasa a la cuarta columna (col = 3):
o row = 0 y row = 1 no son seguros.
o row = 2 y row = 3 tampoco.
o No hay lugares seguros → retrocede (backtracking).
Backtracking (Deshacer Últimos Pasos)
1. Quita la reina de (row = 3, col = 2) y prueba otra opción.
2. Quita la reina de (row = 2, col = 1) y prueba otro lugar.
3. Prueba con la reina en (row = 1, col = 1) → sigue probando.
Después de más intentos, encuentra la primera solución:
plaintext
CopiarEditar
-Q--
---Q
Q---
--Q-
Imprime:
plaintext
CopiarEditar
Solución 1:
-Q--
---Q
Q---
--Q-
Encuentra más soluciones (hasta 10)
El proceso continúa hasta encontrar 10 soluciones como máximo. Cada vez
que encuentra una, la imprime y sigue buscando más. Cuando ha mostrado 10
soluciones o ya no hay más disponibles, termina la ejecución.
Salida Final del Programa
plaintext
CopiarEditar
Ingrese el valor de N (máximo 8): 4
Solución 1:
-Q--
---Q
Q---
--Q-
Solución 2:
--Q-
Q---
---Q
-Q--
Número total de soluciones mostradas: 2
Resumen de la Ejecución
1. El usuario ingresa N → Se crea el tablero N x N.
2. Backtracking coloca reinas columna por columna.
3. Si encuentra una solución completa, la imprime.
4. Si no hay más movimientos posibles, retrocede y prueba otra
configuración.
5. Muestra un máximo de 10 soluciones antes de terminar.
