Hai mai giocato a scacchi? Se sì, sai già che la regina è il pezzo più importante e che può muovere qualsiasi numero di caselle in verticale, orizzontale o diagonale. Se non l’hai fatto, non preoccuparti: oggi impareremo solo come disporre 8 regine sulla scacchiera in modo che nessuna regina possa muoversi in una casella occupata da un’altra regina. In gergo scacchistico, diciamo che le regine non potranno attaccarsi a vicenda. Come facciamo a fare questo? Usiamo il backtracking.
L’algoritmo di backtracking trova una soluzione a problemi in cui alcuni vincoli devono essere rispettati. Prova tutte le possibili soluzioni fino a quando non trova quella corretta. Facciamo un esempio, con quattro regine e una piccola tavola. Cominceremo col piazzare la prima regina:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Ti mostrerà anche molte altre strategie computazionali che ti aiutano a risolvere problemi interessanti!
Ora che sai come funziona il backtracking, possiamo risolvere il problema delle 8 regine a grandezza naturale. Qui sotto, c’è una scacchiera con cui puoi giocare per esercitare le tue abilità e trovare una soluzione. Inizia a piazzare la prima regina cliccando sulla casella in alto a sinistra della scacchiera. Vedrai che la regina che hai piazzato sarà elencata nella lista “Regine attuali”.
Regine attuali
Puoi ora piazzare un’altra regina in una posizione che impedisca loro di attaccarsi a vicenda. La nostra prima regina è in a8, la seconda, per esempio, può essere messa in c7. Continuate a piazzare le regine fino a quando non c’è più nessuna casella sicura sulla scacchiera. A quel punto, è il momento di fare marcia indietro cliccando su “annulla”. Questo cancellerà l’ultima regina che hai piazzato e ti permetterà di scegliere un’altra casella per piazzarla. Puoi anche rimuovere una regina dalla scacchiera cliccando direttamente su di essa.
Giocando al gioco interattivo, puoi iniziare a farti un’idea del backtracking. Come esseri umani, può diventare difficile per noi tenere traccia di tutti i precedenti posizionamenti della regina. È qui che la programmazione aiuta! Qui sotto, puoi trovare un’animazione generata da un programma che dimostra le sue impeccabili capacità di backtracking:
Pseudocodice:
- Inizia a piazzare la prima regina sulla casella in alto a sinistra della scacchiera.
- Se abbiamo piazzato le 8 regine, abbiamo finito. Altrimenti, è possibile piazzare un’altra regina in una posizione sicura?
- Se sì, allora segnalo come parte della soluzione, e torna al punto 2.
- Se no, allora cambia la posizione della regina precedente (backtracking) e torna al punto 2.