Quasi due anni fa raccontavo in questo articolo come l'intelligenza artificiale mi avesse aiutato a chiudere un conto aperto da decenni: il gioco delle 100 caselle, quel puzzle su griglia 10×10 che ai tempi dell'università avevo attaccato con ricorsione, backtracking e perfino Assembly, senza mai venirne a capo. Nell'agosto 2024, con l'aiuto di ChatGPT, la soluzione era finalmente arrivata: ricerca in profondità guidata dall'euristica di Warnsdorff, e la griglia si riempiva in una frazione di secondo. Ero riuscito perfino a spingermi fino a griglie 40×40.
Quell'articolo si chiudeva parlando di collaborazione tra uomo e macchina. Oggi torno sull'argomento perché nel frattempo la macchina è cambiata parecchio, ed è cambiato soprattutto il modo di collaborarci. Ho ripreso in mano quel vecchio codice e l'ho dato in pasto a Claude Fable 5, prima con una semplice richiesta di ottimizzazione, poi con una tecnica che trovo affascinante: il loop engineering, cioè affidare al modello un obiettivo e un numero massimo di tentativi, e lasciarlo lavorare da solo in un ciclo di modifica-misura-verifica. I risultati mi hanno sorpreso quanto la prima soluzione di due anni fa. Ma andiamo con ordine.
Il punto di partenza: cosa non sapevo del codice del 2024
Prima di ottimizzare bisogna misurare, e la prima misura è stata una doccia fredda. Il codice dell'articolo originale funziona benissimo sulla griglia 10×10 e, come raccontavo, anche su 20×20, 30×30 e 40×40. Ma rieseguendolo oggi in modo sistematico su una serie di taglie, con un timeout di 2 minuti per esecuzione, è emersa la sua vera natura:
| Griglia | Codice 2024 (ChatGPT) |
|---|---|
| 10×10 | 0,001 s |
| 40×40 | 0,012 s |
| 50×50 | oltre 2 minuti, interrotto |
| 60×60 | 0,026 s |
| 70×70 | 0,042 s |
| 80×80 | oltre 2 minuti, interrotto |
| 90×90 | 0,067 s |
| 100×100 | oltre 2 minuti, interrotto |
| 120×120 | 0,123 s |
| 150×150 | oltre 2 minuti, interrotto |
Una roulette russa. Quando l'euristica di Warnsdorff "indovina" al primo colpo, il tempo è irrisorio; quando sbaglia strada, il backtracking ricorsivo esplode combinatorialmente e il programma di fatto non termina più. Su dodici taglie provate tra 45 e 150, quattro non sono arrivate in fondo. Nel 2024 non me n'ero accorto semplicemente perché mi ero fermato a 40×40, dove la fortuna aveva sempre girato dal verso giusto. Il problema di fondo — la ricerca di un cammino hamiltoniano è NP-completa, come sospettavo già da studente — era stato aggirato dall'euristica, non domato.
Primo salto: il codice riscritto da Claude Fable 5
Ho quindi passato il codice a Claude Fable 5 chiedendo di ottimizzarlo. Il risultato (il file che oggi chiamo old.py, perché di lì a poco sarebbe diventato a sua volta "il vecchio codice") è una riscrittura completa che cambia strategia proprio nel punto debole: niente più backtracking ricorsivo.
"""
Gioco delle 100 caselle - solver v4 (finale)
- Warnsdorff con doppio tie-break: grado minimo, poi distanza max dal centro
- Rotazioni di Pósa "intelligenti": preferisce nuovi estremi con vicini liberi
e suffissi corti da invertire
"""
import random, sys, time
MOVES = [(3,0),(-3,0),(0,3),(0,-3),(2,2),(2,-2),(-2,2),(-2,-2)]
def build_neighbors(size):
n = size*size
neigh = [None]*n
for r in range(size):
for c in range(size):
lst = []
for dr, dc in MOVES:
nr, nc = r+dr, c+dc
if 0 <= nr < size and 0 <= nc < size:
lst.append(nr*size+nc)
neigh[r*size+c] = lst
return neigh
def solve(size, start=0, seed=None, max_rotations_factor=200):
rng = random.Random(seed)
n = size*size
neigh = build_neighbors(size)
half = (size-1)/2.0
# distanza dal centro (precomputata) per il tie-break secondario
cdist = [0.0]*n
for r in range(size):
for c in range(size):
cdist[r*size+c] = (r-half)*(r-half) + (c-half)*(c-half)
visited = bytearray(n)
deg = [len(neigh[i]) for i in range(n)]
path = [start]; pos = [-1]*n
pos[start] = 0; visited[start] = 1
for nb in neigh[start]: deg[nb] -= 1
rotations = 0
max_rotations = max_rotations_factor*n
while len(path) < n:
cur = path[-1]
# passo greedy: grado min, poi distanza max dal centro, poi random
best, bd, bdist = [], 99, -1.0
for nb in neigh[cur]:
if not visited[nb]:
d = deg[nb]
if d < bd:
bd, bdist, best = d, cdist[nb], [nb]
elif d == bd:
dd = cdist[nb]
if dd > bdist:
bdist, best = dd, [nb]
elif dd == bdist:
best.append(nb)
if best:
nxt = best[rng.randrange(len(best))] if len(best) > 1 else best[0]
visited[nxt] = 1; pos[nxt] = len(path); path.append(nxt)
for nb in neigh[nxt]: deg[nb] -= 1
continue
# vicolo cieco -> rotazione di Pósa
rotations += 1
if rotations > max_rotations:
return None, rotations
plen = len(path)
good, fallback = [], []
for v in neigh[cur]:
i = pos[v]
if i >= plen-2: # rotazione nulla
continue
new_end = path[i+1]
# il nuovo estremo ha vicini non visitati?
has_free = any(not visited[x] for x in neigh[new_end])
(good if has_free else fallback).append(i)
cand = good if good else fallback
if not cand:
return None, rotations
# scelta casuale (evita cicli) con leggera preferenza per suffissi corti
i = max(cand) if rng.random() < 0.5 else cand[rng.randrange(len(cand))]
lo, hi = i+1, plen-1
while lo < hi:
path[lo], path[hi] = path[hi], path[lo]
pos[path[lo]] = lo; pos[path[hi]] = hi
lo += 1; hi -= 1
if lo == hi: pos[path[lo]] = lo
return path, rotations
def verify(path, size):
n = size*size
if path is None or len(path) != n or len(set(path)) != n:
return False
legal = {(3,0),(-3,0),(0,3),(0,-3),(2,2),(2,-2),(-2,2),(-2,-2)}
for a, b in zip(path, path[1:]):
if (b//size - a//size, b%size - a%size) not in legal:
return False
return True
def print_grid(path, size):
"""Stampa la griglia con il numero d'ordine di ogni mossa."""
grid = [[0]*size for _ in range(size)]
for i, node in enumerate(path):
grid[node // size][node % size] = i + 1
w = len(str(size*size))
for row in grid:
print(" ".join(f"{cell:{w}}" for cell in row))
def export_pdf(path, size, filename, seed=None):
"""Esporta la griglia risolta in PDF (A4).
- size <= 30: celle numerate come nel gioco su carta
- size > 30: percorso disegnato con gradiente di colore (verde -> rosso)
"""
from reportlab.lib.pagesizes import A4
from reportlab.lib.units import mm
from reportlab.pdfgen import canvas as pdfcanvas
from datetime import date
page_w, page_h = A4
margin = 18 * mm
title_h = 16 * mm
avail = min(page_w - 2 * margin, page_h - 2 * margin - title_h)
cell = avail / size
grid_w = cell * size
ox = (page_w - grid_w) / 2
oy = (page_h - title_h - grid_w) / 2
c = pdfcanvas.Canvas(filename, pagesize=A4)
# intestazione
c.setFont("Helvetica-Bold", 16)
c.drawCentredString(page_w / 2, page_h - margin, f"Gioco delle {size*size} caselle - griglia {size}x{size}")
c.setFont("Helvetica", 9)
sub = f"Cammino hamiltoniano - mosse: orizz./vert. salto 2, diag. salto 1"
if seed is not None:
sub += f" - seed {seed}"
sub += f" - {date.today().strftime('%d/%m/%Y')}"
c.drawCentredString(page_w / 2, page_h - margin - 12, sub)
# griglia
c.setLineWidth(0.4 if size > 30 else 0.7)
c.setStrokeColorRGB(0.6, 0.6, 0.6)
for i in range(size + 1):
c.line(ox, oy + i * cell, ox + grid_w, oy + i * cell)
c.line(ox + i * cell, oy, ox + i * cell, oy + grid_w)
def center(node):
r, col = node // size, node % size
return ox + (col + 0.5) * cell, oy + grid_w - (r + 0.5) * cell
n = size * size
if size <= 30:
# celle numerate
c.setFillColorRGB(0, 0, 0)
font_size = max(4, min(14, cell * 0.42))
c.setFont("Helvetica", font_size)
for i, node in enumerate(path):
x, y = center(node)
c.drawCentredString(x, y - font_size * 0.35, str(i + 1))
# evidenzia partenza e arrivo
for node, (rr, gg, bb) in ((path[0], (0.13, 0.55, 0.13)), (path[-1], (0.8, 0.1, 0.1))):
r, col = node // size, node % size
c.setStrokeColorRGB(rr, gg, bb)
c.setLineWidth(1.6)
c.rect(ox + col * cell, oy + grid_w - (r + 1) * cell, cell, cell)
else:
# percorso con gradiente verde -> rosso
c.setLineWidth(max(0.25, cell * 0.18))
c.setLineCap(1)
prev = center(path[0])
for i in range(1, n):
t = i / (n - 1)
c.setStrokeColorRGB(0.15 + 0.7 * t, 0.65 - 0.55 * t, 0.15)
cur = center(path[i])
c.line(prev[0], prev[1], cur[0], cur[1])
prev = cur
# marker partenza/arrivo
for node, (rr, gg, bb) in ((path[0], (0.0, 0.5, 0.0)), (path[-1], (0.8, 0.0, 0.0))):
x, y = center(node)
c.setFillColorRGB(rr, gg, bb)
c.circle(x, y, max(1.5, cell * 0.6), stroke=0, fill=1)
# legenda
c.setFont("Helvetica", 8)
c.setFillColorRGB(0.0, 0.5, 0.0)
c.drawString(ox, oy - 12, "@ partenza")
c.setFillColorRGB(0.8, 0.0, 0.0)
c.drawString(ox + 60, oy - 12, "@ arrivo")
c.setFillColorRGB(0.3, 0.3, 0.3)
c.drawString(ox + 115, oy - 12, "(il colore segue l'ordine delle mosse: verde -> rosso)")
c.showPage()
c.save()
print(f"PDF creato: {filename}")
if __name__ == "__main__":
# Uso: python gioco_100_caselle_v2.py [size] [seed] [--pdf]
# Senza argomenti: griglia 10x10 (il gioco originale)
# Con --pdf: esporta la griglia risolta in griglia_<size>x<size>.pdf
args = [a for a in sys.argv[1:] if a != "--pdf"]
make_pdf = "--pdf" in sys.argv[1:]
size = int(args[0]) if len(args) > 0 else 10
seed = int(args[1]) if len(args) > 1 else 42
if size < 5:
print(f"Nessuna soluzione esiste per griglie {size}x{size} (dimostrato per 3x3 e 4x4).")
sys.exit(1)
t0 = time.time()
path, rot = solve(size, start=0, seed=seed)
t1 = time.time()
ok = verify(path, size)
print(f"size={size} trovato={path is not None} verificato={ok} rotazioni={rot} tempo={t1-t0:.2f}s")
if path and size <= 50:
print()
print_grid(path, size)
elif path:
print("(griglia troppo grande per la stampa a video; il percorso e' nella variabile path)")
if path and make_pdf:
export_pdf(path, size, f"griglia_{size}x{size}.pdf", seed=seed)
Quando il percorso greedy finisce in un vicolo cieco, invece di tornare indietro distruggendo il lavoro fatto, il solver applica le rotazioni di Pósa: una tecnica classica della teoria dei grafi che inverte un suffisso del cammino per spostarne l'estremità, riutilizzando tutto il percorso già costruito. A questo si aggiungono un doppio criterio di scelta (grado minimo alla Warnsdorff, e a parità di grado la casella più lontana dal centro) e strutture dati piatte al posto di dizionari e insiemi.
Qui devo confessare una cosa che mi ha fatto un certo effetto. Ai tempi dell'università l'intuizione c'era stata: arrivati a un vicolo cieco, invece di buttare via tutto e tornare indietro, "ruotare" in qualche modo il percorso per ripartire da un'altra estremità. Ne discutemmo anche con i professori, ma non riuscimmo mai a trasformarla in una soluzione pratica. Scoprire oggi che quell'idea non solo era giusta, ma ha un nome, una teoria alle spalle (Lajos Pósa la formalizzò negli anni '70 per i cammini hamiltoniani) e un'implementazione efficiente, è stata la piccola rivincita personale di questo aggiornamento: l'intuito c'era, mancavano gli strumenti per dargli forma.
La differenza non è quantitativa, è qualitativa. Le taglie che facevano impazzire il codice del 2024 diventano banali, e si sblocca un ordine di grandezza del tutto nuovo (tempi misurati sulla stessa macchina della tabella precedente, seed 42):
| Griglia | Codice 2024 | Claude Fable 5 (old.py) |
|---|---|---|
| 50×50 | non termina | 0,007 s |
| 100×100 | non termina | 0,023 s |
| 150×150 | non termina | 0,066 s |
| 300×300 | — | 0,24 s |
| 500×500 | — | 0,74 s |
| 1000×1000 (1 milione di caselle) | impensabile | 3–6 s |
Dalla griglia del gioco originale, 100 caselle, a un milione di caselle in pochi secondi: già qui l'articolo del 2024 sembrava preistoria. Da notare che tutte le soluzioni sono verificate da una funzione che controlla che il cammino tocchi ogni casella una sola volta usando esclusivamente mosse legali.
Restava però un difetto ereditato dal carattere stocastico dell'algoritmo: su griglie estreme, con certi semi casuali sfortunati, il solver poteva entrare in una "tempesta di rotazioni". Nei miei test a 1000×1000, un seed su dieci non arrivava in fondo in tempi ragionevoli. Tenetelo a mente, perché è qui che la storia si fa interessante.
Secondo salto: il loop engineering
Fin qui, il flusso di lavoro era quello classico: io chiedo, l'IA risponde, io verifico. Il passo successivo è stato diverso. Ho dato a Claude un obiettivo e un budget di tentativi, così:
/goal ottimizza il codice per gestire matrici più grandi trovando
la soluzione in meno tempo possibile | fai 10 tentativiDa quel momento il modello ha lavorato in autonomia, in un ciclo che chiamano loop engineering: modifica il codice, esegue i benchmark, confronta i tempi con la versione precedente, decide se la strada è promettente e riparte. Non è più "scrivimi il codice": è delegare un'intera sessione di ingegneria delle prestazioni, misurazioni comprese.
La prima cosa che ha fatto, per conto suo, è stata profilare il codice con cProfile su una griglia 1000×1000, scoprendo che oltre metà del tempo se ne andava nella costruzione delle liste di adiacenza — quasi 9 milioni di append in puro Python — ancora prima di iniziare a risolvere. Da lì, una progressione di quattro versioni: costruzione vettorizzata con numpy, fusione di due passate sui vicini in una sola, e infine la svolta, la compilazione dell'intero solver in codice macchina con numba. Ha perfino scovato da solo il seed patologico di cui parlavo sopra: la baseline col seed 6 bruciava 263 secondi senza trovare nulla, mentre la nuova randomizzazione (l'ordine delle mosse mescolato una volta sola, fuori dal ciclo caldo) ha fatto semplicemente sparire il caso degenere.
I numeri della prima sessione di loop, sulla mia macchina, 10 tentativi richiesti (dettagli nel suo stesso report finale):
| Griglia | old.py | Prima ottimizzazione | Speedup |
|---|---|---|---|
| 1000×1000 | mediana 1,95 s, max 263 s, 1 fallimento su 10 seed | mediana 0,093 s, 0 fallimenti | ~21× |
| 3000×3000 (9 milioni di caselle) | non praticabile | 0,91 s | — |
| 5000×5000 (25 milioni di caselle) | non praticabile | 2,9 s | — |
Terzo salto: il secondo loop
Visto il risultato, ho rilanciato con lo stesso obiettivo e un budget più ampio:
/goal ottimizza il codice per gestire matrici più grandi trovando
la soluzione in meno tempo possibile | fai massimo 20 tentativiNe ha usati 8. E qui la profilazione ha rivelato una cosa controintuitiva: il collo di bottiglia non era più l'algoritmo, ma le tabelle precalcolate che lo alimentavano. A 5000×5000 la matrice dei vicini pesava 800 MB e costava più tempo costruirla che risolvere la griglia; a 10000×10000 avrebbe richiesto oltre 3 GB, rendendo la taglia di fatto impossibile. La soluzione della versione finale (gioco_100_caselle_v2.py) è elegante: niente tabelle. Vicini e distanza dal centro vengono calcolati al volo con pura aritmetica sulle coordinate, dentro il kernel compilato. Nel ciclo caldo, la ALU batte la RAM: fare un conto costa meno che leggere un valore in memoria. Il consumo scende da ~44 a ~10 byte per casella, e i risultati (sulla mia macchina, 32 GB di RAM):
| Griglia | Caselle | Prima ottim. | Seconda ottim. |
|---|---|---|---|
| 1000×1000 | 1 M | 0,40 s | 0,025 s |
| 5000×5000 | 25 M | 2,55 s | 0,71 s |
| 8000×8000 | 64 M | — | 1,8 s |
| 10000×10000 | 100 M | impossibile (>3 GB di RAM) | 2,9 s |
| 20000×20000 | 400 M | — | 12,5 s |
| 30000×30000 | 900 M | — | 28,7 s (~9 GB di RAM) |
Novecento milioni di caselle in meno di mezzo minuto, a un ritmo di circa 35 milioni di caselle al secondo, con verifica completa della soluzione. Il loop si è fermato solo davanti a limiti fisici, documentandoli con precisione: gli indici a 32 bit del kernel reggono fino a griglie 46340×46340 (~2,1 miliardi di caselle), e la RAM della mia macchina si esaurisce intorno a 30000–40000. Oltre, servirebbe una decomposizione a blocchi. Anche sapere perché ci si ferma è un risultato.
"""
Gioco delle 100 caselle - solver v6 (ottimizzato per griglie molto grandi)
- Warnsdorff con doppio tie-break: grado minimo, poi distanza max dal centro
- Rotazioni di Pósa "intelligenti": preferisce nuovi estremi con vicini liberi
e suffissi corti da invertire
- Kernel numba senza tabelle: vicini e distanza dal centro calcolati al volo
dalle coordinate (niente matrice (n,8) ne' cdist) -> ~3x piu' veloce e
memoria O(10 byte/cella); 10000x10000 (100M caselle) in ~3s
- Il seed randomizza l'ordine delle mosse (tie-break deterministico nel loop
caldo, niente RNG per passo); verify() vettorizzato con numpy
"""
import random, sys, time
import numpy as np
try:
from numba import njit
HAS_NUMBA = True
except ImportError:
HAS_NUMBA = False
MOVES = [(3,0),(-3,0),(0,3),(0,-3),(2,2),(2,-2),(-2,2),(-2,-2)]
def build_neighbors(size, moves=MOVES):
"""Liste di adiacenza + gradi iniziali.
Fast path: le celle interne (margine >= 3) hanno tutte le 8 mosse valide e
vengono generate in blocco con numpy; solo il bordo usa il ciclo Python.
"""
m = 3 # margine massimo delle mosse
if size <= 2*m:
# griglia piccola: percorso semplice
neigh = []
for r in range(size):
for c in range(size):
neigh.append([(r+dr)*size + (c+dc) for dr, dc in moves
if 0 <= r+dr < size and 0 <= c+dc < size])
return neigh, [len(l) for l in neigh]
offsets = np.array([dr*size + dc for dr, dc in moves], dtype=np.int32)
inner = np.arange(m, size-m, dtype=np.int32)
interior = (inner[:, None]*size + inner[None, :]).ravel()
chunk = size - 2*m
# (celle interne, 8) -> liste pronte, nessun filtro necessario
int_rows = (interior[:, None] + offsets[None, :]).tolist()
def border_row(r, c0, c1):
out = []
for c in range(c0, c1):
out.append([(r+dr)*size + (c+dc) for dr, dc in moves
if 0 <= r+dr < size and 0 <= c+dc < size])
return out
neigh = []
k = 0
for r in range(m):
neigh.extend(border_row(r, 0, size))
for r in range(m, size-m):
neigh.extend(border_row(r, 0, m))
neigh.extend(int_rows[k:k+chunk])
k += chunk
neigh.extend(border_row(r, size-m, size))
for r in range(size-m, size):
neigh.extend(border_row(r, 0, size))
# gradi iniziali calcolati in blocco (conta mosse valide per cella)
cnt = np.zeros((size, size), dtype=np.int8)
for dr, dc in moves:
r_ok = np.zeros(size, dtype=bool); r_ok[max(0, -dr):size-max(0, dr)] = True
c_ok = np.zeros(size, dtype=bool); c_ok[max(0, -dc):size-max(0, dc)] = True
cnt += r_ok[:, None] & c_ok[None, :]
return neigh, cnt.ravel().tolist()
def center_dist(size):
"""(2r-(size-1))^2 + (2c-(size-1))^2: interi, stesso ordinamento dei float."""
d = (2*np.arange(size, dtype=np.int64) - (size-1))**2
return (d[:, None] + d[None, :]).ravel().tolist()
if HAS_NUMBA:
@njit(cache=True)
def _solve_kernel(size, dr, dc, deg, start, max_rot, rng_state):
# vicini e distanza dal centro calcolati al volo dalle coordinate:
# niente matrice (n,8) ne' array cdist -> memoria minima, zero
# cache-miss sulle tabelle; ranking identico alla versione precedente
n = size*size
nm = dr.shape[0]
s1 = size - 1
visited = np.zeros(n, np.uint8)
path = np.empty(n, np.int32)
pos = np.full(n, -1, np.int32)
path[0] = start; pos[start] = 0; visited[start] = 1
r0 = start // size; c0 = start % size
for k in range(nm):
rr = r0 + dr[k]; cc = c0 + dc[k]
if 0 <= rr < size and 0 <= cc < size:
deg[rr*size + cc] -= 1
plen = 1
cur = start
rotations = 0
state = rng_state
good = np.empty(nm, np.int64)
fall = np.empty(nm, np.int64)
while plen < n:
# passo greedy: grado min, poi distanza max dal centro
cr = cur // size; ccur = cur % size
bd = 99; bdist = np.int64(-1); nxt = -1; nr = 0; ncol = 0
for k in range(nm):
rr = cr + dr[k]; cc = ccur + dc[k]
if 0 <= rr < size and 0 <= cc < size:
nb = rr*size + cc
if visited[nb] == 0:
d = deg[nb]
if d < bd:
bd = d
bdist = (2*rr-s1)**2 + (2*cc-s1)**2
nxt = nb; nr = rr; ncol = cc
elif d == bd:
dd = (2*rr-s1)**2 + (2*cc-s1)**2
if dd > bdist:
bdist = dd; nxt = nb; nr = rr; ncol = cc
if nxt >= 0:
# avanzamento a catena: decremento gradi + scelta successiva
# in un'unica passata (ranking identico alla forma non fusa)
while True:
visited[nxt] = 1
pos[nxt] = plen
path[plen] = nxt
plen += 1
xr = nr; xc = ncol
bd = 99; bdist = np.int64(-1); new = -1
for k in range(nm):
rr = xr + dr[k]; cc = xc + dc[k]
if 0 <= rr < size and 0 <= cc < size:
nb = rr*size + cc
deg[nb] -= 1
if visited[nb] == 0:
d = deg[nb]
if d < bd:
bd = d
bdist = (2*rr-s1)**2 + (2*cc-s1)**2
new = nb; nr = rr; ncol = cc
elif d == bd:
dd = (2*rr-s1)**2 + (2*cc-s1)**2
if dd > bdist:
bdist = dd; new = nb; nr = rr; ncol = cc
if new < 0 or plen == n:
cur = nxt
break
nxt = new
continue
# vicolo cieco -> rotazione di Pósa
rotations += 1
if rotations > max_rot:
return path, rotations, 0
cr = cur // size; ccur = cur % size
ng = 0; nf = 0
for k in range(nm):
rr = cr + dr[k]; cc = ccur + dc[k]
if rr < 0 or rr >= size or cc < 0 or cc >= size:
continue
i = pos[rr*size + cc]
if i >= plen-2: # rotazione nulla
continue
new_end = path[i+1]
er = new_end // size; ec = new_end % size
has_free = False
for k2 in range(nm):
r2 = er + dr[k2]; c2 = ec + dc[k2]
if 0 <= r2 < size and 0 <= c2 < size and visited[r2*size + c2] == 0:
has_free = True
break
if has_free:
good[ng] = i; ng += 1
else:
fall[nf] = i; nf += 1
if ng > 0:
cand = good; nc = ng
elif nf > 0:
cand = fall; nc = nf
else:
return path, rotations, 0
# scelta casuale (LCG) con leggera preferenza per suffissi corti
state = state * 6364136223846793005 + 1442695040888963407
r = (state >> 33) & 0x7FFFFFFF
if (r & 1) == 0:
i = cand[0]
for j in range(1, nc):
if cand[j] > i:
i = cand[j]
else:
state = state * 6364136223846793005 + 1442695040888963407
i = cand[((state >> 33) & 0x7FFFFFFF) % nc]
lo = i+1; hi = plen-1
while lo < hi:
a = path[lo]; b = path[hi]
path[lo] = b; path[hi] = a
pos[b] = lo; pos[a] = hi
lo += 1; hi -= 1
if lo == hi:
pos[path[lo]] = lo
cur = path[plen-1]
return path, rotations, 1
def init_degrees(size, moves):
"""Gradi iniziali (n,) int8, calcolati in blocco senza matrice dei vicini."""
cnt = np.zeros((size, size), dtype=np.int8)
for dr, dc in moves:
r_ok = np.zeros(size, dtype=bool); r_ok[max(0, -dr):size-max(0, dr)] = True
c_ok = np.zeros(size, dtype=bool); c_ok[max(0, -dc):size-max(0, dc)] = True
cnt += r_ok[:, None] & c_ok[None, :]
return cnt.ravel()
MAX_SIZE_INT32 = 46340 # size*size deve stare in int32 (indici di path/pos)
def solve_numba(size, start=0, seed=None, max_rotations_factor=200):
if size > MAX_SIZE_INT32:
raise ValueError(
f"size={size} troppo grande: gli indici int32 del kernel supportano "
f"al massimo {MAX_SIZE_INT32}x{MAX_SIZE_INT32} (~2.1 miliardi di caselle).")
n = size*size
need_gb = 10*n / 1e9 # visited+deg+path+pos = 10 byte/cella
try:
import psutil
avail_gb = psutil.virtual_memory().available / 1e9
except ImportError:
avail_gb = None
if avail_gb is not None and need_gb > avail_gb:
raise MemoryError(
f"griglia {size}x{size}: servono ~{need_gb:.1f} GB di RAM per gli array "
f"del solver, disponibili ~{avail_gb:.1f} GB. Riduci la taglia "
f"(indicativamente size <= {int((avail_gb*1e9/10)**0.5)}).")
rng = random.Random(seed)
moves = list(MOVES)
rng.shuffle(moves)
dr = np.array([m[0] for m in moves], dtype=np.int64)
dc = np.array([m[1] for m in moves], dtype=np.int64)
deg = init_degrees(size, moves)
path, rotations, ok = _solve_kernel(size, dr, dc, deg, start,
int(max_rotations_factor*n),
rng.getrandbits(63) | 1)
if not ok:
return None, rotations
return path, rotations
def solve(size, start=0, seed=None, max_rotations_factor=200):
if HAS_NUMBA:
return solve_numba(size, start, seed, max_rotations_factor)
return solve_python(size, start, seed, max_rotations_factor)
def solve_python(size, start=0, seed=None, max_rotations_factor=200):
rng = random.Random(seed)
n = size*size
# il seed varia l'ordine delle mosse: cambia il tie-break senza costi nel loop
moves = list(MOVES)
rng.shuffle(moves)
neigh, deg = build_neighbors(size, moves)
cdist = center_dist(size)
visited = bytearray(n)
path = [0]*n
path[0] = start
pos = [-1]*n
pos[start] = 0; visited[start] = 1
for nb in neigh[start]: deg[nb] -= 1
plen = 1
cur = start
rotations = 0
max_rotations = max_rotations_factor*n
while plen < n:
# passo greedy: grado min, poi distanza max dal centro
# (a parità: primo nell'ordine delle mosse, mescolato dal seed)
bd = 99; bdist = -1; nxt = -1
for nb in neigh[cur]:
if not visited[nb]:
d = deg[nb]
if d < bd:
bd = d; bdist = cdist[nb]; nxt = nb
elif d == bd:
dd = cdist[nb]
if dd > bdist:
bdist = dd; nxt = nb
if nxt >= 0:
# avanzamento a catena: decremento gradi e scelta del successivo
# in un'unica passata sui vicini (ogni candidato riceve il proprio
# -1 prima della lettura, quindi il ranking e' identico)
while True:
visited[nxt] = 1
pos[nxt] = plen
path[plen] = nxt
plen += 1
bd = 99; bdist = -1; new = -1
for nb in neigh[nxt]:
deg[nb] -= 1
if not visited[nb]:
d = deg[nb]
if d < bd:
bd = d; bdist = cdist[nb]; new = nb
elif d == bd:
dd = cdist[nb]
if dd > bdist:
bdist = dd; new = nb
if new < 0 or plen == n:
cur = nxt
break
nxt = new
continue
# vicolo cieco -> rotazione di Pósa
rotations += 1
if rotations > max_rotations:
return None, rotations
good, fallback = [], []
for v in neigh[cur]:
i = pos[v]
if i >= plen-2: # rotazione nulla
continue
new_end = path[i+1]
# il nuovo estremo ha vicini non visitati?
has_free = any(not visited[x] for x in neigh[new_end])
(good if has_free else fallback).append(i)
cand = good if good else fallback
if not cand:
return None, rotations
# scelta casuale (evita cicli) con leggera preferenza per suffissi corti
i = max(cand) if rng.random() < 0.5 else cand[rng.randrange(len(cand))]
lo, hi = i+1, plen-1
path[lo:hi+1] = path[lo:hi+1][::-1]
for j in range(lo, hi+1):
pos[path[j]] = j
cur = path[plen-1]
return path, rotations
def verify(path, size, chunk=8_000_000):
"""Verifica vettorizzata a blocchi: temporanei limitati a `chunk` elementi,
cosi' non raddoppia la memoria a griglie enormi."""
n = size*size
if path is None or len(path) != n:
return False
p = np.asarray(path)
seen = np.zeros(n, dtype=bool)
for i in range(0, n, chunk):
blk = p[i:i+chunk]
if blk.min() < 0 or blk.max() >= n:
return False
seen[blk] = True
if not seen.all():
return False
del seen
for i in range(0, n-1, chunk):
a = p[i:i+chunk] # ultimo elemento del blocco incluso
b = p[i+1:i+chunk+1] # come primo del confronto successivo
m = min(len(a), len(b))
drs = b[:m]//size - a[:m]//size
dcs = b[:m]%size - a[:m]%size
ok = ((np.abs(drs) == 3) & (dcs == 0)) | ((drs == 0) & (np.abs(dcs) == 3)) \
| ((np.abs(drs) == 2) & (np.abs(dcs) == 2))
if not ok.all():
return False
return True
def print_grid(path, size):
"""Stampa la griglia con il numero d'ordine di ogni mossa."""
grid = [[0]*size for _ in range(size)]
for i, node in enumerate(path):
grid[node // size][node % size] = i + 1
w = len(str(size*size))
for row in grid:
print(" ".join(f"{cell:{w}}" for cell in row))
def export_pdf(path, size, filename, seed=None):
"""Esporta la griglia risolta in PDF (A4).
- size <= 30: celle numerate come nel gioco su carta
- size > 30: percorso disegnato con gradiente di colore (verde -> rosso)
"""
from reportlab.lib.pagesizes import A4
from reportlab.lib.units import mm
from reportlab.pdfgen import canvas as pdfcanvas
from datetime import date
page_w, page_h = A4
margin = 18 * mm
title_h = 16 * mm
avail = min(page_w - 2 * margin, page_h - 2 * margin - title_h)
cell = avail / size
grid_w = cell * size
ox = (page_w - grid_w) / 2
oy = (page_h - title_h - grid_w) / 2
c = pdfcanvas.Canvas(filename, pagesize=A4)
# intestazione
c.setFont("Helvetica-Bold", 16)
c.drawCentredString(page_w / 2, page_h - margin, f"Gioco delle {size*size} caselle - griglia {size}x{size}")
c.setFont("Helvetica", 9)
sub = f"Cammino hamiltoniano - mosse: orizz./vert. salto 2, diag. salto 1"
if seed is not None:
sub += f" - seed {seed}"
sub += f" - {date.today().strftime('%d/%m/%Y')}"
c.drawCentredString(page_w / 2, page_h - margin - 12, sub)
# griglia
c.setLineWidth(0.4 if size > 30 else 0.7)
c.setStrokeColorRGB(0.6, 0.6, 0.6)
for i in range(size + 1):
c.line(ox, oy + i * cell, ox + grid_w, oy + i * cell)
c.line(ox + i * cell, oy, ox + i * cell, oy + grid_w)
def center(node):
r, col = node // size, node % size
return ox + (col + 0.5) * cell, oy + grid_w - (r + 0.5) * cell
n = size * size
if size <= 30:
# celle numerate
c.setFillColorRGB(0, 0, 0)
font_size = max(4, min(14, cell * 0.42))
c.setFont("Helvetica", font_size)
for i, node in enumerate(path):
x, y = center(node)
c.drawCentredString(x, y - font_size * 0.35, str(i + 1))
# evidenzia partenza e arrivo
for node, (rr, gg, bb) in ((path[0], (0.13, 0.55, 0.13)), (path[-1], (0.8, 0.1, 0.1))):
r, col = node // size, node % size
c.setStrokeColorRGB(rr, gg, bb)
c.setLineWidth(1.6)
c.rect(ox + col * cell, oy + grid_w - (r + 1) * cell, cell, cell)
else:
# percorso con gradiente verde -> rosso
c.setLineWidth(max(0.25, cell * 0.18))
c.setLineCap(1)
prev = center(path[0])
for i in range(1, n):
t = i / (n - 1)
c.setStrokeColorRGB(0.15 + 0.7 * t, 0.65 - 0.55 * t, 0.15)
cur = center(path[i])
c.line(prev[0], prev[1], cur[0], cur[1])
prev = cur
# marker partenza/arrivo
for node, (rr, gg, bb) in ((path[0], (0.0, 0.5, 0.0)), (path[-1], (0.8, 0.0, 0.0))):
x, y = center(node)
c.setFillColorRGB(rr, gg, bb)
c.circle(x, y, max(1.5, cell * 0.6), stroke=0, fill=1)
# legenda
c.setFont("Helvetica", 8)
c.setFillColorRGB(0.0, 0.5, 0.0)
c.drawString(ox, oy - 12, "@ partenza")
c.setFillColorRGB(0.8, 0.0, 0.0)
c.drawString(ox + 60, oy - 12, "@ arrivo")
c.setFillColorRGB(0.3, 0.3, 0.3)
c.drawString(ox + 115, oy - 12, "(il colore segue l'ordine delle mosse: verde -> rosso)")
c.showPage()
c.save()
print(f"PDF creato: {filename}")
if __name__ == "__main__":
# Uso: python gioco_100_caselle_v2.py [size] [seed] [--pdf]
# Senza argomenti: griglia 10x10 (il gioco originale)
# Con --pdf: esporta la griglia risolta in griglia_<size>x<size>.pdf
args = [a for a in sys.argv[1:] if a != "--pdf"]
make_pdf = "--pdf" in sys.argv[1:]
size = int(args[0]) if len(args) > 0 else 10
seed = int(args[1]) if len(args) > 1 else 42
if size < 5:
print(f"Nessuna soluzione esiste per griglie {size}x{size} (dimostrato per 3x3 e 4x4).")
sys.exit(1)
t0 = time.time()
path, rot = solve(size, start=0, seed=seed)
t1 = time.time()
ok = verify(path, size)
backend = "numba" if HAS_NUMBA else "python"
print(f"size={size} trovato={path is not None} verificato={ok} rotazioni={rot} tempo={t1-t0:.2f}s [{backend}]")
if path is not None and size <= 50:
print()
print_grid(path, size)
elif path is not None:
print("(griglia troppo grande per la stampa a video; il percorso e' nella variabile path)")
if path is not None and make_pdf:
export_pdf(path, size, f"griglia_{size}x{size}.pdf", seed=seed)
Il quadro d'insieme
Per confrontare le tre generazioni ad armi pari ho rieseguito tutto su una stessa macchina (volutamente modesta, 2 core — sulla mia i tempi sono circa la metà). Alla taglia simbolo di 1000×1000, un milione di caselle:
| Versione | 1000×1000 | Affidabilità (10 seed) |
|---|---|---|
| Codice 2024 (ChatGPT) | non termina | fallisce già a 50×50 |
Claude Fable 5 (old.py) | mediana ~3,6 s | 9/10 (seed 6 patologico) |
| Dopo il loop engineering (v2) | 0,042 s | 10/10 |
E ricordiamo da dove eravamo partiti: nel 2024 festeggiavo la griglia 10×10. La versione attuale risolve e verifica griglie 9 milioni di volte più grandi del gioco originale.
Ma quindi abbiamo "semplificato" un problema NP-completo?
Una precisazione doverosa per i lettori più tecnici, perché la domanda è legittima: se la ricerca di un cammino hamiltoniano è NP-completa, come fa questo solver ad andare quasi in tempo lineare? La risposta è che non abbiamo domato l'NP-completezza — quella è un'affermazione sul caso peggiore su tutti i grafi possibili, e chi la superasse avrebbe dimostrato P=NP. Abbiamo invece sfruttato il fatto che il grafo di questo gioco è un'istanza particolarmente favorevole: denso (quasi ogni casella ha 8 mosse disponibili), regolare, con la difficoltà concentrata su bordi e angoli — esattamente ciò che l'euristica di Warnsdorff sa gestire. Lo si legge nei numeri: su un milione di caselle, le rotazioni di Pósa — i "ripensamenti" del solver — si contano sulle dita di una mano. Non a caso la teoria di Pósa nasce dallo studio dei grafi densi, dove i cammini hamiltoniani non solo esistono quasi sempre, ma si trovano facilmente; e il parallelo perfetto è il giro del cavallo, cugino stretto di questo gioco, per cui Warnsdorff inventò la sua regola già nel 1823: problema intrattabile in generale, facile sulle scacchiere.
Il prezzo di questa velocità è la mancanza di garanzie: il solver è un'euristica randomizzata. Quando trova un cammino, la verifica lo certifica al 100%; quando non lo trova, non ha dimostrato nulla — dice solo che quella sequenza di scelte si è incagliata. Il backtracking del 2024, con tempo infinito, una risposta definitiva prima o poi la darebbe; l'euristica no. Abbiamo barattato la completezza con la velocità e, su questo problema, è un baratto stravinto. Il mio sospetto da studente — "è un problema alla commesso viaggiatore" — era fondato; la fortuna è che il gioco delle 100 caselle vive in un angolo felice di quel problema, e il salto dal 2024 al 2026 è consistito nel passare da un algoritmo che ci inciampava a uno che quell'angolo felice lo sfrutta fino in fondo.
Cosa ho imparato
Due anni fa la notizia era che l'IA avesse trovato la strada giusta — l'euristica di Warnsdorff — dove io per anni avevo sbattuto contro la ricorsione cieca. Era l'IA come consulente: le chiedi una cosa, te la dà, e il pezzo difficile (capire se è buona, misurarla, migliorarla) resta a te.
Il salto di questi giorni è di natura diversa, e in realtà sono due salti distinti. Il primo è la qualità del modello: Claude Fable 5, con una singola richiesta, ha prodotto un solver che non solo è più veloce, ma è algoritmicamente più onesto — le rotazioni di Pósa al posto del backtracking hanno trasformato una roulette russa in uno strumento affidabile. Il secondo è il metodo: con il loop engineering non ho più dettato le soluzioni, ho dettato l'obiettivo e il criterio di arresto. Profilare, ipotizzare, implementare, misurare, verificare, decidere se continuare: l'intero ciclo dell'ingegneria delle prestazioni è avvenuto dentro il loop, tentativo dopo tentativo, con tanto di report finale che documenta i vicoli ciechi e i limiti raggiunti.
La cosa che mi colpisce di più, ripensando allo studente che riempiva quadretti a mano negli anni '80, è che il mio ruolo non è sparito: si è spostato più in alto. Scegliere il problema, formulare l'obiettivo, decidere quanto budget dargli, giudicare i risultati. La macchina ha imparato a fare il ciclo di lavoro; a noi resta — per ora — il compito di decidere quale ciclo valga la pena far girare.
I report generati dai due loop di ottimizzazione sono disponibili su richiesta. L'articolo originale del 2024, con le regole del gioco e la storia completa, è qui.
Errata e precisazioni (aggiornamento successivo alla pubblicazione)
Dopo la pubblicazione, un lettore competente mi ha inviato una revisione tecnica puntuale di questo articolo. Nello spirito di quanto raccontato qui sopra — fidarsi è bene, misurare è meglio — ho verificato ogni rilievo, rifatto i test dove serviva, e riporto di seguito le correzioni. Alcune sono limature terminologiche; una, l'ultima, è una correzione sostanziale che ho scoperto proprio grazie a questa revisione.
Il grafo è sparso, non denso. Nell'articolo ho scritto che il grafo del gioco è "denso". In teoria dei grafi è il contrario: con N caselle ci sono circa 4N archi (ogni casella ha al massimo 8 mosse) contro gli ~N²/2 di un grafo completo — a 1000×1000, quattro milioni di archi su cinquecento miliardi possibili. La formulazione corretta è che si tratta di una famiglia di grafi sparsi, quasi regolari e a grado limitato, dove quasi tutte le caselle interne hanno le 8 mosse disponibili e la difficoltà si concentra su bordi e angoli. Ed è proprio questo il contesto giusto anche per Pósa: il suo lavoro del 1976 riguardava grafi casuali con circa n·log n archi — sparsi, appunto — dove i cammini hamiltoniani non solo esistono quasi sempre, ma si trovano facilmente.
NP-completezza, con più precisione. A rigore è la versione decisionale del problema ("esiste un cammino hamiltoniano?") a essere NP-completa, su grafi arbitrari; la ricerca concreta del cammino è NP-hard. Soprattutto: nessuno ha dimostrato che questa specifica famiglia di grafi-griglia condivida quella complessità. Potrebbe benissimo esistere una costruzione deterministica polinomiale per ogni taglia ammissibile — per il giro del cavallo, cugino stretto di questo gioco, esiste. Quindi il gioco è un'istanza di un problema difficile in generale, non necessariamente un problema difficile esso stesso.
Come sono misurati i tempi. I tempi del backend numba riportati nelle tabelle sono misurati con il kernel già compilato (dopo un warm-up): la primissima esecuzione in assoluto paga circa 1–2 secondi di compilazione JIT, poi salvata su disco. Le tabelle della seconda ottimizzazione (10000², 20000², 30000²) provengono dal report di lavoro e includono solve e verifica; la tabella di confronto tra le tre generazioni misura invece il solo tempo di risoluzione, con la verifica eseguita separatamente (a 1000×1000 la verifica aggiunge qualche centesimo di secondo). Chi esegue il programma una sola volta, a freddo, vedrà quindi tempi più alti di quelli tabellati. Preciso anche che i ~10 byte per casella citati si riferiscono agli array del solver: il picco di memoria dell'intero processo è superiore, soprattutto durante inizializzazione e verifica. Infine, sul codice del 2024 avevo scritto che "fallisce già a 50×50": più esattamente, può non terminare già a 50×50 — nei miei stessi test riusciva in millisecondi a 60×60, 70×70, 90×90 e 120×120, per poi incagliarsi di nuovo a 80×80, 100×100 e 150×150. È proprio questa imprevedibilità il suo difetto.
Il caso degenere non è "sparito" — correzione sostanziale. Nell'articolo ho scritto che la nuova randomizzazione aveva fatto "semplicemente sparire" le tempeste di rotazioni. Il revisore ha osservato, giustamente, che 10 seed sono un campione troppo piccolo per un'affermazione del genere. Ho quindi rifatto il test su 300 seed a 1000×1000, e aveva ragione lui: la mediana resta di pochi centesimi di secondo, ma il seed 57 ha richiesto 12,7 secondi (70.000 rotazioni), il seed 84 ben 387 secondi (817.000 rotazioni), e un terzo seed girava ancora dopo 8 minuti quando ho interrotto la prova. La distribuzione dei tempi ha una coda pesante: i casi difficili sono rari, ma esistono ancora. La differenza reale rispetto alla versione precedente è un'altra, e resta importante: quei casi ora convergono comunque a una soluzione invece di esaurire il limite di rotazioni e fallire. Ma "più robusto" era la parola giusta; "sparito" no. Resta vero anche il limite di fondo già dichiarato: quando l'euristica non trova il cammino, non ha dimostrato che il cammino non esista.
