Diversi anni dopo la pubblicazione di questa risposta, ci è stato segnalato che un gruppo di sviluppatori ne ha tratto ispirazione per realizzare un gioco per Android e iOS.
Il gioco si chiama SquareOFF ed è disponibile sia su Google Play sia su Apple Store“
Affronto volentieri la soluzione di questo gioco, che sembra essere decisamente popolare tra gli studenti di scuola superiore (per lo meno, giudicando quelli a cui mi sono trovato a insegnare io).
Preciso da subito che non intendo darne la soluzione subito, ma piuttosto raccontare la strategia con la quale l’ho risolto io quando, a suo tempo, mi è stato proposto. Oltretutto, non pretendo neanche che la strada che propongo sia la più semplice o la più elegante: spero comunque che i miei suggerimenti possano sembrare interessanti o, per lo meno, non banali.
Per affrontare un problema, spesso conviene iniziare dalla soluzione di un problema più semplice. Capita infatti a volte che un problema più “piccolo” del problema che dobbiamo affrontare ammetta una soluzione dalla quale si possono trarre interessanti suggerimenti per la soluzione del problema maggiore; a volte, anzi, capita addirittura che la soluzione del problema minore si possa estendere in modo quasi immediato al problema maggiore. Con questo spirito ho provato per
prima cosa a risolvere lo stesso gioco in una scacchiera 5 x 5, dove una strategia di riempimento si trova abbastanza
rapidamente (invito il lettore a provarci; qui si trova comunque una possibile soluzione ad uso di chi decidesse di arrendersi).
La speranza sarebbe stata a questo punto quella di poter trovare un modo di iniziare e finire il riempimento di questa scacchiera da due punti situati in modo tale da permettere di riempire la scacchiera 10 x 10 dividendola in quattro quadrati 5 x 5.
Purtroppo non ho trovato altrettanto facilmente una soluzione a questa variante del problema. In compenso, la ricerca della soluzione del problema 5 x 5 mi aveva fatto notare che:
- dopo un po’ mi era venuto piuttosto spontaneo cercare soluzioni “simmetriche”: in effetti, riuscendo a scrivere i numeri da 1 a 13 in modo tale che il 13 venga scritto nella casella centrale e che rimangano vuote le posizioni simmetriche rispetto al centro di tutti i numeri tra 1 e 12, i numeri da 14 a 25 possono essere collocati senza fatica;
- anche in considerazione di quanto detto sopra, sembrava più facile cercare di muoversi in diagonale soltanto quando si fossero già raggiunte tutte le caselle che si potevano raggiungere per movimenti orizzontali o verticali;
- se “tutti i movimenti orizzontali” potevano essere effettuati in più di un modo (per esempio, iniziando dalla casella in alto a sinistra, i numeri 1, 2, 3, 4 possono essere collocati ai vertici di un quadrato 4 x 4 sia procedendo in senso orario sia procedendo in senso antiorario), non tutti i modi diversi permettevano di trovare una soluzione. Bisognava allora riflettere su quale fosse il modo giusto di “riempire” una griglia in modo da arrivare in un punto dal quale fosse possibile passare a una griglia ancora vuota.
ìA proposito di queste osservazioni, si noti che la soluzione proposta possiede in effetti le proprietà 1 e 2. Si noti anche che se si segue la strategia suggerita fino al numero 14 e (“dimenticando” il vincolo di simmetria) si scrivono i numeri 15, 16, 17 in senso antiorario invece che in senso orario, dal numero 17 non si riuscirà più a raggiungere nessuna casella vuota:ì
Ho allora provato a applicare queste considerazioni al problema 10 x 10. La prima decisione è stata quella di continuare a cercare strategie che affrontassero una mossa diagonale soltanto dopo aver “riempito” tutte le caselle che si potevano raggiungere con movimenti diagonali. L’effetto è stato quello di dividere la scacchiera in nove sottoinsiemi di caselle collegate tra loro da mosse diagonali, che con termine da matematico tra me e me chiamavo orbite:
Da un esame della figura qui sopra ci si rende conto che esistono quattro orbite quadrate di 3 x 3 elementi (E, F, H e I), due orbite rettangolari 3 x 4 (B, C) e due rettangolari 4 x 3 (D, G) e, infine, una sola orbita quadrata 4 x 4 (A). Vale poi la pena di notare che da ogni orbita è possibile “passare” tramite una mossa diagonale a quattro (e soltanto quattro) delle altre otto: questa situazione può essere rappresentata in modo piuttosto efficace dal grafo qui sotto.
Scegliere la successione con la quale riempire tutte le orbite significa allora semplicemente scegliere un cammino nel grafo appena visto che tocchi tutti i nodi una e una sola volta. Questo cammino, però, non può essere scelto in modo completamente casuale: cerchiamo di capire perché.
Osserviamo che, mentre le orbite 3 x 4 (o 4 x 3) e l’orbita 4 x 4 possono essere riempite iniziando da qualsiasi loro casella (provare per credere!), le orbite 3 x 3 non possono essere riempite completamente iniziando da una casella che si trovi a metà di uno dei lati ma soltanto a partire dai quattro vertici oppure dal centro.
Questo suggerisce un altro ragionamento che poi si dimostrera` fondamentale per arrivare alla soluzione. Se coloriamo le caselle a colori alternati come in una scacchiera “classica”, possiamo osservare che i movimenti in orizzontale ci portano sempre in una casella di colore diverso rispetto alla casella di partenza, mentre i movimenti in diagonale ci portano verso una casella dello stesso colore di quella di partenza. Notiamo allora che quando avremo finito di riempire un’orbita con un numero pari di caselle (A, B, C, D, G) ci troveremo in una casella di colore diverso da quello della casella di partenza, mentre quando avremo finito di riempire un’orbita quadrata 3 x 3 (E, F, H, I) saremo in una casella dello stesso colore di quella di partenza.
Possiamo allora associare alle orbite quadrate 3 x 3 il colore (bianco o nero) delle celle che si trovano ai
loro vertici e al loro centro, perché tali orbite possono essere riempite soltanto iniziando da una casella di quel colore e, quindi, terminando in una casella di quel colore: in sostanza, considereremo “bianche” le orbite E, I e “nere” le orbite F, H. Teniamo poi a mente che tutte le altre orbite possono essere riempite a partire da qualsiasi casella ma terminando sempre in una casella di colore diverso da quella di partenza. Questo fa sì che, aggiungendo i colori delle orbite quadrate al grafo di sopra, possiamo escludere alcune scelte per la successione delle orbite.
Consideriamo per esempio la successione, piuttosto naturale,
D – H – C – E – A – I – B – F – G:
possiamo dire fin da subito che non ci saranno soluzioni che seguono questa successione di orbite. Infatti, supponiamo di iniziare a riempire l’orbita D da una casella bianca: termineremo pertanto su una casella nera e salteremo su una casella nera di H. Sarà allora possibile riempire H terminando su una casella nera, dalla quale salteremo su una casella nera di C; riempita C, termineremo su una casella bianca dalla quale salteremo a una casella bianca di E. Anche E può essere riempita iniziando da una sua casella bianca e terminando su un’altra casella bianca: salteremo allora a una casella bianca di A, che riempiremo terminando su una casella nera. A questo punto non potremo andare avanti, perché potremmo saltare soltanto su una casella nera di I dalla quale I non può essere riempita. Una successione “corretta” da questo punto di vista è allora, per esempio,
A – F – B – I – D – H – C – E – G.
Con un po’ di fatica, è possibile anche convincersi del fatto che ogni scelta della successione delle orbite tale da rispettare questa condizione di “compatibilità” può generare una soluzione del nostro problema, ma lasciamo al lettore il compito di farlo.
Andiamo finalmente a cominciare. Per passare dall’orbita A (le cui caselle sono segnate in verde nella figura qui sotto) all’orbita F è necessario effettuare un movimento diagonale verso l’alto e verso destra: dovremo quindi cercare un riempimento che ci permetta di finire in una casella abbastanza in basso e abbastanza a sinistra da rendere possibile questo salto. Una possibile scelta è rappresentata qui sotto.
–>
Si tratta quindi di riempire l’orbita F in un modo che poi ci permetta di sull’orbita C… ma arrivato a questo punto mi sembra perfino di aver detto troppo e di rischiare di rovinare tutto il divertimento: lascerei al lettore il compito di proseguire questo ragionamento fino a riempire tutta la scacchiera.
Per chi invece non avesse tempo o voglia di farlo, qui si trova la mia soluzione completa
Penso che invece valga la pena di osservare che le considerazioni che ci hanno permesso di risolvere questo gioco del 100 si possono applicare pari pari a qualsiasi scacchiera rettangolare m x n (dove m e n, come è facile convincersi, devono essere numeri più grandi di 5). Sarà sempre possibile dividere la scacchiera in nove orbite collegate tra loro come nel grafo visto sopra; basterà poi considerare il “colore” caratteristico delle orbite “dispari” e scegliere un percorso che rispetti la giusta successione di orbite. Di qui sarà poi quasi immediato trovare la giusta strategia di riempimento.