Problema de las ocho reinas en Java
Este tutorial demuestra el problema de las ocho reinas en Java.
Problema de las ocho reinas en Java
El problema de las ocho reinas es que tenemos que colocar ocho reinas en un tablero de ajedrez de 8x8 de manera que no se ataquen entre sí. Eso significa que dos reinas no pueden estar en la misma fila, columna o diagonal porque las reinas pueden moverse en eso en el ajedrez.
El retroceso se puede utilizar para resolver el problema de Eight Queens o N-Queens en Java. Entonces, primero, analicemos el algoritmo de retroceso.
Use el algoritmo de seguimiento posterior para el problema de las ocho reinas
La idea de resolver el problema de las ocho reinas usando el algoritmo de retroceso es colocar individualmente las reinas en diferentes columnas comenzando desde la columna más a la izquierda. Ponemos una reina en una columna y luego verificamos el choque con otras reinas que se colocaron previamente.
Luego, en una columna, si una fila no está en conflicto, marcamos tanto la columna como la fila como parte de la solución al problema de las ocho reinas. El retroceso se utilizará si no encontramos una situación que no esté en conflicto y devolvemos falso.
Aquí está el proceso paso a paso para resolver el problema de las ocho reinas usando el algoritmo de retroceso:
-
En primer lugar, comience desde la columna más a la izquierda.
-
Establezca una condición para que el código devuelva verdadero si se colocan todas las reinas.
-
Ahora haga lo siguiente y pruebe cada fila en una columna:
- Si una reina se coloca de forma segura en una fila, entonces esta fila y columna se marcarán como la parte de la solución que se comprueba recursivamente para otras soluciones.
- Si una reina se coloca de forma segura en una fila, devuelve verdadero.
- Si una reina no se coloca de forma segura en una fila, desmarque la fila y la columna, retroceda la solución, vuelva a la primera opción y aplique la solución a otras filas.
-
Si hemos verificado todas las filas y no hay solución, debemos devolver falso para activar el algoritmo de retroceso.
Ahora intentemos implementar un ejemplo basado en los pasos anteriores:
package delftstack;
public class EightQueen {
// Size of the board should be 8x8 for the eight queens problem
public static final int SIZE_OF_BOARD = 8;
boolean[][] BOARD_BOOLEAN;
// For an empty place
public static final boolean EMPTY_PLACE = false;
// For a place that contains a queen
public static final boolean QUEEN_PLACE = true;
// The number of moves
public static final int MOVES_NUMBER = 4;
// The horizontal moves
int[] Horizontal_Moves;
// The Vertical moves
int[] Vertical_Moves;
public int Queens = 0;
public EightQueen() {
// Constructor creates an empty board
BOARD_BOOLEAN = new boolean[SIZE_OF_BOARD][SIZE_OF_BOARD];
for (int row = 0; row < BOARD_BOOLEAN.length; row++) {
for (int col = 0; col < BOARD_BOOLEAN[row].length; col++) {
BOARD_BOOLEAN[row][col] = EMPTY_PLACE;
}
}
Horizontal_Moves = new int[MOVES_NUMBER];
Vertical_Moves = new int[MOVES_NUMBER];
// move up right
Horizontal_Moves[0] = -1;
Vertical_Moves[0] = 1;
// move down left
Horizontal_Moves[1] = 1;
Vertical_Moves[1] = -1;
// move up left
Horizontal_Moves[2] = -1;
Vertical_Moves[2] = -1;
// move down right
Horizontal_Moves[3] = 1;
Vertical_Moves[3] = 1;
}
public boolean Queens_Placing(int Board_Column) {
if (Board_Column >= SIZE_OF_BOARD) {
return true;
} else {
boolean Queen_Placed = false;
int Board_Row = 0;
while (!Queen_Placed && Board_Row < SIZE_OF_BOARD) {
if (Queen_UnderAttack(Board_Row, Board_Column)) {
++Board_Row;
} else {
Set_Queen(Board_Row, Board_Column);
Queen_Placed = Queens_Placing(Board_Column + 1);
if (!Queen_Placed) {
Remove_Queen(Board_Row, Board_Column);
++Board_Row;
}
}
}
return Queen_Placed;
}
}
private void Remove_Queen(int Board_Row, int Board_Column) {
BOARD_BOOLEAN[Board_Row][Board_Column] = EMPTY_PLACE;
// Remove the comment from the code below to check which place the queen was removed.
// System.out.printf("The queen is REMOVED from [%d][%d]\n", Board_Row, Board_Column);
--Queens;
}
private void Set_Queen(int Board_Row, int Board_Column) {
BOARD_BOOLEAN[Board_Row][Board_Column] = QUEEN_PLACE;
// Remove the comments from the code below to check where the queen was placed
// System.out.printf("The queen is PLACED in [%d][%d]\n", Board_Row, Board_Column);
++Queens;
}
public boolean Queen_UnderAttack(int Board_Row, int Board_Column) {
boolean Queen_Condition = false;
// check the row
for (int Column = 0; Column < SIZE_OF_BOARD; Column++) {
if ((BOARD_BOOLEAN[Board_Row][Column] == true)) {
Queen_Condition = true;
}
}
// check the column
for (int Row = 0; Row < BOARD_BOOLEAN.length; Row++) {
if (BOARD_BOOLEAN[Row][Board_Column] == true) {
Queen_Condition = true;
}
}
// check the diagonal
for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column < 8;
Row += Horizontal_Moves[0], Column += Vertical_Moves[0]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column >= 0;
Row += Horizontal_Moves[1], Column += Vertical_Moves[1]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column >= 0;
Row += Horizontal_Moves[2], Column += Vertical_Moves[2]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column < 8;
Row += Horizontal_Moves[3], Column += Vertical_Moves[3]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
return Queen_Condition;
}
public void Display_Board() {
int Count = 0;
for (int Board_Row = 0; Board_Row < BOARD_BOOLEAN.length; Board_Row++) {
for (int Board_Column = 0; Board_Column < BOARD_BOOLEAN[Board_Row].length; Board_Column++) {
if (BOARD_BOOLEAN[Board_Row][Board_Column] == true) {
System.out.printf("|%s| ", " Q ");
Count++;
} else {
System.out.printf("|%s| ", " X ");
}
}
System.out.println();
}
System.out.printf("%d queens problem is solved, the queens are placed.\n", Count);
}
public static void main(String[] arg) {
EightQueen EightQueen_Problem = new EightQueen();
EightQueen_Problem.Queens_Placing(0);
EightQueen_Problem.Display_Board();
}
}
El código anterior implementa el problema de las ocho reinas utilizando la solución del algoritmo de retroceso. Colocará a las reinas donde no puedan matarse entre sí.
Vea la salida donde Q denota las reinas:
| Q | | X | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | Q | | X |
| X | | X | | X | | X | | Q | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | X | | Q |
| X | | Q | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | Q | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | Q | | X | | X |
| X | | X | | Q | | X | | X | | X | | X | | X |
8 queens problem is solved, the queens are placed.
La complejidad temporal del algoritmo anterior es O(N!), y el espacio auxiliar es O(N2).
Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.
LinkedIn Facebook