Gioco del quadrato

di Massimo Fantin

HOME

Premessa 

Questo gioco mi è stato proposto da due miei studenti che ne cercavano a mano la risoluzione.  L'analisi del metodo è interessante dal punto di vista matematico 
Il modello di  rappresentazione del problema è  un albero del quale si devono  analizzare i rami fino a quando non si trova  quello che costituisce una soluzione , proseguendo nell'ìanalisi dei rami dell'albero si possono trovare tutte le soluzioni.  

Scopo del gioco 

Il gioco consiste nel riempire un quadrato  di   n x n casella con i numeri da 1 a n² in modo che  il successivo di un numero sia spostato o di  tre caselle in alto, in baso, a destra, a sinistra oppure in diagonale in una delle quattro direzioni saltando una casella.

Commento e risoluzione

E' facile dimostrare che se n<5 il gioco non ha soluzione. Se n è  almeno 5 per trovare le soluzioni si può procedere  in modo come segue:

Se un numero x si trova in una determinata casella, il numero successivo occuperà una delle 8 caselle di cui sopra ( ammesso che siano disponibili).  Nominiamo  queste otto caselle secondo un ordine ben definito per esempio cominciamo dalla casella in basso e la indichiamo convenzionalmente con "a".  Ruotiamo in senso antiorario in modo che la posizione in diagonale basso destra sia  la  "b", quella a destra è la "c" e così via fino alla "h"  che è in basso a sinistra.  E' importante che una volta scelta una condizione la si rispetti sempre.

Si assegna il numero 1 a una casella per esempio la prima in alto.

si assegna il numero 2 alla prima casella libera secondo la convenzione presa sopra, per esempio la casella 2 sarà  tre caselle sotto l'uno perché  libera.  Si procede così per il numero 3, 4 fino a quando   si arriva ad un numero per il quale tutte le  caselle permesse per il numero successivo sono occupate e  non si può procedere oltre. A questo punto si cancella l'ultimo numero scritto si torna al numero precedente  si prende come successivo di quest'ultimo la casella disponibile che, secondo l'ordine scelto viene immediatamente dopo quella già considerata. Se nessun di queste caselle è disponibile si ritorna ancora indietro fino a quando non si trova una casella che abbia disponibile un'altra uscita.  Si ricomincia analizzando la nuova via. Si procede in questo modo fino a che non si sono riempite tutte le caselle si è raggiunta  una delle soluzioni cercate. Per cercare la soluzione successiva si torna indietro di una casella, si cancella la via già percorsa e si procedere nuovamente. In questo modo è possibile trovare tutte le soluzioni.

Il metodo indicato  è un metodo costruttivo nel senso che permette di costruire tutte le soluzioni,  il problema in questo metodo è che i tempi di calcolo crescono   rispetto alle dimensioni del gioco in modo esponenziale  e  i tempi di calcolo diventano presto enormi. Se per risolvere il problema con una tabella 7x7 è di pochi secondi , per risolvere una di 9x9 sono richieste ore mentre quella 10x 10 tempi lunghissimi.  
Se non interessano tutte le soluzioni ma se ne vuole trovare solo alcune si può procedere come segue, suddividendo il problema in sottoproblemi di dimensioni inferiori. Per esempio per trovare una soluzione 10x10 o anche più grandi si può  usare il metodo "Divide et imperat"  Modo generico di indicare un metodo informatico che si applica ad una grande serie di problemi  per i quali, come in questo , l'aumento di  dimensioni fa aumentare enormemente il tempo di calcolo: si divide il problema in più sottoproblemi di dimensioni inferiori e ricomponendo le soluzioni di questi sottoproblemi è possibile giungere alla soluzione del problema principale. 
Nel nostro caso per risolvere un quadrato 10x 10 si può pensare di suddividere il quadrato in quattro quadrati 5 x 5. risolvere il primo in modo che  l'ultimo numero: il 25  sia vicino al bordo.Iil 26 sarà in una casella del  quadrato vicino. Si ripete il procedimento fino a che non si è riempito tutto il quadrato. 

Questa è una tavola 10 x 10 risolta in questo modo, si vede infatti che i numeri da 1 a 25 sono tutti nel quadrato 5x5 in alto a sinistra, i numeri da 26 a 50 nel quadrato in basso a sinistra, i numeri da 51 a 75 sono in basso a sinistra e infine i numeri da 76 a 100 sono in alto a destra.  naturalmente questo metodo non permette di trovare tutte le soluzioni.

Lo studio dei problemi naturalmente ne apre altri, per esempio pensando a una figura che non sia necessariamente un quadrato,  come devono essere  forma e  dimensioni e  affinché ammetta soluzioni?   

Uso del programma

Il programma  esegue le operazioni illustrate sopra molto più velocemente di quanto si possa fare a mano,  per avere un'idea della velocità , con il mio computer, che è già vecchiotto, il     numero di passi che il programma esegue  in un secondo è  circa 50 milioni. 

I passi si possono eseguire uno per volta  facendo click su passo. o tutti insieme facendo click su via. 
Per evitare che il computer non si fermi più è previsto un tempo massimo espresso in passi che può essere modificato fino a un max di 10 miliardi ( il tempo  è circa di 5 ore).
Se il programma non è riuscito a trovare una soluzione nel numero dei passi previsto si ferma e visualizza la configurazione  a cui era arrivato. 
Per  continuare si può fare nuovamente click su via.    

I tasti x+ e x-, y+ y- cambiano le dimensioni del gioco mentre il tasto sposta cambia la cella di partenza. 

L'applet che segue è un aggiornamento del programma originale ed  è possibile risolvere il problema su rettangoli. Si può osservare che mentre nel caso del rettangolo  4x4 non ci sono soluzioni , il problema  4x5 ha  6 soluzioni che si possono trovare facilmente.