Matematica e teoria

Tutto sul gioco del 15, per tema: modalità di gioco, risolutori, puzzle con foto e la matematica dietro le configurazioni impossibili.

Articoli Modalità di gioco Solver e soluzioni Puzzle con foto personali Per chi Matematica e teoria
Algoritmo del 15-puzzle — da BFS ai database di pattern

Una storia degli algoritmi per risolvere il 15-puzzle: BFS, A* con distanza di Manhattan, IDA*, walking distance e database di pattern additivi.
Perché alcuni 15-puzzle non si possono risolvere — la regola della parità

Il teorema di parità del 15-puzzle: controlla se una griglia è risolvibile contando le inversioni più la riga del vuoto. Dimostrazione pulita e la storia di Sam Loyd.
Euristica della distanza di Manhattan — perché funziona

Come funziona l’euristica della distanza di Manhattan, perché è ammissibile e consistente, e dove non basta per risolvere i puzzle scorrevoli.
Strategia per puzzle scorrevoli — le tecniche che scalano

Le quattro tecniche che risolvono a mano qualsiasi puzzle a tessere scorrevoli: riduzione riga-e-colonna, manovra a L dell’angolo, instradamento del vuoto, endgame.
Perché alcuni 15-puzzle non si possono risolvere — un controllo in linguaggio semplice

Come controllare se un 15-puzzle è risolvibile, in linguaggio semplice: conta le inversioni, aggiungi la riga del vuoto, controlla la parità. Cosa fare se ottieni una griglia cattiva.