Joc la 15

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 septembrie 2021; verificările necesită 2 modificări .

Jocul 15 [1] [2] [3] , tag [4] [5] , luat [2] [5] [6]  este un joc popular de puzzle inventat în 1878 de Noah Chapman. Puzzle-ul este un set de 15 oase pătrate identice cu numere imprimate pe ele, aflate într-o cutie pătrată. Lungimea laturii cutiei este de patru ori mai mare decât lungimea laturii osului, astfel încât un câmp pătrat rămâne necompletat în casetă. Scopul jocului este aranjarea pieselor în ordine crescătoare, mutându-le în interiorul cutiei, de preferință cu cât mai puține mișcări.

Istorie

Autoritate

Din 1891 până la moartea sa , Samuel Loyd a susținut că el a fost cel care a inventat puzzle-ul și multă vreme s-a crezut că așa a fost într-adevăr [7] [8] . Cu toate acestea, există dovezi că el nu a fost implicat nici în crearea de jetoane 14 și 15 [9] [10] [11] [8] . Apogeul popularității puzzle-ului în Statele Unite a venit în prima jumătate a anului 1880; totuși, nicio mențiune despre Sam Loyd în legătură cu cei „cincisprezece” nu a fost găsită până în ianuarie 1891 [12] [10] . În special, The New York Times a publicat materiale despre puzzle de două ori, pe 22 martie 1880 și 11 iunie 1880, fără să-l menționeze o dată pe Loyd, în ciuda faptului că Loyd locuia la New York [13] .

Adevăratul inventator al puzzle-ului a fost Noah Palmer Chapman, un maestru de poștă din Canastota [14] [15] , care în 1874 le-a arătat prietenilor săi un puzzle format din șaisprezece pătrate numerotate care trebuiau puse în rânduri de câte patru, astfel încât suma numerele din fiecare rând erau egale cu 34 [16] .

Fiul lui Noah Chapman, Frank Chapman, a adus puzzle-urile finalizate la Syracuse, New York, și le-a dat lui Anna și James Belden [17] . Ei, la rândul lor, au dus puzzle-ul la Watch Hill, Rhode Island unde au fost făcute copii ale puzzle-ului [14] ; una dintre aceste copii a ajuns la Hartford [14] printr-o rută necunoscută , unde elevii de la Școala Americană pentru Deficienți de Auz au început să facă copii brute ale puzzle-ului [14] . Până în 1879, puzzle-ul era deja vândut nu numai în Hartford, ci și în Boston . Apoi, lucrătorul de lemn Matthias J. Rice a aflat despre „etichete”. În decembrie 1879, Matthias Rice a început o nouă afacere cu puzzle-uri în Boston numită The  Gem Puzzle [18] [ 19] [20] .

La începutul anului 1880, un anume Charles Pevey, un dentist din Worcester , a atras atenția publicului oferind o recompensă în bani pentru rezolvarea problemei de a pune cap la cap un puzzle, ceea ce a sporit popularitatea noului joc. În primăvara acelui an, jocul a ajuns în Europa .

La 21 februarie 1880, Noah Chapman a încercat să solicite un brevet pentru invenția sa sub denumirea de „Block Solitaire Puzzle” („Puzzle-solitaire cu blocuri”) [21] , dar cererea de brevet a fost respinsă; nu s-a păstrat nicio înregistrare care să explice de ce s-a întâmplat acest lucru [22] . Aparent, acest lucru s-a datorat faptului că, potrivit inspectorului de brevete Burke, noua cerere diferă puțin de brevetul [23] „Cunning Blocks”, „Puzzle-Blocks”, eliberat lui Ernest W. Kinsey (Ernest U. Kinsey). ) cu mai mult de un an înainte ca Noah Chapman să-și depună cererea [24] [25] .

Distribuție

În SUA

Pe 6 ianuarie 1880, Boston Evening Transcript a apărut un anunț pentru un puzzle numit Boss Puzzle . Pe 12 ianuarie, Boston Transcript a menționat mai multe versiuni de la terți, inclusiv Gem Puzzle , Solitaire , Fifteen și Number Puzzle . Pe 19 ianuarie, un puzzle numit The New Puzzle a fost anunțat în același ziar ; chiar a doua zi, Worcester Gazette a difuzat un anunț pentru The Boss Puzzle . Popularitatea puzzle-ului a crescut rapid, iar antreprenorii au început deja să-l producă și să-l vândă [26] .

Între 26 și 30 ianuarie, Boston Evening Transcript a publicat un anunț al lui Matthias Ries, enervat de apariția unor copii ale puzzle-ului. Anunțul spunea [27] :

Atenție la falsuri. Asigurați-vă că îl obțineți pe acesta și numai un puzzle atent creat și testat cu atenție.
Text original  (engleză) : 
Puzzle cu bijuteriile lui Rice. Marele Original. Atenție la imitații. Asigurați-vă că cereți acest lucru, singurul puzzle realizat cu precizie și de încredere de pe piață, și nu luați altul.

În februarie 1880, articole detaliate despre puzzle au început să apară în diferite ziare [28] . O serie de reviste naționale, inclusiv The Youth's Companion , Illustrated Newspaper , Harper's Weekly , Scientific American , The Independent , au făcut publicitate puzzle-ului timp de câteva săptămâni [29] . Vestea puzzle-ului s-a răspândit în alte orașe. Până la începutul lunii martie, mulți producători au lansat versiuni ale puzzle-ului sub diferite nume [19] .

Pe 12 februarie, Boston Herald a publicat o poezie despre puzzle, urmată de o serie de lucrări sub formă de versuri în alte lucrări 30] . Pe 17 februarie, ziarul Rochester Democrat and Chronicle a publicat un articol despre impactul puzzle-ului asupra societății. Pe 20 februarie, New York Ontario County Journal a publicat un articol care spunea după cum urmează [31] :

Probabil că N. P. Chapman, maestru de poștă al Canastotei, va fi cel mai blestemat om din țară în următoarele săptămâni. El a inventat Jocul la 15 ani.
Text original  (engleză) : 
Probabil NP Chapman, director de poștă din Canastota, NY, va fi, în următoarele câteva săptămâni, cel mai blestemat om din țară. El a inventat „Jocul celor 15”.

La 17 martie 1880, Boston Daily Advertiser a publicat un articol care descria „începutul nebuniei” la Boston în urmă cu trei luni (decembrie 1879) [28] .

Pe baza reclamelor și articolelor din ziare, autorii The 15 Puzzle Slocum și Zonneveld concluzionează că în majoritatea orașelor „nebunia” a durat una până la două luni; cu toate acestea, în multe orașe puzzle-ul a devenit popular înainte de publicarea în ziarele locale și a rămas popular chiar și atunci când publicarea a încetat [32] .

În afara SUA

În martie 1880, puzzle-ul a început să se răspândească în afara Statelor Unite. Până la sfârșitul lunii martie, a ajuns în Canada și Franța. În cursul lunii aprilie, „nebunia” a ajuns în Anglia, Germania, Letonia, Austria, Estonia, Norvegia, Suedia, Rusia, Finlanda, în luna mai – Noua Zeelandă, Olanda, Italia, Mexic, Danemarca, Australia [33] .

În Rusia

La 25 aprilie 1880, Sf. Petersburg Herold a postat un anunț în germană „Neues Spiel - Das Spiel der Funfzehn” [34] („Joc nou - Joc la 15”).

Sarcini

Puzzle-ul cu pietre prețioase

În The Gem Puzzle , realizat și vândut de Matthias Ries în 1879, jucătorul a golit plăci dintr-o cutie și le-a pus la întâmplare înapoi, după care a încercat să restabilească configurația ordonată [20] [10] :

Așezați blocurile în cutie aleatoriu, apoi mutați-le până când se aliniază în ordinea corectă.
Text original  (engleză) : 
Așezați blocurile în cutie neregulat, apoi mutați până în ordinea obișnuită.

În această versiune, problema s-a dovedit a fi de nerezolvat în exact jumătate din cazuri.

Puzzle 14-15

Într-o altă versiune, toate plăcile, cu excepția celor 14 și 15, sunt inițial la locul lor; sarcina este de a schimba piesele 14 și 15 plasate greșit. Această sarcină este de nerezolvat; totuși, în acest caz, puteți aranja plăcile cu o celulă goală în colțul din stânga sus, sau puteți alinia jetoanele în coloane [35] .

  • Orez. 1. În poziția de pornire în puzzle-ul 14-15, piesele 14 și 15 sunt schimbate

  • Orez. 2. Această locație nu este accesibilă de la locația de pornire a puzzle-ului 14-15 (Fig. 1)

  • Orez. 3. Dar această locație este realizabilă din locația de pornire a puzzle-ului 14-15 (Fig. 1)

  • Orez. 4. O altă locație realizabilă pentru puzzle-ul 14-15 (Fig. 1)

Modificări moderne

Au fost lansate numeroase variante ale puzzle-ului. În unele exemple de realizare, în loc de a ordona numere, scopul este de a restabili o anumită imagine. Literele pot fi folosite în loc de cifre; prezența a cel puțin două litere identice poate face ca rezolvarea puzzle-ului să fie o sarcină nebanală.

  • Elefantul doarme în picioare. Si tu?

  • În engleză ("Measure your mind, my friend") [8]

  • În germană („Fără muncă nu există recompensă”)

Piața Magică

Una dintre sarcini este de a rearanja plăcile în așa fel încât suma numerelor din fiecare rând (orizontală, verticală sau diagonală mare) să fie egală cu același număr ; în timp ce valoarea numerică a unei celule goale este considerată egală cu zero [36] [37] . În acest caz, suma magică este 30. Este nevoie de cel puțin 35 de mișcări pentru a obține pătratul magic din locația de pornire și există un singur pătrat magic care poate fi atins în 35 de mișcări [38] .

Descriere matematică

Se poate demonstra că exact jumătate din toate 20 922 789 888 000 (=16 ! ) poziții inițiale posibile ale etichetelor nu pot fi aduse la forma asamblată. Lasă o piesă cu un număr să fie amplasată înainte (dacă numărați de la stânga la dreapta și de sus în jos) plăci cu numere mai mici de ; atunci notăm . În special, dacă după o piesă cu un număr nu există piese cu numere mai mici de , atunci . De asemenea, introducem un număr  — numărul rândului celulei goale (numărând de la 1). Dacă suma

(adică suma numărului de perechi de oase în care osul cu un număr mai mare vine înaintea osului cu un număr mai mic și numărul rândului unei celule goale) este impară , atunci nu există o soluție pentru puzzle-ul [39] [3] .

Dacă permitem cutiei să se rotească cu 90 de grade, în care imaginile numerelor vor fi întinse pe o parte, atunci este posibilă transformarea combinațiilor nerezolvabile în combinații solubile (și invers). Astfel, dacă în loc de numere de pe articulații puneți puncte și nu fixați poziția cutiei, atunci nu vor exista combinații de nerezolvat deloc.

Soluție optimă

Pentru etichetele generalizate (cu mai mult de 15 piese), problema găsirii celei mai scurte soluții pentru o anumită configurație este NP-complet [40] [41] .

4  ×  4

Oricare dintre cele 10.461.394.944.000 de configurații rezolvabile ale puzzle-ului „clasic” 4  ×  4 poate fi convertită în cea inițială în cel mult 80 de mișcări, dacă prin mutare înțelegem mișcarea unei plăci [42] [43] [38] [44 ] , sau nu mai mult decât în ​​43 de mișcări, dacă prin mutare înțelegem mișcarea simultană a unui rând continuu de cel mult trei piese [45] . Doar 17 dintre toate configurațiile rezolvabile nu pot fi rezolvate în mai puțin de 80 de mișcări, adică necesită 80 de mișcări de plăci individuale pentru a rezolva [43] [38] [46] ; doar 16 configurații rezolvabile necesită 43 de mișcări de rânduri continue de plăci [45] .

5  ×  5

În 1995, s-a demonstrat că orice configurație a unui puzzle de 5  ×  5 poate fi rezolvată în cel mult 219 de mișcări simple [47] , adică s-a obținut o limită superioară de 219 de mișcări pentru lungimea soluției optime la o soluție arbitrară. configurație. În 1996, a fost găsită o configurație care nu poate fi rezolvată în mai puțin de 112 mișcări de țiglă [48] . În 2000, limita superioară a fost îmbunătățită la 210 mutări [49] ; în 2011, o  limită inferioară de 152 de mișcări și o limită superioară de 208 mutări au fost obținute pentru „ Numărul lui Dumnezeu ” al puzzle -ului 5  × 5 [44] .

Rezultatele curente

Tabelul rezumă datele pentru o serie de generalizări ale „etichetelor”. Când rezultatul exact nu este cunoscut, cele mai cunoscute limite inferioare și superioare sunt date sub forma lb - ub .

Marimea Configurație țintă Numărul
de configurații de rezolvat
Mișcări „lungi” [K 1] 		„ Numărul lui Dumnezeu ” Numărul
de „antipozi” [K 2]
2  ×  2 cutie goală în colț 12 Nu 6 [49] [50] 1 [49]
2  ×  3 cutie goală în colț 360 Nu 21 [49] [50] 1 [49]
2  ×  4 cutie goală în colț 20 160 Nu 36 [49] [50] 1 [49]
2  ×  5 cutie goală în colț 1 814 400 Nu 55 [51] [50] 2 [51]
2  ×  6 cutie goală în colț 239 500 800 Nu 80 [52] [50] 2 [52]
2  ×  7 cutie goală în colț 43 589 145 600 Nu 108 [53] [50]
2  ×  8 cutie goală în colț 10 461 394 944 000 Nu 140 [53] [50]
3  ×  3 cutie goală în colț 181 440 Nu 31 [49] [44] [50] 2 [49] [54]
da 24 [44]
3  ×  4 cutie goală în colț 239 500 800 Nu 53 [49] [50] 18 [49]
3  ×  5 cutie goală în colț 653 837 184 000 Nu 84 [50]
3  ×  5 celula goală în centru 653 837 184 000 Nu 84 [55]
4  ×  4 cutie goală în colț 10 461 394 944 000 Nu 80 [43] [38] [44] [50] 17 [43] [38] [46]
da 43 [45] 16 [45]
5  ×  5 cutie goală în colț 7,7556⋅10 24 Nu 152 [44]  - 208 [44]

Utilizarea etichetelor în informatică

„Fifteen” de diferite dimensiuni au fost utilizate în mod regulat în cercetarea AI încă din anii 1960 ; în special, ei testează și compară algoritmi de căutare în spațiul de stare cu diferite funcții euristice [56] [57] [58] [59] și alte optimizări care afectează numărul de configurații de puzzle (vârfurile graficului) vizitate în procesul de căutare. În studii, într-un fel sau altul, puzzle-uri de dimensiuni 3  ×  3 [60] [61] , 4  ×  4 [62] [63] [43] , 5  ×  5 [48] [64] [65] , 6  × S-au folosit  6 [66] , 2  ×  7 [55] , 3  ×  5 [55] .

Se pot enumera principalele motive pentru alegerea etichetelor ca „banc de testare” pentru algoritmii de căutare [67] [40] [68] :

  1. spațiul de stare al etichetelor clasice este accesibil pentru analiză, dar totuși suficient de mare pentru a fi de interes și pentru a utiliza și compara diverse euristici [69] ;
  2. nu este cunoscut niciun algoritm care să găsească cea mai scurtă soluție pentru n  ×  n etichete generalizate într-un timp rezonabil [40] ;
  3. însăși sarcina de a găsi cea mai scurtă soluție pentru etichete este ușor de înțeles și de manipulat programatic [56] [40] ; puzzle-ul este descris cu un set mic și bine definit de reguli simple [70] [40] ;
  4. Modelarea puzzle-ului nu necesită transferul subtilităților semantice inerente domeniilor mai complexe [71] ;
  5. problemele cu etichete sunt reprezentanți de succes ai clasei de probleme în care este necesar să se găsească calea cea mai scurtă între două vârfuri date ale unui graf finit nedirecționat [40] ;
  6. dimensiunea graficului de căutare depinde exponențial de dimensiunea puzzle-ului n , deși orice stare poate fi descrisă folosind memoria O ( n 2 ) [40] ;
  7. aceeași funcție euristică poate fi aplicată tuturor stărilor, deoarece toate stările sunt descrise în același mod; în aplicații reale, stări diferite pot avea descrieri diferite, ceea ce necesită introducerea mai multor euristici [72] ;
  8. utilizarea jocurilor și puzzle-urilor în cercetare nu ridică probleme financiare sau etice [71] .

Căutare euristică

Algoritmul A* , IDA* [73] , prima căutare pe lățime poate fi folosit ca algoritm de căutare .

Puzzle -ul 3  × 3  este ușor de rezolvat prin orice algoritm de căutare. Configurațiile arbitrare ale etichetelor 4  ×  4 sunt rezolvate folosind algoritmi moderni de căutare în câteva milisecunde [57] . Soluția optimă a puzzle-ului 5  ×  5 necesită mai multe resurse chiar și cu utilizarea computerelor moderne și a algoritmilor [57] [64] ; procesul de căutare poate dura câteva săptămâni și poate genera trilioane de noduri [65] [66] . Soluția optimă a configurațiilor arbitrare ale puzzle-ului 6  ×  6 este încă dincolo de posibilități [66] și, prin urmare, studiile încearcă doar să prezică performanța relativă a algoritmului IDA* cu diferite funcții euristice [66] .

Una dintre cele mai simple euristici pentru etichete poate fi exprimată după cum urmează [74] [75] [76] :

Numărul de mișcări necesare pentru rezolvare nu este mai mic decât numărul de piese care nu sunt la locul lor.

Corectitudinea enunțului, adică admisibilitatea funcției euristice „numărul de plăci care nu sunt la locurile lor”, rezultă din faptul că o singură plăci poate fi pusă la loc într-o singură mișcare. Această euristică nu folosește toate informațiile disponibile: de exemplu, nu ține cont de distanțele la care trebuie deplasate plăcile individuale.

O euristică mai inteligentă atribuie fiecărei locații de plăci suma distanțelor de la poziția curentă a fiecărei plăci la poziția sa țintă [77] . În literatură, această euristică se găsește sub denumirea „Manhattan distance” (Manhattan distance) [76] [78] . Valabilitatea funcției decurge din faptul că o singură piesă se mișcă pe mișcare, iar distanța dintre această piesă și poziția sa finală se modifică cu 1. Totuși, nici această euristică nu folosește toate informațiile disponibile, datorită faptului că în o poziție două plăci nu pot fi în același timp. Există versiuni mai informate ale „distanței Manhattan”, cum ar fi Conflictul Linear [58] .

 Euristica bazată pe baze de date cu modele [63] [64] [59] au fost dezvoltate pentru a găsi rapid soluția optimă pentru un puzzle 4  ×  4, precum și pentru a putea găsi soluția optimă pentru un puzzle 5  × 5 într-un mod rezonabil. timp . Astfel de euristici sunt, în esență, tabele precalculate și stocate în RAM, în care sunt codificate soluții optime pentru subsarcini; fiecare dintre subsarcini se rezumă la mutarea unui anumit grup de plăci în pozițiile țintă [63] . Aceste euristici pot fi aplicate și la Cubul Rubik și la alte puzzle-uri [64] .

Vezi și

Comentarii

  1. ↑ Coloana indică dacă mișcarea mai multor plăci în același timp, formând un rând continuu vertical sau orizontal, contează ca o singură mișcare.
  2. ↑ „Antipode” - configurații de puzzle care necesită cele mai multe mișcări pentru a fi rezolvate

Note

  1. ↑ Timp liber matematic, 1972 , p. 401.
  2. ↑ 1 2 Sarcini și experimente distractive, 1972 , p. 365.
  3. ↑ 1 2 Se joacă „15” . Componenta matematică . Studii matematice .
  4. ↑ Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 43, 114, 163, 166, 168, 181-182.
  5. ↑ 1 2 Nume „Fifteen” . TwistyPuzzles.RU.
  6. ↑ Vladimir Belov. Puzzle-uri de la o distanță apropiată. Partea 2 . Computerra (18 ianuarie 2000). Arhivat din original pe 28 noiembrie 2015.
  7. ↑ Cyclopedia of Puzzles , p. 235
  8. ↑ 1 2 3 Jaap Scherphuis. 14-15 puzzle / Boss puzzle . Pagina de puzzle a lui Jaap .
  9. ↑ The 15 Puzzle, 2006 .
  10. ↑ 1 2 3 Recenzie despre The 15 Puzzle de Aaron Archer , p. unu.
  11. ↑ Puzzle-uri pentru plăcere, 1994 , p. 10-12.
  12. ↑ Puzzle-ul celor 15, 2006 , p. 76.
  13. ↑ Puzzle-uri pentru plăcere, 1994 , p. unsprezece.
  14. ↑ 1 2 3 4 Puzzle-ul celor 15, 2006 , p. 109.
  15. ↑ Recenzie despre The 15 Puzzle de Aaron Archer , p. 13.
  16. ↑ Puzzle-ul celor 15, 2006 , p. 98-99.
  17. ↑ Puzzle-ul celor 15, 2006 , p. 103-104, 109.
  18. ↑ Puzzle-ul celor 15, 2006 , p. 11, 109.
  19. ↑ 1 2 Recenzie despre The 15 Puzzle de Aaron Archer , p. 2.
  20. ↑ 1 2 Jerry Slocum: Sam Loyd's Most Successful Hoax Arhivat 23 decembrie 2015 la Wayback Machine (PDF; 672 kB) . Vortrag auf: A șaptea adunare pentru Gardner, martie 2006, Convenția Asociației Colecționarilor de Jocuri și Puzzle. Publicat în: E. Pegg, A. H. Schoen & T. Rodgers: Homage to a Pied Puzzler. A.K. Peters, Wellesley/Massachusetts, 2009, S. 3-21. (vezi: S. 4)
  21. ↑ Puzzle-ul celor 15, 2006 , p. 100-101.
  22. ↑ Puzzle-ul celor 15, 2006 , p. 101.
  23. ↑ EU Kinsey. Blocuri de puzzle. Nu. 207124. Patentat Aug. 20, 1878 .
  24. ↑ Puzzle-ul celor 15, 2006 , p. 102.
  25. ↑ Recenzie despre The 15 Puzzle de Aaron Archer , p. 3.
  26. ↑ Puzzle-ul celor 15, 2006 , p. 14-15.
  27. ↑ Puzzle-ul celor 15, 2006 , p. 15-16.
  28. ↑ 1 2 Puzzle-ul celor 15, 2006 , p. 12.
  29. ↑ Puzzle-ul celor 15, 2006 , p. douăzeci.
  30. ↑ Puzzle-ul celor 15, 2006 , p. 21.
  31. ↑ Puzzle-ul celor 15, 2006 , p. 24, 98.
  32. ↑ Puzzle-ul celor 15, 2006 , p. 59.
  33. ↑ Puzzle-ul celor 15, 2006 , p. 60.
  34. ↑ Puzzle-ul celor 15, 2006 , p. 63.
  35. ↑ Sarcini și experimente distractive, 1972 , p. 370.
  36. ↑ Sarcini și experimente distractive, 1972 , p. 371.
  37. ↑ Sam Loyd; Martin Gardner: Puzzle-uri matematice ale lui Sam Loyd . Dover Pubs., New York 1959, pp. 19 și 20. Cărți Google
  38. ↑ 1 2 3 4 5 Herbert Kociemba. Fifteen Puzzle Optimal Solver . Arhivat din original pe 2 octombrie 2015.
  39. ↑ Slocum J., Weisstein EW 15 Puzzle  (engleză) pe site-ul Wolfram MathWorld .
  40. ↑ 1 2 3 4 5 6 7 Ratner D., Warmuth MK Găsirea celei mai scurte soluții pentru extensia N × N a 15-PUZZLE este insolubilă // Conferința națională privind inteligența artificială, 1986.
  41. ↑ Ratner D., Warmuth M. Puzzle -ul (n 2 −1) și problemele de relocare aferente  // Journal of Symbolic Computation. - 1990. - T. 10 , nr 2 . — p. 111–137 . - doi : 10.1016/S0747-7171(08)80001-6 .
  42. ↑ A. Brüngger, A. Marzetta, K. Fukuda și J. Nievergelt, The parallel search bench ZRAM and its applications , Annals of Operations Research 90 (1999), pp. 45-63.
  43. ↑ 1 2 3 4 5 Richard E. Korf, Peter Schultze. Căutare pe lățime paralelă la scară largă . — 2005.
  44. ↑ 1 2 3 4 5 6 7 Secvența OEIS A087725 : cel mai mare număr de mișcări de care ar putea fi nevoie pentru a generaliza  puzzle -ul n  × n 15
  45. ↑ 1 2 3 4 Bruce Norskog. Puzzle-ul Cincisprezece poate fi rezolvat în 43 de „mișcări” . Forumul Domeniului Cubului (8 decembrie 2010).
  46. ↑ 1 2 secvența OEIS A089484 : numărul de configurații de etichete a căror soluție optimă conține n mișcări
  47. ↑ Ralph Udo Gasser. Valorificarea resurselor de calcul pentru o căutare exhaustivă eficientă . — 1995.
  48. ↑ 1 2 Richard E. Korf, Larry A. Taylor. Găsirea soluțiilor optime pentru puzzle-ul celor douăzeci și patru . — 1996.
  49. ↑ 1 2 3 4 5 6 7 8 9 10 11 Filip RW Karlemo și Patric RJ Östergård On Sliding Block Puzzles , Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107
  50. ↑ 1 2 3 4 5 6 7 8 9 10 11 Secvența OEIS A151944 : cel mai mare număr de mișcări de care ar putea fi necesar să generalizeze un puzzle de m  ×  n cu 15 puzzle
  51. ↑ 1 2 Secvența A090036 în OEIS
  52. ↑ 1 2 Secvența A090167 în OEIS
  53. ↑ 1 2 Secvența A151943 în OEIS
  54. ↑ Secvența OEIS A089473 _
  55. ↑ 1 2 3 Richard E. Korf. Căutare la frontieră la lățime, cu detectarea întârziată a duplicaturilor . — 2004.
  56. ↑ 1 2 Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 114.
  57. ↑ 1 2 3 Inteligența artificială: o abordare modernă, 2006 , p. 118.
  58. ↑ 1 2 Generarea de euristici admisibile prin criticarea soluțiilor la modelele relaxate, 1985 .
  59. ↑ 1 2 F. Yang, J. Culberson, R. Holte, U. Zahavi și A. Felner A General Theory of Additive State Space Abstractions Arhivat 8 decembrie 2015 la Wayback Machine , volumul 32 (2008), paginile 631-662
  60. ↑ Alexander Reinfeld. Soluția completă a opt puzzle-ului și beneficiul ordonării nodurilor în IDA* . — 1993.
  61. ↑ Daniel R. Kunkle. Rezolvarea celor 8 puzzle într-un număr minim de mișcări: o aplicare a algoritmului A* . — 2001.
  62. ↑ Richard E. Korf. Depth-first Iterative-Deepening: O căutare optimă admisibilă în arbore . — 1985.
  63. ↑ 1 2 3 Joseph C. Culberson, Jonathan Schaeffer. Baze de date de modele . — 1998.
  64. ↑ 1 2 3 4 Richard E. Korf. Progrese recente în proiectarea și analiza funcțiilor euristice admisibile . — 2000.
  65. ↑ 1 2 Richard E. Korf, Ariel Felner. Euristică a bazei de date cu modele disjunse . — 2002.
  66. ↑ 1 2 3 4 Ariel Felner, Richard E. Korf, Sarit Hanan. Euristica bazei de date cu modele aditive . — 2004.
  67. ↑ Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 43, 114, 163.
  68. ↑ Generarea de euristici admisibile prin criticarea soluțiilor la modelele relaxate, 1985 , p. 3.
  69. ↑ Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 114, 163.
  70. ↑ Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 43, 163.
  71. ↑ 1 2 Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 43.
  72. ↑ Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 163.
  73. ↑ Borowski BS Optimal 8/15-Puzzle Solver . // Galeria de proiecte a lui Brian. Consultat la 29 iulie 2013. Arhivat din original la 17 august 2013.
  74. ↑ Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 156.
  75. ↑ Programare distractivă: Tutorial, 2005 , p. 171.
  76. ↑ 1 2 Generarea de euristici admisibile prin criticarea soluțiilor la modelele relaxate, 1985 , p. 4-5.
  77. ↑ Inteligența artificială: strategii și metode de rezolvare a problemelor complexe, 2003 , p. 157.
  78. ↑ Programare distractivă: Tutorial, 2005 , p. 173.

Literatură

Cărți
  • Gardner M. Timp liber matematic / Per. din engleza. Yu. A. Danilova . Ed. Da. A. Smorodinsky . — M .: Mir , 1972.
  • Perelman Ya. I. Sarcini și experimente distractive. - M . : Literatura pentru copii , 1972.
  • Jerry Slocum și Dic Sonneveld. Puzzle-ul 15. - 2006. - ISBN 1-890980-15-3 .
  • Szczepan Jelensky Pe urmele lui Pitagora: Matematică distractivă = Śladami Pitagorasa / Tradus din poloneză de G. F. Boyarskaya, B. V. Boyarsky și A. A. Yakushev. -M.:Detgiz, 1961. - S. 231-233.
  • Clarke BR Puzzle-uri pentru plăcere . - Cambridge University Press, 1994. - ISBN 0-521-46634-2 .
  • Luger, George F. Inteligența artificială : Structuri și strategii pentru rezolvarea problemelor complexe. - editia a 4-a. - Editura Williams, 2003. - 864 p. — ISBN 5-8459-0437-4 . — ISBN 978-5-845-90437-9 .
  • Stuart Russell, Peter Norvig . Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach. - Ed. a II-a. - M . : Editura „Williams”, 2006. - 1408 p. — ISBN 5-8459-0887-6 .
  • Mozgovoy M. V. Programare distractivă: Tutorial . - Sankt Petersburg. : Peter , 2005. - 208 p. - ISBN 5-94723-853-5 .
Articole

Link -uri

 Probleme NP-complete
Problema
de maximizare a stivuirii (ambalării)
teoria grafurilor
teoria multimelor
Probleme algoritmice
Jocuri de logică
și puzzle-uri