Il gioco del Quindici

		*MokaByte Numero 18 - Aprile* 1998**

	di Alessandro Bellucci e Massimo Bellucci	Il Gioco del Quindici

Questo articolo presenta una panoramica sui vari metodi per automatizzare la soluzione del problema del Gioco del Quindici con riferimento ad una implementazione realizzata in linguaggio Java.

Il gioco del quindici fu inventato da Sam Loyd piu' di un secolo fa. Lo scopo del gioco e' quello di ordinare le caselle dal numero 1 al numero 15, partendo da una configurazione casuale (non proprio casuale, come vedremo in seguito), lasciando in basso a destra il tassello vuoto (nelle formule rappresentato per semplicita' con il numero 16). Le mosse consentite sono solo gli spostamenti sulla posizione vuota di tasselli ad essa adiacenti.

Se consideriamo l'insieme A di tutte le permutazioni dei 16 tasselli, compreso quello bianco, si puo' dimostrare che, se definiamo due sottoinsiemi B e C di A come segue:

- B contiene tutte le configurazioni che possono portare alla soluzione in un numero finito di mosse.

- C contiene le configurazioni che non portano a nessuna soluzione.

e definiamo:

- mossa: uno spostamento di un tassello qualsiasi sul tassello bianco, se ad esso adiacente (Es: nella figura precedente lo spostamento del tassello 12 o 15 sul tassello bianco).

- scambio: uno spostamento tra due tasselli qualunque, anche se non adiacenti (Es: nella figura precedente lo scambio del tassello 1 con il tassello 7).

si ha che:

1. B unione C = A (ovviamente ogni permutazione porta o non porta alla soluzione).

2. B intersezione C = 0 (B e C non hanno elementi in comune).
3. ogni configurazione appartenente all'insieme B (C) e' raggiungibile con un numero finito di mosse da ogni altra configurazione appartenente a B (C).
4. ogni scambio di tasselli che non coinvolga il tassello bianco fa passare da una configurazione appartenente all'insieme B ad una appartenente all'insieme C (o viceversa).
5. un numero pari di scambi di tasselli porta ad una configurazione appartenente all'insieme di partenza (B o C).
6. un numero dispari di scambi fa passare da C a B (o viceversa).

Si dice che Sam Loyd, dopo aver inventato e divulgato il gioco, mise in palio un premio di $1000 che avrebbe consegnato a chi avesse risolto il puzzle a partire dalla configurazione ordinata ma con il 14 ed il 15 scambiati: lui sapeva che tale configurazione appartiene all'insieme di quelle che non porteranno mai alla soluzione (l'insieme C) e per questo si permise di mettere in palio una cifra talmente alta (soprattutto per quei tempi!).

Il nostro scopo e' quello di realizzare un programma che risolva in modo automatico il gioco partendo da una configurazione casuale (che puo' essere generata usando le funzioni random() dei comuni linguaggi di programmazione), purche' appartenente all'insieme B. Ma come e' possibile sapere se una configurazione generata in modo casuale appartiene a B od a C?
La risposta al problema e' semplice: e' sufficiente contare il numero di scambi (non di mosse!) necessari per riportarsi nella configurazione iniziale e controllare se questo sia pari o dispari.
Il programma che e' stato realizzato (implementato in linguaggio Java), risolve lo stesso problema in modo ancora piu' semplice: partendo da una configurazione appartenente all'insieme B genera un numero pari di scambi casuali, ottenendo cosi' una configurazione disordinata, ma di certo ancora appartenente all'insieme B.
L'utente potra' mescolare i tasselli in ogni momento, semplicemente premendo il pulsante 'Mescola'. Il codice relativo e' riportato di seguito:

/*
* Disordina le caselle effetuando nScambi scambi.
* Si ritorna ad una posizione valida se (e soltanto se) il
* numero di scambi e' pari.
*/
public void disordina(int nScambi)
{
Random random = new Random();
int a1,b1,a2,b2;
for(int i = 0;i < nScambi; i++)
{
    /*
    * Scambia due caselle a caso purche' non coincidano e
    * nessuna delle due sia quella vuota (n*n).
    */
    do
    {
        a1 = Math.abs(random.nextInt()%n);
        b1 = Math.abs(random.nextInt()%n);
        a2 = Math.abs(random.nextInt()%n);
        b2 = Math.abs(random.nextInt()%n);
    }
    while(((a1==a2) && (b1==b2)) || (q[a1][b1]==n*n) || (q[a2][b2]==n*n));
    scambia(a1,b1,a2,b2);
}
}

Chiunque e' in grado di risolvere il gioco dopo qualche minuto di apprendimento iniziale. I problemi nascono quando si tenta di scrivere un algoritmo che trovi automaticamente una soluzione partendo da una configurazione iniziale appartenente all'insieme B. Per quanto ci si sforzi di capire le regole che inconsciamente applichiamo quando lo risolviamo, non riusciremo a descriverle in forma semplice. Sebbene esistano delle soluzioni basate su regole del gioco del Quindici, esse non rivestono molto interesse in quanto richiedono un numero di mosse molto elevato e soprattuno non rispecchiano la modalita' di ragionamento della mente umana.
Un approcio al problema semplice, per quanto ingegnoso, e' quello di definire una funzione che associ ad ogni permutazione la sua "distanza" dalla configurazione ordinata e di implementare un algoritmo che calcoli, ad ogni passo, la distanza di tutte le configurazioni ottenibili con una mossa (al massimo 4) e che scelga quella piu' "vicina" alla soluzione. Se nessuna delle mosse possibili diminuisce la distanza rispetto alla configurazione attuale non viene effettuato nessuno spostamento. Se la distanza implementata e' quella reale a questa condizione dovrebbe corrispondere la configurazione ordinata.

Se indichiamo con q la matrice n x n che rappresenta il gioco (tutti i risultati precedenti sono generalizzabili al caso n x n), due semplici distanze potrebbero essere le seguenti:

La prima distanza misura la differenza tra il tassello che si trova in una data posizione e quello che dovra' esserci nella configurazione ordinata.
La seconda distanza tiene conto del fatto che sono consentite anche mosse in verticale e quindi, per ogni tassello, misura la sua distanza dalla posizione finale in termini di numero minimo di mosse per raggiungerla.
La seconda distanza e' associata al pulsante 'Risolvi 1', la prima non e' implementata nella versione finale. Il codice che le implementa e' riportato di seguito:

/*
* Calcola la distanza tra la configurazione attuale e quella da raggiungere: e' una variante del metodo 1. che non considera il
* tassello vuoto.
*/
private int dist()
{
int d=0;
for(int i=0;i<n;i++)
{
     for(int j=0;j<n;j++)
     {
        if(q[i][j] != n*n)
          d += Math.abs(q[i][j] - (i*n+j+1));
     }
}
return d;
}
/*
* Calcola la distanza tra la configurazione attuale e quella da raggiungere: e' una variante del metodo 2. che non considera il
* tassello vuoto.
*/
private int dist2()
{
int d=0;
for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
          if(c[i][j]!=n*n)
         {
            d += Math.abs(q[i][j]/n - i);
            d += Math.abs(q[i][j]%n - 1 - j);
          }
     }
}
return d;
}

Purtroppo nessuna delle due distanze porta a dei risultati soddisfacenti. Infatti, se non si e' particolarmente fortunati, dopo pochi passi si raggiunge una posizione in cui nessuna delle mosse possibili abbasserebbe ulteriormente la distanza, ma nonostante questo non si e' nella posizione ordinata. Di seguito e' illustrato un semplice esempio di come questo possa avvenire con la prima delle distanze introdotte. A partire dalla configurazione

Distanza 1 = |15-11| + |11-12| + |12-15| = 8 Distanza 2 = 1 + 2 + 1 = 4

si hanno due mosse possibili:

Distanza 1 = |12-16| + |15-11| + |11-12| = 9 Distanza 2 = 1 + 1 + 1 = 3

Distanza 1 = |12-15| + |11-16| + |15-11| = 12 Distanza 2 = 1 + 2 + 1 = 4

e come si vede entrambe incrementano la distanza 1. Questo esempio mostra anche che la distanza 2 funziona meglio in molti casi, ma e' facile trovare situazioni in cui anch'essa non porta alla soluzione corretta.

Probabilmente la reale funzione distanza che da qualunque configurazione di partenza decresce fino alla disposizione ordinata e' incredibilmente complicata. Nella realta' cio' che noi facciamo quando risolviamo manualmente il gioco e' "distruggere per ricreare", cioe' permettiamo alla distanza di crescere per poi diminuirla piu' di quanto non sia aumentata.

Per risolvere il problema e' necessario indagare piu' approfonditamente nell'albero delle soluzioni, per individuare strade che in ultima analisi possono risultare vantaggiose, anche se in prima approssimazione non lo sembrano affatto.
Per implementare un algoritmo piu' efficace e' stato necessario scrivere un pacchetto per la gestione degli alberi; provando ad andare in profondita' di tre mosse (o piu' se non viene trovata nessuna strada che abbassi la distanza nelle prime due) si sono ottenuti discreti risultati (il pulsante 'risolvi 2' consente di eseguire automaticamente una mossa utilizzando questo metodo di risoluzione), ma per risolvere il gioco nella maggioranza delle situazioni e' necessario adottare tecniche piu' sofisticate perche' scendere ancora nell'albero costa troppo in termini di risorse computazionali.
Per raggiungere risultati ottimali e' necessario esplorare solo determinate zone dell'albero scartando a priori quei rami che presentano una distanza "eccessiva" dalla soluzione. Ancora non e' stata implementata una soluzione di questo tipo, ma dovrebbe permettere di risolvere il problema a partire da qualunque configurazione iniziale.

Quindici.java

Alessandro Bellucci e' perito informatico ed e' studente in Ingegneria Informatica. Si e' occupato di problematiche relative alla sintesi vocale da calcolatore ed ha collaborato alla realizzazione di applicazioni client-server sviluppate in Java. Puo' essere contattato all'indirizzo bellu@tin.it.

Massimo Bellucci ha conseguito il Diploma Universitario in Ingegneria Elettronica con una tesi sull' "Utilizzo dell'ambiente Java per l'accesso ad un sistema di telecontrollo tramite Internet". Attualmente si occupa di un progetto Europeo che ha come scopo la creazione di un sistema di acquisizione di dati ambientali distribuiti in Internet. Puo' essere contattato agli indirizzi bellu@tin.it, bellucci@pinet.ing.unifi.it.



	MokaByte rivista web su Java MokaByte ricerca nuovi collaboratori Chi volesse mettersi in contatto con noi può farlo scrivendo a mokainfo@mokabyte.it