L'algoritmo di Warnsdorff

Il giochino di cui ho parlato qualche giorno fa può essere risolto con un programma per computer. Tecnicamente si tratta di una ricerca di un cammino hamiltoniano su un grafo, che sarebbe poi un percorso che tocca tutti i vertici di un grafo una volta sola.

La scacchiera 10×10 deve essere infatti vista come un grafo: ogni casella è collegata a tutte quelle che sono raggiungibili, a partire da essa, con una sola mossa.

Per esempio, se noi partiamo dalla casella nell'angolo in alto a sinistra, osserviamo che essa è collegata soltanto a tre altre caselle, come nella seguente figura.

A sua volta, ognuna delle tre caselle raggiungibili con la prima mossa è collegata ad altre caselle, e così via. Dunque, per completare il giochino il nostro programma dovrebbe esplorare l'albero delle mosse allo scopo di trovare un percorso che tocchi tutte le caselle una volta sola.

Come si fa? Bè, in generale il problema della ricerca di un cammino hamiltoniano è NP-completo. In linguaggio non da informatico significa che è un problema difficile. Volendo essere più precisi, si può dire che se si riesce a trovare una soluzione al problema, allora è facile verificare che essa sia giusta; ma il problema è trovarla. Infatti la caratteristica principale dei problemi NP-completi è che non si conosce nessun tipo di algoritmo veloce per poterli risolvere. Ciò significa che il tempo impiegato dal computer per risolvere il problema diventa rapidamente dell'ordine degli anni (o delle migliaia di anni, milioni di anni, miliardi di anni, esagerate pure) appena si tenta di aumentare un po' la dimensione del problema stesso.

Volendo essere ancora più precisi: se si riesce a trovare una soluzione veloce a uno dei tanti problemi NP-completi, allora è stato dimostrato che si può trovare una soluzione altrettanto veloce per tutti i problemi della categoria NP-completi. In pratica, sono tutti equivalenti. Per dare un'idea dell'importanza di tutto ciò, sappiate che se riuscite a trovare l'algoritmo veloce avete diritto a un premio di un milione di dollari. Anzi, forse avete diritto al premio anche se dimostrate soltanto l'esistenza di un algoritmo veloce, senza trovarlo (per capire bene se le cose stanno così bisognerebbe leggersi tutto il bando ufficiale del premio).

Bene, torniamo al nostro programma. La scacchiera 10×10 è ancora abbastanza piccola, per cui l'albero delle possibili mosse può ancora essere esplorato andando per tentativi: si prova a sistemare il primo numero, poi si prova col secondo, e così via. Se si arriva all'ultimo, siamo fortunati e il giochino è risolto, altrimenti si torna indietro, si cambia una scelta fatta, e si percorre una nuova strada. Prima o poi si trova la soluzione (o si percorrono tutte le strade e si può affermare con certezza che la soluzione non esiste). Questa tecnica è detta backtracking, ovvero prova e riprova.

Questo particolare tipo di problema di ricerca di cammino hamiltoniano, però, può anche essere risolto senza fare uso della forza bruta, ma utilizzando un algoritmo veloce, detto algoritmo di Warnsdorff (che è poi quello che ho usato io quando ho risolto a mano il gioco).

Funziona in questo modo: supponiamo di avere riempito una certa casella; dobbiamo decidere quale sarà la successiva da riempire. Per ognuna delle caselle candidate, andiamo a vedere a quante altre caselle esse sono collegate. Per esempio, se cominciamo con la prima casella in alto a sinistra, abbiamo tre possibilità. Osserviamo che da due caselle possiamo proseguire in 4 modi diversi, e dalla terza casella possiamo proseguire in 5 modi.

Bene, per andare avanti dobbiamo sempre scegliere la casella con il minor numero di connessioni, cioè quella più difficile da raggiungere (se ci sono più caselle con lo stesso minimo numero di connessioni, scegliamone una a caso). Se seguiamo questo accorgimento, siamo sicuri di arrivare in fondo. Ecco, per esempio, una soluzione generata al computer.

+---+---+---+---+---+---+---+---+---+---+
|  1| 62| 40| 16| 61| 39| 75| 49| 38| 74|
+---+---+---+---+---+---+---+---+---+---+
| 54| 18|  3| 53| 58|  4| 52| 72|  5| 51|
+---+---+---+---+---+---+---+---+---+---+
| 41| 15| 60| 67| 94| 79| 66| 95| 78| 48|
+---+---+---+---+---+---+---+---+---+---+
|  2| 63| 57| 17| 64| 69| 76| 50| 37| 73|
+---+---+---+---+---+---+---+---+---+---+
| 55| 19| 99| 82| 59| 98| 91| 71|  6| 90|
+---+---+---+---+---+---+---+---+---+---+
| 42| 14| 29| 68| 93| 80| 65| 96| 77| 47|
+---+---+---+---+---+---+---+---+---+---+
| 23| 83| 56| 24| 86| 70| 25| 87| 36| 10|
+---+---+---+---+---+---+---+---+---+---+
| 30| 20|100| 81| 32| 97| 92| 33|  7| 89|
+---+---+---+---+---+---+---+---+---+---+
| 43| 13| 28| 44| 12| 27| 45| 11| 26| 46|
+---+---+---+---+---+---+---+---+---+---+
| 22| 84| 31| 21| 85| 34|  8| 88| 35|  9|
+---+---+---+---+---+---+---+---+---+---+

Un gioco simile a questo è il giro del cavallo: si tratta di toccare tutte le caselle di una scacchiera utilizzando le mosse del cavallo degli scacchi. In questo caso l'algoritmo di Warnsdorff non sempre assicura il successo; se volete divertirvi, in questa pagina c'è una applet java che vi permette di provare.