Joc de cincisprezece

Jocul celor cincisprezece s-a rezolvat

Jocul celor cincisprezece este un joc clasic de puzzle creat în 1874 de Noyes Palmer Chapman ^[1] , un poștaș care slujea în Canastota și popularizat în 1880 de Samuel Loyd . Jocul este format dintr-o masă în formă de pătrat, de obicei din plastic , împărțită în patru rânduri și patru coloane (deci 16 poziții), pe care sunt așezate 15 dale pătrate, numerotate progresiv începând de la 1. Dale pot derula orizontal sau vertical, dar deplasarea lor este evident limitată de existența unui singur spațiu gol. Scopul jocului este de a rearanja dale după ce le-a „amestecat” aleatoriu (poziția de atins este cea cu numărul 1 în stânga sus și celelalte numere care urmează de la stânga la dreapta și de sus în jos, până la 15 urmată de caseta goală).

Jocul celor cincisprezece (adesea generalizat în versiunea a n-a) este o problemă clasică cu care sunt explicați algoritmii bazați pe euristică . Printre euristicile utilizate în mod obișnuit pentru această problemă avem numărul de plăci prost poziționate (al căror model matematic tipic este distanța Hamming ) și suma distanțelor Manhattan între fiecare placă și poziția corectă a acesteia. ^[2] Ambele euristici sunt admisibile (adică nu supraestimează numărul de mișcări lipsă), prin urmare permit rezolvarea problemei într-un mod optim pentru unii algoritmi precum A *. ^[2]

fundal

Loyd a descris pentru prima oară cele cincisprezece puzzle-uri din Ciclopedia lui Sam Loyd a 5000 de puzzle-uri, trucuri și enigme , publicat postum în 1914 de fiul său (tot Samuel Loyd). Jocul a avut imediat succes, contribuind la faima inventatorului său, deja un renumit jucător de puzzle și autor al altor jocuri de succes.

Loyd a dat suma de o mie de dolari ca premiu pentru cei care au reușit să rezolve o versiune a jocului începând de la o poziție identică cu cea finală, dar cu numerele 14 și 15 schimbate. Un premiu pe care nimeni nu l-ar putea pretinde vreodată, deoarece, așa cum autorul știa foarte bine, soluția jocului pornind de la o astfel de configurație este matematic imposibilă.

Jocul de cincisprezece este considerat acum un solitaire clasic, așa-numita harpă sau puzzle . A fost comercializat de multe edituri și în multe variante. Multe ediții combină ideea originală cu cea a puzzle - ului , distribuind un design pe plăci care reapare corect numai atunci când au fost rearanjate corect. Există, de asemenea, variante cu un număr diferit de pătrate (și, prin urmare, de dale). Multe versiuni de software sunt disponibile pentru computerele personale .

Analiza matematică a soluției

O generalizare naturală a jocului de cincisprezece este un puzzle de $(n\times n)-1$ ${\ displaystyle (n \ times n) -1}$ ${\ displaystyle (n \ times n) -1}$ pe un grătar $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ . Pentru a determina dacă începeți de la o configurație dată $C1$ ${\ displaystyle C1}$ ${\ displaystyle C1}$ se poate ajunge la altul $C2$ ${\ displaystyle C2}$ ${\ displaystyle C2}$ este necesar să se calculeze permutările numerelor de pe casete (în ordinea citirii): numărul de inversiuni (perechi neordonate) trebuie să fie par.

Notă

^ Jerry Slocum și Dic Sonneveld, The 15 Puzzle , 2006. ISBN 1-890980-15-3
^ ^a ^b ( EN ) Richard E. Korf,Progrese recente în proiectarea și analiza funcțiilor euristice admisibile ( PDF ), în Progres recent în proiectarea și analiza funcțiilor euristice admisibile , SARA 2000. Abstracție, reformulare și aproximare: a 4-a simpozion internațional, Texas, SUA. LNCS 1864, voi. 1864, Springer, 2000, pp. 45–55, DOI : 10.1007 / 3-540-44914-0_3 , ISBN 978-3-540-67839-7 . Adus la 26 aprilie 2010 .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre Game of Fifteen

linkuri externe

Jocul celor 15 (versiune educațională)
O versiune iPhone / iPod touch , la itunes.apple.com .
O versiune pentru Android , pe play.google.com .

[1] Jerry Slocum și Dic Sonneveld, The 15 Puzzle , 2006. ISBN 1-890980-15-3

[Korf,2000-2] ( EN ) Richard E. Korf,Progrese recente în proiectarea și analiza funcțiilor euristice admisibile ( PDF ), în Progres recent în proiectarea și analiza funcțiilor euristice admisibile , SARA 2000. Abstracție, reformulare și aproximare: a 4-a simpozion internațional, Texas, SUA. LNCS 1864, voi. 1864, Springer, 2000, pp. 45–55, DOI : 10.1007 / 3-540-44914-0_3 , ISBN 978-3-540-67839-7 . Adus la 26 aprilie 2010 .

[1]

[2]