Backtracking – ¡salimos del aula!

Aprovechando el ajedrez gigante que hay en el patio de la ESI, la clase de hoy ha consistido en realizar tres actividades sobre el tablero con el objetivo de ilustrar y afianzar algunas nociones básicas sobre backtracking, que es el tema que hemos comenzado a estudiar esta semana en la asignatura de Metodología de la Programación.

Esta técnica de resolución de problemas se suele presentar, tanto en clase como en los manuales de referencia, con algunos ejemplos básicos que se plantean sobre un tablero de ajedrez. El más conocido es el que consiste en colocar 8 reinas sobre el tablero sin que se amenacen entre sí. Otro ejemplo típico es el del recorrido de las casillas del tablero con los movimientos de un caballo sin pasar dos veces por la misma. Pero también hay un ejemplo muy intuitivo para ellos, que es el de intentar encontrar la salida a un laberinto, que se puede representar también mediante un tablero de ajedrez.

Puesto que la técnica de backtracking hace una búsqueda en el espacio de todos los estados posibles, la cantidad de movimientos que hay que realizar para generar este espacio de estados sobre un tablero de ajedrez, de 8×8 casillas, es descomunal. Por tanto, el tablero de 8×8 celdas lo hemos “dividido” en cuatro tableros más sencillos de 4×4 casillas, lo que permite, además, que se puedan plantear de forma simultánea 4 problemas.

Así pues, los y las estudiantes se han dividido en 4 grupos, cada uno de los cuales ha trabajado sobre un cuadrante y sobre una versión distinta de cada uno de los tres problemas. Además, a cada grupo se les ha proporcionado una ficha, que han ido completando mientras resolvían el problema, en la que se planteaban preguntas sobre conceptos básicos relacionados con el backtracking.

Durante todo el proceso, el papel de la profesora Carmen Lacave ha sido el de ayudar a cada grupo tratando de resolver las dudas que les iban surgiendo o corrigiendo algunos errores de concepto. Y, sobre todo, agradecerles su buena disposición a pesar del frío y la cantidad de lluvia que ha caído mientras realizaban las actividades. Espero que mañana, a la hora que le toca al otro grupo, esté mejor regulado el termostato del patio 😉