Gioco del quindici: differenze tra le versioni

Versione delle 13:58, 20 apr 2010

Versione attuale delle 05:22, 13 mar 2025

(41 versioni intermedie di 32 utenti non mostrate)

Riga 1:

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

Il '''gioco del quindici''' è un [[rompicapo]] classico inventatocreato danel [[Samuel1874]] Loydda 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 [[18781891]] da [[Samuel Loyd]]. Il gioco consiste di una tabellina di forma quadrata, solitamente di [[plastica]], divisa in quattro righe e quattro colonne (quindi 16sedici posizioni), su cui sono posizionate 15quindici 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). In questo senso, la dinamica generale del gioco presenta delle evidenti analogie con quella del [[cubo di Rubik]].

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"/>

== Cenni storici ==

== Storia ==

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.

Riga 10 ⟶ 12:

== Analisi matematica della soluzione ==

Una generalizzazione naturale del gioco del quindici è un puzzle di <math>(n \times n)-1</math> su una griglia <math>n \times n</math>. Per determinare se a partire da una data configurazione <math>C1</math> se ne possa raggiungere un'altra <math>C2</math> occorre calcolare le [[permutazione|permutazioni]] dei numeri sulle caselle (nell'ordine di lettura): il numero di inversioni (coppie non ordinate), deve essere pari.

== Collegamenti esterniNote ==

<references />

== Altri progetti ==

{{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}}

* [http://www2.polito.it/didattica/polymath/htmlS/probegio/GAMEMATH/Blocchetti/Blocchetti.htm Giochi a blocchetti mobili]

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

{{Portale|giochi}}

* [http://www.gioco15.altervista.org Gioco del 15]

[[Categoria:GiochiRompicapi di logicameccanici]]

[[Categoria:Rompicapi matematici e logici]]

[[Categoria:Solitari]]

[[Categoria:Problemi NP-completi]]

[[cs:Patnáctka]]

[[da:15-spillet]]

[[de:15-Puzzle]]

[[en:Fifteen puzzle]]

[[fr:Taquin]]

[[he:חידת ה-15]]

[[ja:15パズル]]

[[nl:Schuifpuzzel]]

[[ru:Пятнашки]]

[[sl:Igra 15]]

[[sv:Femtonspel]]

[[te:పదిహేను-పజిల్]]

[[th:ปริศนา 15]]

[[zh:數字推盤遊戲]]