C'è qualcosa di magico nel tornare con la mente a quei semplici passatempi della nostra giovinezza, specialmente per chi, come me, appartiene alla Generazione X. Erano i tempi in cui la noia si affrontava con giochini su carta e penna, o con voli pindarici di fantasia. Uno di questi giochi, che ancora ricordo con affetto dai tempi delle superiori, si svolgeva su un foglio a quadretti: si tracciava un quadrato 10x10 e, partendo da un punto scelto, si cercava di coprire tutte le 100 caselle seguendo regole ben precise.
Le regole erano semplici ma sfidanti:
- In orizzontale o verticale, si saltano due caselle.
- In diagonale, si salta una casella.
Questo giochino mi ha accompagnato fino all'università, diventando un piccolo enigma personale da risolvere. Arrivato al terzo anno di Informatica, durante l'esame di Sistemi 2 – materia che includeva algoritmi fondamentali e complessità computazionale – decisi di affrontarlo con un approccio più formale e tecnico. Volevo trovare una soluzione attraverso un algoritmo.
Provai vari approcci: dalla ricorsione al backtracking, spingendomi fino a scrivere parti di codice in linguaggio Assembly per ottimizzare i tempi di esecuzione. Ma niente da fare: il problema della griglia 10x10 sembrava inaffrontabile (a meno di non usare "trucchetti" come dividere la griglia in sezioni 5x5 per poi unirle). Ma in questo modo la soluzione esisteva, sì, ma non era generica. Il progetto fu comunque accettato e l'esame superato, ma quel piccolo tarlo non mi abbandonò.
Decisi di approfondire la questione insieme a vari professori, riconducendo il problema a un grafo: le posizioni diventavano nodi e i possibili movimenti archi. Iniziava a sembrare un problema noto, simile a quello del commesso viaggiatore, suggerendo la possibilità che fosse NP-completo. Tuttavia, dimostrarlo in modo formale era complicato, data la struttura specifica del grafo. Così, dopo ulteriori tentativi e riflessioni, mi arresi, pur continuando a pensarci periodicamente e a esplorare nuovi approcci.
Il Ruolo dell'Intelligenza Artificiale: Una Nuova Speranza
Fino a ieri sera. Mi sono ricordato ancora una volta del problema e, ispirato da un suggerimento del buon Marco Montemagno – "IA first" – ho deciso di coinvolgere l'intelligenza artificiale nella soluzione. Ho aperto ChatGPT, spiegato le regole del gioco e chiesto di risolverlo.
L'IA ha iniziato a girare, testando diversi approcci. Dopo un po', ha indicato che il calcolo richiedeva troppo tempo e avrebbe provato metodi alternativi. Anche io avevo già analizzato il problema in passato, così ho iniziato a suggerirgli alcune vie da seguire. Ci siamo spostati sul modello dei grafi, con ChatGPT che ha riconosciuto la somiglianza con il problema del commesso viaggiatore e la ricerca di un cammino hamiltoniano. Abbiamo tentato con il backtracking, ma senza successo. Poi, suggerisco di provare con la Ricerca in Profondità (DFS, Depth-First Search). A questo punto, ChatGPT ha suggerito di combinare questo approccio con una strategia euristica, utilizzando l'algoritmo di Warnsdorff. Questo algoritmo tenta di muoversi sempre verso la casella con il minor numero di mosse successive possibili, riducendo così la probabilità di trovarsi in un vicolo cieco. Abbiamo provato. E, incredibilmente, ha funzionato. La soluzione era lì, davanti a noi. Ho chiesto all'IA di esportare la griglia su Excel per verificare che tutte le mosse fossero corrette. Con mia grande sorpresa, tutto era giusto.
Abbiamo poi aumentato la complessità, provando su griglie più grandi: 20x20, 30x30, fino a 40x40. L'IA ha continuato a trovare la soluzione corretta. Mi sono quasi commosso.
Considerazioni Finali
Questa esperienza mi ha mostrato quanto potente possa essere l'intelligenza artificiale, ma soprattutto come la collaborazione tra uomo e macchina possa portare a risultati sorprendenti. Quello che sembrava un rompicapo senza soluzione è stato finalmente risolto, grazie a un mix di intuizione umana e potenza computazionale dell'IA.
Per chi volesse provare, un piccolo avvertimento: quando spiegate le regole all'IA, potrebbe non comprenderle perfettamente al primo tentativo. Un buon metodo è farle esportare una griglia con le prime 20 mosse e correggerla se necessario.
Codice Python per la Soluzione
Ecco il codice Python che risolve il gioco (si tratta dell'algoritmo suggerito da ChatGPT; ho verificato che funziona, ma non l'ho revisionato completamente, quindi potrebbero esserci bug):
import random
def create_graph(size):
graph = {}
# Definisci i movimenti consentiti
moves = [
(3, 0), (-3, 0), # Movimenti orizzontali (saltando 2 caselle)
(0, 3), (0, -3), # Movimenti verticali (saltando 2 caselle)
(2, 2), (2, -2), (-2, 2), (-2, -2) # Movimenti diagonali (saltando 1 casella)
]
# Crea i nodi e gli archi del grafo
for r in range(size):
for c in range(size):
node = (r, c)
graph[node] = []
for move in moves:
neighbor = (r + move[0], c + move[1])
if 0 <= neighbor[0] < size and 0 <= neighbor[1] < size:
graph[node].append(neighbor)
return graph
def find_hamiltonian_path(graph, start_node, grid_size):
path = []
visited = set()
def dfs(node):
visited.add(node)
path.append(node)
if len(visited) == grid_size * grid_size:
return True
neighbors = sorted(graph[node], key=lambda n: len([nbr for nbr in graph[n] if nbr not in visited]))
for neighbor in neighbors:
if neighbor not in visited:
if dfs(neighbor):
return True
# Backtrack
visited.remove(node)
path.pop()
return False
dfs(start_node)
return path
def print_path(path, size):
grid = [[0] * size for _ in range(size)]
for i, pos in enumerate(path):
grid[pos[0]][pos[1]] = i + 1
for row in grid:
print(" ".join(f"{cell:3}" for cell in row))
def main():
# Definisci la dimensione della griglia
grid_size = 10
graph = create_graph(grid_size)
# Scegli una posizione iniziale casuale
start_node = (random.randint(0, grid_size - 1), random.randint(0, grid_size - 1))
print(f"Starting node: {start_node}")
# Trova il percorso Hamiltoniano
path = find_hamiltonian_path(graph, start_node, grid_size)
# Visualizza il percorso trovato
print_path(path, grid_size)
if __name__ == "__main__":
main()
Conclusioni
L'IA è davvero una forza. Sono entusiasta di aver potuto sperimentare in prima persona come l'unione delle forze tra uomo e IA sia vincente. Questa esperienza non solo mi ha permesso di risolvere un piccolo gioco matematico che mi tormentava da anni, ma mi ha anche fatto riflettere su quanto sia promettente la sinergia tra intelligenza umana e artificiale nel campo della ricerca.
In fondo, la curiosità e la perseveranza, unite alla tecnologia, possono davvero spostare i confini della conoscenza.
