El algoritmo utilizado para resolver el problema de 8 reinas o el problema de N reinas en general es: Retroceso
Backtracking es un algoritmo recursivo que funciona según el siguiente principio:
- De la lista de todas las opciones, elija una opción en particular.
- Compruebe si la opción elegida es segura o correcta. Por ejemplo: en este problema, se dice que la opción es segura cuando una Reina no está amenazada por ninguna otra Reina cuando esa opción se elige como un movimiento. Si la opción es segura, siga avanzando hasta que se alcance la condición final o se encuentre una opción insegura. Si se alcanza la condición final, devuelva True.
- Si la opción elegida no es segura, devuelve False y Backtrack. Elija la opción alternativa después de Backtracking. Si todas las opciones están agotadas, devuelve False.
- ¿Hay algún truco para que un programador de computadoras recuerde el código de un tipo de burbuja?
- ¿Cuál es el mejor algoritmo para encontrar si 3 números son coprimos? ¿Como funciona?
- Cómo implementar este problema: Problema - C - Fuerzas de código
- Cómo reconocer un problema como un problema de programación dinámica
- ¿Para qué sirve un tamaño de obtención de matriz?
Aquí está el código que escribí en C implementando el algoritmo Backtracking:
#include
#include // usa el archivo de encabezado stdbool para importar palabras clave verdaderas y falsas
#define N 8 // N se puede reemplazar con cualquier número
int junta [N] [N]; // Matriz AN * N que almacenará la información sobre) sy 1s en el tablero
int mueve [N] [2]; // matriz AN * 2 que almacenará los movimientos realizados
bool csafe (int count, int y) // Una función de utilidad para verificar si la columna en la que se colocará la reina es segura
{
int i;
para (i = 0; i <cuenta; i ++)
{
if (tablero [i] [y] == 1)
falso retorno;
}
volver verdadero;
}
bool digsafe (int x, int y) // Una función de utilidad para verificar si la reina es diagonalmente segura
{
bool flag1 = verdadero, flag2 = verdadero;
int tempx = x, tempy = y;
para (; x> = 0 && y> = 0; x–, y–)
{
if (tablero [x] [y] == 1)
{
flag1 = falso;
descanso;
}
}
para (; tempy = 0; tempx–, tempy ++)
{
if (tablero [tempx] [tempy] == 1)
{
flag2 = falso;
descanso;
}
}
if (flag1 == verdadero && flag2 == verdadero)
volver verdadero;
falso retorno;
}
bool issafe (int count, int y) // Una función bool que devuelve verdadero o falso independientemente de si la posición es segura
{
if (csafe (cuenta, y) == verdadero && digsafe (cuenta, y) == verdadero)
volver verdadero;
falso retorno;
}
bool placequeen (int count) // Una función para colocar reinas de forma recursiva
{
int i;
si (cuenta == N)
volver verdadero; // devuelve verdadero cuando todas las reinas ya están colocadas
para (i = 0; i <N; i ++)
{
if (issafe (cuenta, i) == verdadero)
{
tablero [cuenta] [i] = 1;
mueve [cuenta] [0] = cuenta;
mueve [cuenta] [1] = i;
if (placequeen (cuenta + 1) == verdadero)
volver verdadero; // Si la siguiente pila devuelve verdadero, devuelve verdadero
tablero [cuenta] [i] = 0;
}
}
falso retorno; // Si todos los movimientos posibles intentaron devolver falso
}
int main ()
{
int i, j;
para (i = 0; i <N; i ++)
{
para (j = 0; j <N; j ++)
tablero [i] [j] = 0; // inicializa el tablero completo a cero.
}
if (placequeen (0) == verdadero)
{
para (i = 0; i <N; i ++)
{
printf (“% d,% d”, mueve [i] [0], mueve [i] [1]);
printf (“\ n”);
}
}
más
printf (“No es posible:”);
devuelve 0;
}
El código está escrito para N Queens en general. Puede reemplazar la expansión de macro 8 con cualquier valor general.
