Backtracking – abbiamo lasciato l'aula!

Sfruttando gli scacchi giganti che si trovano nel cortile dell'ESI, la lezione odierna è consistita nello svolgere tre attività alla scacchiera con lo scopo di illustrare e consolidare alcune nozioni di base su backtracking, che è l'argomento che abbiamo iniziato a studiare questa settimana nell'ambito della Metodologia di programmazione.

Questa tecnica di risoluzione dei problemi è spesso presentata, sia in classe che nei manuali di riferimento, con alcuni esempi di base disposti su una scacchiera. La più nota è quella che consiste nel mettere 8 regine sul tabellone senza minacciarsi a vicenda. Un altro esempio tipico è quello di attraversare le caselle del tabellone con i movimenti di un cavaliere senza percorrerlo due volte. Ma c'è anche un esempio molto intuitivo per loro, che sta cercando di trovare la via d'uscita da un labirinto, che può essere rappresentato anche da una scacchiera.

Poiché la tecnica di backtracking fa una ricerca nello spazio di tutti gli stati possibili, il numero di mosse che bisogna fare per generare questo spazio di stati su una scacchiera, 8×8 caselle, è enorme. Pertanto, abbiamo "diviso" la scheda a 8 × 8 celle in quattro schede più semplici a 4 × 4 celle, il che consente anche di presentare 4 problemi contemporaneamente.

Gli studenti sono stati così divisi in 4 gruppi, ognuno dei quali ha lavorato su un quadrante e su una versione diversa di ciascuno dei tre problemi. Inoltre, ad ogni gruppo è stata fornita una scheda, che hanno completato durante la risoluzione del problema, in cui domande sui concetti di base relativi al backtracking.

Durante tutto il processo, il ruolo della professoressa Carmen Lacave è stato quello di aiutare ogni gruppo a cercare di risolvere i dubbi sorti o correggere alcune idee sbagliate. E, soprattutto, ringraziarli per la loro buona disposizione nonostante il freddo e la quantità di pioggia caduta durante lo svolgimento delle attività. Spero che domani, all'ora che ha l'altro gruppo, il termostato del patio venga regolato meglio 😉