Gioco del quindici - puzzle online

Puzzle online Gioco del quindici

Gioco del quindici

Il gioco del quindici è un rompicapo classico creato nel 1874 da Noyes Palmer Chapman (North Stonington, 14 gennaio 1811 – Canastota, 28 aprile 1889), postino in servizio a Canastota, e popolarizzato nel 1891 da Samuel Loyd. Il gioco consiste di una tabellina di forma quadrata, solitamente di plastica, divisa in quattro righe e quattro colonne (quindi 16 posizioni), su cui sono posizionate 15 tessere quadrate, numerate progressivamente a partire da 1. Le tessere possono scorrere in orizzontale o verticale, ma il loro spostamento è ovviamente limitato dall'esistenza di un singolo spazio vuoto. Lo scopo del gioco è riordinare le tessere dopo averle "mescolate" in modo casuale (la posizione da raggiungere è quella con il numero 1 in alto a sinistra e gli altri numeri a seguire da sinistra a destra e dall'alto in basso, fino al 15 seguito dalla casella vuota).

Il gioco del quindici (spesso generalizzato in versione n-esima) è un classico problema con cui vengono spiegati gli algoritmi basati su euristiche. Fra le euristiche comunemente usate per questo problema abbiamo il numero di tessere con posizione errata (il cui tipico modello matematico è la distanza di Hamming) e la somma delle distanze di Manhattan tra ogni tessera e la sua posizione corretta. Entrambe le euristiche sono ammissibili (ovvero non sovrastimano mai il numero di mosse mancanti), quindi permettono di risolvere il problema in maniera ottimale per alcuni algoritmi come A*.