Hra v 15

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 3. září 2021; kontroly vyžadují 2 úpravy .

Hra 15 [1] [2] [3] , tag [4] [5] , převzato [2] [5] [6]  je populární logická hra , kterou v roce 1878 vymyslel Noah Chapman. Puzzle je sada 15 stejných čtvercových kostí s natištěnými čísly, které leží ve čtvercové krabici. Délka strany krabice je čtyřikrát větší než délka strany kosti, takže jedno čtvercové pole zůstane v krabici nevyplněné. Cílem hry je uspořádat dlaždice ve vzestupném pořadí jejich pohybem uvnitř krabice, nejlépe s co nejmenším počtem tahů.

Historie

Autorství

Od roku 1891 až do své smrti Samuel Loyd tvrdil, že to byl on, kdo vynalezl hlavolam, a dlouho se věřilo, že tomu tak skutečně bylo [7] [8] . Existují však důkazy, že se nepodílel ani na vytvoření čipů 14 a 15 [9] [10] [11] [8] . Vrchol popularity hlavolamu ve Spojených státech přišel v první polovině roku 1880; žádná zmínka o Samu Loydovi v souvislosti s „patnáctkou“ však nebyla nalezena až do ledna 1891 [12] [10] . Konkrétně The New York Times zveřejnil materiály o hádance dvakrát, 22. března 1880 a 11. června 1880, aniž by se jednou zmínil o Loydovi, a to navzdory skutečnosti, že Loyd žil v New Yorku [13] .

Skutečným vynálezcem hlavolamu byl Noah Palmer Chapman, poštmistr z Canastoty [14] [15] , který již v roce 1874 ukázal svým přátelům hlavolam sestávající z šestnácti očíslovaných čtverců, které bylo nutné poskládat do řad po čtyřech tak, aby součet čísla v každém řádku byla rovna 34 [16] .

Syn Noaha Chapmana, Frank Chapman, přinesl hotové hádanky do Syrakus v New Yorku a dal je Anně a Jamesi Beldenovým [17] . Oni zase vzali hádanku do Watch Hill, Rhode Island , kde byly vyrobeny kopie hádanky [14] ; jedna z těchto kopií se dostala neznámou cestou do Hartfordu [14] , kde studenti Americké školy pro sluchově postižené začali vytvářet hrubé kopie hádanky [14] . V roce 1879 se puzzle již prodávalo nejen v Hartfordu, ale také v Bostonu . Poté se o „značkách“ dozvěděl dřevozpracující dělník Matthias J. Rice. V prosinci 1879 zahájil Matthias Rice v Bostonu nový obchod s puzzle s názvem The  Gem Puzzle [18] [ 19] [20] .

Počátkem roku 1880 jistý Charles Pevey, worcesterský zubař , upoutal pozornost veřejnosti tím, že nabídl peněžní odměnu za vyřešení problému se složením puzzle, což přispělo k popularitě nové hry. Na jaře téhož roku se hra dostala do Evropy .

21. února 1880 se Noah Chapman pokusil požádat o patent na svůj vynález pod názvem „Block Solitaire Puzzle“ („Hádanka-solitaire s bloky“) [21] , ale přihláška patentu byla zamítnuta; nedochoval se žádný záznam vysvětlující, proč se tak stalo [22] . Zřejmě to bylo způsobeno tím, že podle patentového inspektora Burkea se nová přihláška jen málo lišila od patentu [23] "Cunning Blocks", "Puzzle-Blocks", vydaného Ernestu W. Kinseymu (Ernest U. Kinsey ) více než rok předtím, než Noah Chapman podal svou žádost [24] [25] .

Distribuce

V USA

6. ledna 1880 se Boston Evening Transcript objevila reklama na hádanku nazvanou Boss Puzzle . 12. ledna Bostonský přepis zmínil několik verzí třetích stran, včetně Gem Puzzle , Solitaire , Fifteen a Number Puzzle . 19. ledna byla ve stejných novinách oznámena hádanka s názvem The New Puzzle ; hned druhý den se ve Worcester Gazette objevila reklama na The Boss Puzzle . Obliba hlavolamu rychle rostla a podnikatelé jej již začali vyrábět a prodávat [26] .

Mezi 26. a 30. lednem Boston Evening Transcript zveřejnil oznámení Matthiase Riese, kterého rozčiluje výskyt kopií hádanky. V oznámení bylo uvedeno [27] :

Pozor na padělky. Ujistěte se, že získáte toto jediné a pouze pečlivě vytvořené, pečlivě testované puzzle.
Původní text  (anglicky) : 
Rice's Gem Puzzle. Velký originál. Pozor na imitace. Ujistěte se, že si vyžádáte toto, jediné přesně vyrobené, naprosto spolehlivé puzzle na trhu, a neberte si žádné jiné.

V únoru 1880 se začaly v různých novinách objevovat podrobné články o hlavolamu [28] . Řada národních časopisů, včetně The Youth's Companion , Illustrated Newspaper, Harper's Weekly , Scientific American , The Independent , inzerovala hádanku několik týdnů [29] . Zpráva o hádance se rozšířila do dalších měst. Začátkem března mnoho výrobců uvolňovalo verze skládačky pod různými jmény [19] .

12. února Boston Herald publikoval báseň o hlavolamu, po níž následovala řada prací ve formě veršů v jiných listech 30] . 17. února noviny Rochester Democrat and Chronicle zveřejnily článek o dopadu hádanky na společnost. 20. února publikoval New York Ontario County Journal článek, který zní takto [31] :

Pravděpodobně N. P. Chapman, poštmistr z Canastoty, bude v příštích týdnech nejprokletejším mužem v zemi. Hru vymyslel v 15 letech.
Původní text  (anglicky) : 
Pravděpodobně NP Chapman, poštmistr z Canastoty, NY, bude během nadcházejících několika týdnů nejsrdečněji prokletým mužem v zemi. Vynalezl 'Hru 15'.

17. března 1880 zveřejnil Boston Daily Advertiser článek, který popisoval „začátek šílenství“ v Bostonu před třemi měsíci (prosinec 1879) [28] .

Na základě novinových inzerátů a článků došli autoři The 15 Puzzle Slocum a Zonneveld k závěru, že ve většině měst „šílenství“ trvalo jeden až dva měsíce; nicméně, v mnoha městech hlavolam stal se populární před publikací v místních novinách a zůstal populární dokonce když publikace přestala [32] .

Mimo USA

V březnu 1880 se hádanka začala šířit mimo Spojené státy. Do konce března se dostala do Kanady a Francie. Během dubna zasáhlo „šílenství“ Anglii, Německo, Lotyšsko, Rakousko, Estonsko, Norsko, Švédsko, Rusko, Finsko, v květnu pak Nový Zéland, Holandsko, Itálie, Mexiko, Dánsko, Austrálie [33] .

V Rusku

Dne 25. dubna 1880 byl kostel sv. Petersburg Herold zveřejnil inzerát v němčině "Neues Spiel - Das Spiel der Funfzehn" [34] ("Nová hra - hra v 15").

Úkoly

The Gem Puzzle

Ve hře The Gem Puzzle , kterou vyrobil a prodal Matthias Ries v roce 1879, hráč vysypal destičky z krabice a náhodně je umístil zpět, načež se pokusil obnovit objednanou konfiguraci [20] [10] :

Umístěte bloky do krabice náhodně a poté je posouvejte, dokud se neseřadí ve správném pořadí.
Původní text  (anglicky) : 
Umístěte bloky do krabice nepravidelně a poté se pohybujte, dokud nebudou v pravidelném pořadí.

V této verzi se problém ukázal jako neřešitelný přesně v polovině případů.

Puzzle 14-15

V jiné verzi jsou všechny dlaždice kromě 14 a 15 zpočátku na svém místě; úkolem je prohodit špatně umístěné destičky 14 a 15. Tento úkol je neřešitelný; v tomto případě však můžete uspořádat dlaždice s prázdnou buňkou v levém horním rohu nebo seřadit žetony do sloupců [35] .

  • Rýže. 1. Na výchozí pozici v hádance 14-15 jsou destičky 14 a 15 prohozeny

  • Rýže. 2. Tato lokace není dosažitelná ze startovní lokace 14-15 (obr. 1)

  • Rýže. 3. Ale toto umístění je dosažitelné ze startovního místa puzzle 14-15 (obr. 1)

  • Rýže. 4. Další dosažitelné umístění pro puzzle 14-15 (obr. 1)

Moderní úpravy

Bylo vydáno mnoho variant skládačky. V některých provedeních je cílem namísto objednávacích čísel obnovit nějaký obraz. Místo číslic lze použít písmena; přítomnost alespoň dvou stejných písmen může udělat z vyřešení hádanky netriviální úkol.

  • Slon spí ve stoje. a ty?

  • V angličtině („Measure your mind, my friend“) [8]

  • V němčině („Bez práce není odměny“)

Magický čtverec

Jedním z úkolů je přeskupit dlaždice tak, aby součet čísel v každém řádku (horizontální, vertikální nebo velká úhlopříčka) byl roven stejnému číslu ; zatímco číselná hodnota prázdné buňky je považována za rovnou nule [36] [37] . V tomto případě je magický součet 30. Získání magického pole ze startovního místa trvá nejméně 35 tahů a existuje pouze jedno magické pole, kterého lze dosáhnout za 35 tahů [38] .

Matematický popis

Lze ukázat, že přesně polovinu ze všech možných 20 922 789 888 000 (=16 ! ) počátečních pozic tagů nelze přenést do sestavené podoby. Nechte dlaždici s číslem před (pokud počítáte zleva doprava a shora dolů) dlaždicemi s čísly menšími než ; pak označíme . Zejména pokud po dlaždici s číslem nejsou žádné dlaždice s čísly menšími než , pak . Dále zadáme číslo  — číslo řádku prázdné buňky (počítáno od 1). Pokud částka

(tj. součet počtu párů kostí, ve kterých kost s vyšším číslem předchází kosti s menším číslem, a počtu řady prázdné buňky) je lichý , pak neexistuje žádné řešení hádanka [39] [3] .

Pokud necháme o 90 stupňů otočit krabičku, ve které budou obrázky čísel ležet na boku, pak je možné neřešitelné kombinace převést na rozpustné (a naopak). Pokud tedy místo čísel na klouby dáte tečky a nefixujete polohu rámečku, nebudou vůbec žádné neřešitelné kombinace.

Optimální řešení

U zobecněných tagů (s více než 15 dlaždicemi) je problém najít nejkratší řešení pro danou konfiguraci NP-complete [40] [41] .

4  ×  4

Kteroukoli z 10 461 394 944 000 řešitelných konfigurací „klasického“ puzzle 4  ×  4 lze převést na výchozí maximálně za 80 tahů, pokud tahem rozumíme pohyb jedné dlaždice [42] [43] [38] [44 ] , nebo ne více než ve 43 tazích, pokud tahem rozumíme současný pohyb souvislé řady nejvýše tří dlaždic [45] . Pouze 17 ze všech řešitelných konfigurací nelze vyřešit za méně než 80 tahů, tj. jejich vyřešení vyžaduje 80 tahů jednotlivých dlaždic [43] [38] [46] ; pouze 16 řešitelných konfigurací vyžaduje 43 pohybů souvislých řad dlaždic [45] .

5  ×  5

V roce 1995 se ukázalo, že jakoukoli konfiguraci hlavolamu 5  ×  5 lze vyřešit nanejvýš 219 jednotlivými tahy [47] , to znamená, že byla získána horní hranice 219 tahů pro délku optimálního řešení libovolného konfigurace. V roce 1996 byla nalezena konfigurace, kterou nelze vyřešit za méně než 112 tahů dlaždicemi [48] . V roce 2000 byla horní hranice vylepšena na 210 tahů [49] ; v roce 2011  byla získána dolní hranice 152 tahů a horní hranice 208 tahů pro „ Boží číslo “ hádanky 5  × 5 [44] .

Aktuální výsledky

Tabulka shrnuje data pro řadu zobecnění „tagů“. Pokud není znám přesný výsledek, nejznámější dolní a horní hranice jsou uvedeny ve tvaru lb - ub .

Velikost Cílová konfigurace Počet
konfigurací k řešení		 "Dlouhé"
pohyby [K 1] 		" Boží číslo " Počet
"antipodů" [K 2]
2  ×  2 prázdná krabice v rohu 12 Ne 6 [49] [50] 1 [49]
2  ×  3 prázdná krabice v rohu 360 Ne 21 [49] [50] 1 [49]
2  ×  4 prázdná krabice v rohu 20 160 Ne 36 [49] [50] 1 [49]
2  ×  5 prázdná krabice v rohu 1 814 400 Ne 55 [51] [50] 2 [51]
2  ×  6 prázdná krabice v rohu 239 500 800 Ne 80 [52] [50] 2 [52]
2  ×  7 prázdná krabice v rohu 43 589 145 600 Ne 108 [53] [50]
2  ×  8 prázdná krabice v rohu 10 461 394 944 000 Ne 140 [53] [50]
3  ×  3 prázdná krabice v rohu 181 440 Ne 31 [49] [44] [50] 2 [49] [54]
Ano 24 [44]
3  ×  4 prázdná krabice v rohu 239 500 800 Ne 53 [49] [50] 18 [49]
3  ×  5 prázdná krabice v rohu 653 837 184 000 Ne 84 [50]
3  ×  5 prázdná buňka uprostřed 653 837 184 000 Ne 84 [55]
4  ×  4 prázdná krabice v rohu 10 461 394 944 000 Ne 80 [43] [38] [44] [50] 17 [43] [38] [46]
Ano 43 [45] 16 [45]
5  ×  5 prázdná krabice v rohu 7,7556⋅10 24 Ne 152 [44]  - 208 [44]

Použití značek v informatice

"Patnáctky" různých velikostí byly pravidelně používány ve výzkumu AI od 60. let 20. století ; zejména testují a porovnávají vyhledávací algoritmy ve stavovém prostoru s různými heuristickými funkcemi [56] [57] [58] [59] a dalšími optimalizacemi, které ovlivňují počet konfigurací hádanek (vrcholů grafu) navštívených v procesu vyhledávání. Ve studiích, tak či onak, hádanky o velikostech 3  ×  3 [60] [61] , 4  ×  4 [62] [63] [43] , 5  ×  5 [48] [64] [65] , 6  × Bylo použito  6 [66] , 2  ×  7 [55] , 3  ×  5 [55] .

Je možné vyjmenovat hlavní důvody pro výběr tagů jako "testovací základny" pro vyhledávací algoritmy [67] [40] [68] :

  1. stavový prostor klasických značek je přístupný pro analýzu, ale stále dostatečně velký, aby byl zajímavý a aby bylo možné používat a porovnávat různé heuristiky [69] ;
  2. není znám žádný algoritmus, který by našel nejkratší řešení pro zobecněné n  ×  n tagy v rozumném čase [40] ;
  3. samotný úkol najít nejkratší řešení pro značky je snadno pochopitelný a programově manipulovatelný [56] [40] ; hádanka je popsatelná pomocí malého a dobře definovaného souboru jednoduchých pravidel [70] [40] ;
  4. modelování hlavolamů nevyžaduje přenos sémantických jemností, které jsou vlastní složitějším oborům [71] ;
  5. problémy s tagy jsou úspěšnými reprezentanty třídy problémů, ve kterých je potřeba najít nejkratší cestu mezi dvěma danými vrcholy neorientovaného konečného grafu [40] ;
  6. velikost vyhledávacího grafu závisí exponenciálně na velikosti hlavolamu n , i když jakýkoli stav lze popsat pomocí paměti O ( n 2 ) [40] ;
  7. stejnou heuristickou funkci lze aplikovat na všechny stavy, protože všechny stavy jsou popsány stejným způsobem; v reálných aplikacích mohou mít různé stavy různé popisy, což vyžaduje zavedení několika heuristik [72] ;
  8. používání her a hádanek ve výzkumu nevyvolává finanční ani etické problémy [71] .

Heuristické vyhledávání

Algoritmus A* , IDA* [73] , prohledávání šířky lze použít jako vyhledávací algoritmus .

Hádanka 3  × 3  je snadno vyřešena jakýmkoli vyhledávacím algoritmem. Libovolné konfigurace 4  ×  4 tagů jsou řešeny pomocí moderních vyhledávacích algoritmů během několika milisekund [57] . Optimální řešení hlavolamu 5  ×  5 vyžaduje více prostředků i při použití moderních počítačů a algoritmů [57] [64] ; proces vyhledávání může trvat několik týdnů a generovat biliony uzlů [65] [66] . Optimální řešení libovolných konfigurací hlavolamu 6  ×  6 je stále mimo možnosti [66] , a proto se studie snaží pouze předpovědět relativní výkon algoritmu IDA* s různými heuristickými funkcemi [66] .

Jedna z nejjednodušších heuristik pro značky může být vyjádřena následovně [74] [75] [76] :

Počet tahů potřebných k vyřešení není menší než počet destiček, které nejsou na svém místě.

Správnost tvrzení, tedy přípustnost heuristické funkce „počet destiček, které nejsou na svých místech“, vyplývá z toho, že jedním tahem lze položit pouze jednu destičku. Tato heuristika nevyužívá všechny dostupné informace: například nebere v úvahu vzdálenosti, o které se musí jednotlivé dlaždice posunout.

Chytřejší heuristika přiřadí každému umístění dlaždice součet vzdáleností od aktuální pozice každé dlaždice k cílové poloze [77] . V literatuře se tato heuristika nachází pod názvem „Manhattan distance“ (Manhattan distance) [76] [78] . Platnost funkce vyplývá ze skutečnosti, že za tah se pohne pouze jedna figurka a vzdálenost mezi touto figurkou a její konečnou polohou se změní o 1. Tato heuristika však také nevyužívá všechny dostupné informace, protože v jedna pozice dvě dlaždice nemohou být současně. Existují informovanější verze „manhattanské vzdálenosti“, jako je lineární konflikt [58] .

 Heuristika založená na databázích vzorů [63] [64] [59] byla vyvinuta tak, aby rychle nalezla optimální řešení hádanky 4  ×  4 a také aby bylo možné najít optimální řešení hádanky 5  × 5 za rozumnou cenu. čas . Takové heuristiky jsou v podstatě tabulky předem vypočítané a uložené v paměti RAM, ve kterých jsou zakódována optimální řešení dílčích úloh; každý z dílčích úkolů se scvrkává na přesun určité skupiny dlaždic na cílové pozice [63] . Tyto heuristiky lze také aplikovat na Rubikovu kostku a další hádanky [64] .

Viz také

Komentáře

  1. ↑ Sloupec udává, zda se pohyb několika dlaždic současně, tvořících souvislou vertikální nebo horizontální řadu, počítá jako jeden pohyb.
  2. ↑ "Antipodes" - puzzle konfigurace, které vyžadují nejvíce tahů k vyřešení

Poznámky

  1. ↑ Matematický volný čas, 1972 , s. 401.
  2. ↑ 1 2 Zábavné úkoly a pokusy, 1972 , str. 365.
  3. ↑ 1 2 Přehrávání "15" . Matematická složka . Matematické studie .
  4. ↑ Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 43, 114, 163, 166, 168, 181-182.
  5. ↑ 1 2 Název "Patnáct" . TwistyPuzzles.RU.
  6. ↑ Vladimír Bělov. Hádanky z blízké vzdálenosti. Část 2 . Computerra (18. ledna 2000). Archivováno z originálu 28. listopadu 2015.
  7. ↑ Cyklopedie hlavolamů , str. 235
  8. ↑ 1 2 3 Jaap Scherphuis. 14-15 puzzle / Boss puzzle . Jaapova puzzle stránka .
  9. ↑ The 15 Puzzle, 2006 .
  10. ↑ 1 2 3 Recenze The 15 Puzzle od Aarona Archera , str. jeden.
  11. ↑ Hádanky pro radost, 1994 , str. 10-12.
  12. ↑ The 15 Puzzle, 2006 , str. 76.
  13. ↑ Hádanky pro radost, 1994 , str. jedenáct.
  14. ↑ 1 2 3 4 The 15 Puzzle, 2006 , s. 109.
  15. ↑ Recenze knihy The 15 Puzzle od Aarona Archera , str. 13.
  16. ↑ The 15 Puzzle, 2006 , str. 98-99.
  17. ↑ The 15 Puzzle, 2006 , str. 103-104, 109.
  18. ↑ The 15 Puzzle, 2006 , str. 11, 109.
  19. ↑ 1 2 Recenze The 15 Puzzle od Aarona Archera , str. 2.
  20. ↑ 1 2 Jerry Slocum: Nejúspěšnější hoax Sama Loyda Archivováno 23. prosince 2015 na Wayback Machine (PDF; 672 kB) . Vortrag auf: Seventh Gathering for Gardner, březen 2006, Konvence Asociace sběratelů her a hlavolamů. Publikováno v: E. Pegg, A. H. Schoen & T. Rodgers: Pocta strakatým hlavolamům. A. K. Peters, Wellesley/Massachusetts, 2009, S. 3-21. (hier: S. 4)
  21. ↑ The 15 Puzzle, 2006 , str. 100-101.
  22. ↑ The 15 Puzzle, 2006 , str. 101.
  23. ↑ EU Kinsey. Puzzle bloky. Ne. 207124. Patentováno Aug. 20, 1878 .
  24. ↑ The 15 Puzzle, 2006 , str. 102.
  25. ↑ Recenze knihy The 15 Puzzle od Aarona Archera , str. 3.
  26. ↑ The 15 Puzzle, 2006 , str. 14-15.
  27. ↑ The 15 Puzzle, 2006 , str. 15-16.
  28. ↑ 1 2 The 15 Puzzle, 2006 , str. 12.
  29. ↑ The 15 Puzzle, 2006 , str. dvacet.
  30. ↑ The 15 Puzzle, 2006 , str. 21.
  31. ↑ The 15 Puzzle, 2006 , str. 24, 98.
  32. ↑ The 15 Puzzle, 2006 , str. 59.
  33. ↑ The 15 Puzzle, 2006 , str. 60.
  34. ↑ The 15 Puzzle, 2006 , str. 63.
  35. ↑ Zábavné úkoly a pokusy, 1972 , str. 370.
  36. ↑ Zábavné úkoly a pokusy, 1972 , str. 371.
  37. ↑ Sam Loyd; Martin Gardner: Matematické hádanky Sama Loyda . Dover Pubs., New York 1959, pp. 19 a 20. Google knihy
  38. ↑ 1 2 3 4 5 Herbert Kociemba. Patnáct Puzzle Optimální řešitel . Archivováno z originálu 2. října 2015.
  39. ↑ Slocum J., Weisstein EW 15 Puzzle  (anglicky) na webu Wolfram MathWorld .
  40. ↑ 1 2 3 4 5 6 7 Ratner D., Warmuth MK Nalezení nejkratšího řešení pro N × N prodloužení 15-PUZZLE je nezvládnutelné // Národní konference o umělé inteligenci, 1986.
  41. ↑ Ratner D., Warmuth M. The (n 2 −1)-puzzle and related relocation problems  // Journal of Symbolic Computation. - 1990. - T. 10 , č. 2 . — s. 111–137 . - doi : 10.1016/S0747-7171(08)80001-6 .
  42. ↑ A. Brüngger, A. Marzetta, K. Fukuda a J. Nievergelt, Paralelní vyhledávací lavice ZRAM a její aplikace , Annals of Operations Research 90 (1999), s. 45-63.
  43. ↑ 1 2 3 4 5 Richard E. Korf, Peter Schultze. Paralelní vyhledávání ve velkém měřítku . — 2005.
  44. ↑ 1 2 3 4 5 6 7 Sekvence OEIS A087725 : největší počet tahů, který může trvat zobecnění hádanky n  ×  n 15
  45. ↑ 1 2 3 4 Bruce Norskog. Puzzle Patnáct lze vyřešit ve 43 "tahech" . Doména fóra Cube (8. prosince 2010).
  46. ↑ 1 2 OEIS sekvence A089484 : počet konfigurací tagů , jejichž optimální řešení obsahuje n tahů
  47. ↑ Ralph Udo Gasser. Využití výpočetních zdrojů pro efektivní vyčerpávající vyhledávání . — 1995.
  48. ↑ 1 2 Richard E. Korf, Larry A. Taylor. Hledání optimálních řešení hádanky 24 . — 1996.
  49. ↑ 1 2 3 4 5 6 7 8 9 10 11 Filip RW Karlemo a 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 sekvence OEIS A151944 : největší počet tahů, který může trvat zobecnění m  ×  n 15-puzzlové hádanky
  51. ↑ 1 2 Sekvence A090036 v OEIS
  52. ↑ 1 2 Sekvence A090167 v OEIS
  53. ↑ 1 2 Sekvence A151943 v OEIS
  54. ↑ OEIS sekvence A089473 _
  55. ↑ 1 2 3 Richard E. Korf. Hledání na hranici šířky se zpožděnou detekcí duplicit . — 2004.
  56. ↑ 1 2 Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 114.
  57. ↑ 1 2 3 Umělá inteligence: moderní přístup, 2006 , str. 118.
  58. ↑ 1 2 Generování přípustné heuristiky kritikou řešení uvolněných modelů, 1985 .
  59. ↑ 1 2 F. Yang, J. Culberson, R. Holte, U. Zahavi a A. Felner Obecná teorie aditivních stavových prostorových abstrakcí Archivováno 8. prosince 2015 ve Wayback Machine , svazek 32 (2008), strany 631-662
  60. ↑ Alexander Reinfeld. Kompletní řešení osmičky a výhoda řazení uzlů v IDA* . — 1993.
  61. ↑ Daniel R. Kunkle. Řešení 8 hlavolamů v minimálním počtu tahů: Aplikace algoritmu A* . — 2001.
  62. ↑ Richard E. Korf. Iterativní prohlubování do hloubky: Optimální přípustné stromové vyhledávání . — 1985.
  63. ↑ 1 2 3 Joseph C. Culberson, Jonathan Schaeffer. Databáze vzorů . — 1998.
  64. ↑ 1 2 3 4 Richard E. Korf. Nedávný pokrok v návrhu a analýze přípustných heuristických funkcí . — 2000.
  65. ↑ 1 2 Richard E. Korf, Ariel Felner. Heuristika databáze nesouvislých vzorů . — 2002.
  66. ↑ 1 2 3 4 Ariel Felner, Richard E. Korf, Sarit Hanan. Heuristika databáze aditivních vzorů . — 2004.
  67. ↑ Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 43, 114, 163.
  68. ↑ Generování přípustné heuristiky kritikou řešení uvolněných modelů, 1985 , str. 3.
  69. ↑ Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 114, 163.
  70. ↑ Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 43, 163.
  71. ↑ 1 2 Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 43.
  72. ↑ Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 163.
  73. ↑ Borowski BS Optimal 8/15-Puzzle Solver . // Galerie Brianových projektů. Získáno 29. července 2013. Archivováno z originálu 17. srpna 2013.
  74. ↑ Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 156.
  75. ↑ Zábavné programování: Tutorial, 2005 , str. 171.
  76. ↑ 1 2 Generování přípustné heuristiky kritikou řešení uvolněných modelů, 1985 , str. 4-5.
  77. ↑ Umělá inteligence: strategie a metody řešení složitých problémů, 2003 , str. 157.
  78. ↑ Zábavné programování: Tutorial, 2005 , str. 173.

Literatura

knihy
  • Gardner M. Matematický volný čas / Per. z angličtiny. Yu.A. Danilova . Ed. Ano, A. Smorodinsky . — M .: Mir , 1972.
  • Perelman Ya. I. Zábavné úkoly a experimenty. - M .: Dětská literatura , 1972.
  • Jerry Slocum a Dic Sonneveld. Puzzle 15. - 2006. - ISBN 1-890980-15-3 .
  • Szczepan Jelensky Po stopách Pythagora: Zábavná matematika = Śladami Pitagorasa / Z polštiny přeložili G. F. Boyarskaya, B. V. Boyarsky a A. A. Yakushev. -M.:Detgiz, 1961. - S. 231-233.
  • Clarke BR Puzzle pro radost . - Cambridge University Press, 1994. - ISBN 0-521-46634-2 .
  • Luger, George F. Umělá inteligence: Struktury a strategie pro komplexní řešení problémů. - 4. vydání. - Williams Publishing House, 2003. - 864 s. — ISBN 5-8459-0437-4 . — ISBN 978-5-845-90437-9 .
  • Stuart Russell, Peter Norvig . Umělá inteligence: Moderní přístup = Artificial Intelligence: A Modern Approach. - 2. vyd. - M. : Nakladatelství "Williams", 2006. - 1408 s. — ISBN 5-8459-0887-6 .
  • Mozgovoy M. V. Zábavné programování: Tutoriál . - Petrohrad. : Peter , 2005. - 208 s. - ISBN 5-94723-853-5 .
články

Odkazy

 NP-úplné problémy
Maximalizační problém
stohování (balení)
teorie grafů
teorie množin
Algoritmické problémy
Logické hry
a hádanky