Si consiglia la visione delle attività “La stanza cinese“, “Un robot su Marte” e “Introduzione alle funzioni” .

Materiale

Una copia della scheda degli 8 polpi per ogni studente

Età

A partire dai 7 anni

Numero di giocatori

Attività individuale

Competenze acquisite

Obiettivi di apprendimento al termine della classe quinta della scuola primaria

Ambito algoritmi
O-P5-A-1. Utilizzare il ragionamento logico per spiegare il funzionamento di alcuni semplici algoritmi

Ambito algoritmi
O-P5-A-2. Risolvere problemi mediante la loro scomposizione in parti più piccole

Ambito programmazione
O-P5-P-2. Scrivere cicli per ripetere una stessa azione mentre permane una condizione verificabile in modo semplice

Ambito programmazione
O-P5-P-3. Riconoscere che una sequenza di istruzioni può essere considerata come un’unica azione oggetto di ripetizione o selezione

Ambito programmazione
O-P5-P-5. Esplorare l’uso della selezione a due vie per attuare azioni mutuamente esclusive all’interno di programmi semplici

Obiettivi di apprendimento al termine della classe terza della scuola secondaria di primo grado

Ambito programmazione
O-M-P-2. Scrivere programmi che usano l’annidamento di cicli e selezioni

Attività per introdurre la classe alla visita in profondità con backtracking (un algoritmo non informato).

Per questo gioco sono stati pensati tre diversi livelli di difficoltà: facile (che corrisponde alla prima scheda, in cui vi sono 3 scogli), intermedio (la seconda scheda con 2 scogli) e per esperti (la terza scheda senza alcuno scoglio). E’ comunque consigliato partire dal livello facile e, se gli studenti non presentano troppe difficoltà, si può allora proseguire con le schede successive. Consegnate ad ogni alunno una scheda del livello di difficoltà scelto.

1. Spiegare agli studenti lo scopo del rompicapo: consiste nel posizionare 8 polpi sulla griglia tenendo conto di questo vincolo: nessun polpo deve “acchiapparne” un altro (si immagina infatti che i polpi possano prendersi a vicenda usando i propri tentacoli). Per “acchiappare” si intende:

prendere un altro polpo che si trova sulla stessa linea orizzontale, verticale o diagonale.

Se tra due polpi si trova uno scoglio, allora questi non riescono ad acchiapparsi, e possono quindi stare sulla stessa linea.

2. Lasciare che gli studenti provino da soli a trovare una soluzione (da notare che ci possono essere più soluzioni possibili per una stessa griglia), lasciando all’incirca un quarto d’ora di tempo.
3. Allo scadere del tempo, valutare se le soluzioni fornite dagli studenti sono corrette.
4. Far ragionare la classe sull’approccio utilizzato avviando la seguente discussione conclusiva.

Vediamo un esempio di soluzione per la prima scheda (difficoltà facile). Capirne il meccanismo porterà la classe ad elaborare un algoritmo corretto per risolvere il rompicapo degli 8 polpi.

Manca solamente un polpo: tuttavia non sappiamo dove posizionarlo! Se non vogliamo che acchiappi nessun polpo di tutti quelli già posizionati (senza considerare gli ultimi due inseriti), restano solo queste posizioni: D0, F6, H0, H2 (verificare sulla griglia, per aiutarsi scartare le caselle in cui si sa a priori che non è possibile inserire un polpo; ovvero, ogni volta che si posiziona un nuovo polpo, si scartano le caselle sulle stesse linee orizzontali, verticali e diagonali). Nessuna di queste posizioni ci è però d’aiuto, perchè un nuovo polpo verrà acchiappato dal sesto e/o dal settimo polpo!

Come fare? Si applica un meccanismo chiamato backtracking (dall’inglese “tornare indietro”): ritorno al polpo precedente (il settimo, in questo caso) e provo a cercare una posizione alternativa in modo che si riesca a posizionare l’ultimo senza problemi. Se non trovo nessuna posizione alternativa allora provo col polpo ancora prima (il sesto) e così via… fino a quando non riuscirò a sistemarli tutti senza che si acchiappino!

Quindi, proviamo a spostare il settimo (che ora è in C0): l’unica posizione alternativa possibile è in D0, ma non risolve il problema (non si riesce ancora a posizionare l’ottavo polpo).

Allora concentriamoci sul sesto polpo; ci sono tre posizioni alternative possibili:

• in H0: ma viene acchiappato dal settimo (in C0);
• in F6 o in H2: finalmente non crea problemi!

Perciò se scegliamo di mettere il sesto polpo in F6, avremo il settimo in C0 e l’ottavo in H2 (viceversa, se decidiamo di posizionare il sesto in H2, allora il settimo sarà in C0 e l’ottavo in F6).

Abbiamo risolto il gioco!

Spiegare alla classe che questo tipo di approccio si chiama visita in profondità con backtracking: 

• visita in profondità: perché si continuano a posizionare polpi fino a quando non si è bloccati;
• quando non si riesce a proseguire, entra in gioco il backtracking: si “ritorna indietro”, ovvero, ci si focalizza sull’ultimo polpo inserito e si cercano altre posizioni possibili che possano risolvere il blocco; se non se ne trova nessuna, si ritorna al penultimo polpo inserito, si cercano altre posizioni… e così via, fino a quando non si riesce a posizionarli tutti correttamente.

La visita in profondità con backtracking è un esempio di algoritmo non informato. Si tratta di algoritmi che non sfruttano informazioni aggiuntive per gli stati, ma si basano solo sulla definizione data del problema.

Il meccanismo della visita in profondità con backtracking può essere sintetizzato con un algoritmo. Si può decidere di far lavorare gli studenti a gruppi in modo che provino a scrivere l’algoritmo per conto loro, se hanno una buona conoscenza delle istruzioni condizionali e dei cicli.

In caso contrario, scrivere l’algoritmo seguente alla lavagna e spiegare le parti che gli studenti faticano a comprendere, basandosi sulla spiegazione dell’esempio appena terminata:

1. finchè non hai inserito tutti gli 8 polpi {
	2. inserisci un nuovo polpo
	3. se il polpo appena inserito non ne acchiappa nessun altro {
		4. inserisci il polpo successivo e ripeti dall’istruzione 2.
	}
	5. altrimenti {
		6. prova a spostare il polpo in un’altra posizione finchè non trovi una posizione adatta
		7. se non trovi una posizione adatta {
			8. ritorna al polpo precedente e ripeti dall’istruzione 6.
		}
	}	
}

L’istruzione 2 viene effettuata ogni volta che si posiziona un nuovo polpo. Le istruzioni 3 e 4 corrispondono, ad esempio, alla parte della soluzione in cui posizioniamo il primo e il secondo polpo (o il secondo e il terzo). Le istruzioni 5 e 6 sono eseguite nel momento in cui si prova a inserire il quarto polpo prima in E1, per poi correggere inserendolo in F1. Infine, il backtracking coincide con le istruzioni 7 e 8.

Per concludere, come nell’attività 2 del capitolo di introduzione, si possono porre queste domande alla classe:

• qual è il problema espresso in questo esercizio? Disporre gli 8 polpi sulla griglia senza che si acchiappino;
• cosa sono gli stati? Sono le varie caselle della griglia;
• quali sono le azioni? Posizionare un polpo sulla griglia e spostarlo;
• qual è l’obiettivo (e quindi lo stato obiettivo)? Nessuno degli 8 polpi deve essere acchiappato da un altro;
• qual è lo stato iniziale? La griglia vuota;
• qual è la funzione costo? Ogni posizionamento e ogni spostamento hanno lo stesso costo (che possiamo supporre sia uguale a 1).