Gioco del quindici: differenze tra le versioni

Versione delle 16:31, 1 giu 2006

Versione attuale delle 05:22, 13 mar 2025

(89 versioni intermedie di 63 utenti non mostrate)

Riga 1:

[[File:15-puzzle.svg|thumb|right|Il gioco del quindici risolto]]

== Descrizione del gioco ==

Il '''gioco del quindici''' è un [[rompicapo]] classico creato nel [[1874]] da Noyes Palmer Chapman<ref>Jerry Slocum e Dic Sonneveld, ''The 15 Puzzle'', 2006. ISBN 1-890980-15-3</ref> (North Stonington, 14 gennaio 1811 – Canastota, 28 aprile 1889)<ref>https://unoscacchista.com/2019/09/13/il-gioco-del-15-e-un-rovescio-di-sam-loyd/</ref><ref>https://it.findagrave.com/memorial/48928889/noyes-palmer-chapman</ref>, 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 sedici posizioni), su cui sono posizionate quindici tessere quadrate, numerate progressivamente a partire da 1. Le tessere possono scorrere in orizzontale o verticale, ma il loro spostamento è 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 [[Funzione euristica|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 [[Geometria del taxi|distanze di Manhattan]] tra ogni tessera e la sua posizione corretta.<ref name="Korf,2000">{{Cita pubblicazione|nome=Richard E. |cognome=Korf |url=https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf | doi=10.1007/3-540-44914-0_3 |contributo=Recent progress in the design and analysis of admissible heuristic functions |serie=SARA 2000. Abstraction, reformulation, and approximation: 4th international symposium, Texas, USA. LNCS 1864 |pp=45-55 |editore=Springer |anno=2000 | isbn=978-3-540-67839-7 |accesso=26 aprile 2010 |titolo=Recent Progress in the Design and Analysis of Admissible Heuristic Functions |volume=1864|lingua=en}}</ref> Entrambe le euristiche sono [[Euristica ammissibile|ammissibili]] (ovvero non sovrastimano mai il numero di mosse mancanti), quindi permettono di risolvere il problema in maniera ottimale per alcuni algoritmi come A*.<ref name="Korf,2000"/>

[[Immagine:Quindici.jpg|right|frame|Un esempio di gioco del quindici per PC]]

Il gioco del quindici è un classico [[gioco da tavolo]] [[solitario]], inventato da [[Samuel Loyd]] ([[1841]] - [[1911]]) nel [[1878]]. Il gioco consiste di una tavoletta di forma quadrata, solitamente di materiale plastico, sulla quale sono disposte, su quattro righe e quattro colonne, quindici caselline quadrate contrassegnate da un numero progressivo ed in grado di scorrere, seguendo una direzione ortogonale, verso uno spazio libero adiacente. Lo scopo del gioco è ordinare le caselle in senso crescente partendo da una configurazione casuale, in modo da ritornare alla posizione originaria che prevede il numero uno in alto a sinistra e lo spazio vuoto in basso a destra.

== Cenni storiciStoria ==

Loyd descrisse per la prima volta il suo ''fifteen puzzle'' ("rompicapo del quindici") nel volume ''[[Sam Loyd's Cyclopaedia of 5000 Puzzles, Tricks and Conundrums]]'', pubblicato postumo nel [[1914]] dal figlio (anche lui Samuel Loyd). Il gioco ebbe subito grande successo, contribuendo alla fama del suo inventore, già rinomato [[enigmistica|enigmista]] e autore di altri giochi di successo.

Loyd mise in palio la cifra di mille [[USD|dollari]] come premio per chi fosse riuscito a risolvere una versione del gioco partendo da una posizione identica a quella tradizionalefinale, ma con i numeri 14 e 15 a posizioni invertitescambiati. Un premio che nessuno mai avrebbe potuto reclamare, poiché, come l'autore sapeva benissimo, la soluzione del gioco partendo da una siffattatale configuarazioneconfigurazione è matematicamente impossibile.

Loyd descrisse il [[puzzle]] per la prima volta nel volume "Sam Loyd's Cyclopaedia of 5000 Puzzles, Tricks and Conundrums", pubblicato postumo nel 1914 dall'omonimo figlio dell'autore.

Il gioco ebbe sin da subito grande successo, contribuendo alla fama del suo inventore, già enigmista ed autore di altri giochi di successo.

Il gioco del quindici è oggi considerato un solitario classico, un cosiddetto ''scacciapensieri'' o ''rompicapo''. È stato commercializzato da tantissime case editrici e in moltissime varianti. Molte edizioni uniscono l'idea originale con quella del [[puzzle]], distribuendo sulle tessere un disegno che riappare correttamente solo quando gli stessi sono state riordinati correttamente. Esistono anche varianti con un numero di caselle (e quindi di tessere) differente. Molte versioni [[software]] sono disponibili per [[personal computer]].

Loyd mise in palio la cifra di mille dollari come premio per chi fosse riuscito a risolvere una versione del gioco identica a quella tradizionale, ma con i numeri 14 e 15 a posizioni invertite. Un premio che nessuno mai avrebbe potuto reclamare, poiché come l'autore sapeva benissimo, la soluzione del gioco partendo da una siffatta configuarazione è matematicamente impossibile.

== Analisi matematica della soluzione ==

Il gioco del quindici è considerato un classico intrattenimento solitario, un cosiddetto "schiacciapensieri", e sono disponibili numerose versioni come [[software]] per [[computer]]

Una generalizzazione naturale del gioco del quindici è un puzzle di <math>(n* \times n)-1</math> su una griglia <math>n* \times n</math>. E' possibilePer determinare se a partire da una data configurazione di (n*n)-1<math>C1</math> se ne possa raggiungere un'altra: le<math>C2</math> dueoccorre calcolare le [[permutazione|permutazioni]] dei numeri sulle caselle (nell'ordine di lettura) devono corrispondere nella ""parità"", ovvero: il valore del numero di inversioni (coppie non ordinate), che puòdeve essere pari o dispari.

== Note ==

<references />

== Altri progetti ==

== Analisi matematica della soluzione ==

{{interprogetto}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* [http://utenti.quipo.it/base5/jsgioco15/g15did.htm Il gioco del 15] (versione didattica)

* {{cita web|url=https://itunes.apple.com/it/app/ilgiocodel15-full/id485816738?l=it&ls=1&mt=8|titolo=Una versione per iPhone/iPod touch}}

* {{cita web|url=https://play.google.com/store/apps/details?id=it.megasoft78.fifteenpuzzlex|titolo=Una versione per Android}}

{{Portale|giochi}}

Una generalizzazione naturale del gioco del quindici è un puzzle di (n*n)-1 su una griglia n*n. E' possibile determinare se a partire da una configurazione di (n*n)-1 se ne possa raggiungere un'altra: le due permutazioni dei numeri sulle caselle (nell'ordine di lettura) devono corrispondere nella ""parità"", ovvero il valore del numero di inversioni (coppie non ordinate), che può essere pari o dispari.

[[Categoria:GiochiRompicapi da tavolomeccanici]]

[[Categoria:Solitari]]

[[Categoria:Problemi NP-completi]]