TAREA 3.1: Infografía "Backtracking"

BACKTRACKING

¿Qué es?

El backtracking es un algoritmo de búsqueda exhaustiva que se utiliza para resolver problemas computacionales, especialmente aquellos que involucran la generación de posibles soluciones. Este enfoque se basa en la idea de construir soluciones paso a paso y, en caso de llegar a un punto donde la solución parcial no puede extenderse a una solución válida, retrocede (backtracks) para probar otras opciones.

Estructura general del algoritmo backtracking

1. Elección: Se realiza una elección para agregar un elemento a la solución parcial actual.

2. Exploración: Se explora la factibilidad de continuar con la elección actual.

3. Backtrack: Si la elección actual no conduce a una solución válida, se deshace y se prueba otra opción.

ejemplo de un problema que podría resolverse con backtracking

Problema de las N-Reinas

Descripción del Problema: Colocar N reinas en un tablero de ajedrez N × N de tal manera que ninguna reina amenace a otra. Las reinas pueden moverse horizontal, vertical o diagonalmente.

Ej Código

Este ejemplo muestra cómo el backtracking se utiliza para explorar todas las posibles configuraciones del tablero y encontrar soluciones al problema de las N-Reinas. La función es_seguro verifica si es seguro colocar una reina en una posición dada, y la función principal resolver_n_reinas utiliza el backtracking para probar diferentes configuraciones. El algoritmo se detiene cuando se encuentra una solución o se exploran todas las posibilidades.

Implementación en Backtracking:

def es_seguro(tablero, fila, columna, N): # Verifica si es seguro colocar una reina en la posición (fila, columna) # Comprueba la fila y las diagonales for i in range(fila): if tablero[i] == columna or \ tablero[i] - i == columna - fila or \ tablero[i] + i == columna + fila: return False return True def resolver_n_reinas(tablero, fila, N): # Caso base: todas las reinas están colocadas if fila == N: # Aquí 'tablero' contiene una solución válida print(tablero)

return # Intenta colocar una reina en cada columna de la fila actual for columna in range(N): if es_seguro(tablero, fila, columna, N): tablero[fila] = columna # Recursivamente intenta colocar la siguiente reina resolver_n_reinas(tablero, fila + 1, N) # Backtrack: deshace la elección actual tablero[fila] = -1 def n_reinas(N): # Inicializa un tablero vacío tablero = [-1] * N resolver_n_reinas(tablero, 0, N) # Ejemplo de uso para el problema de las 8 reinas n_reinas(8)