A meccs 15-kor

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. szeptember 3-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A 15 [1] [2] [3] , tag [4] [5] , [2] [5] [6] játék  egy népszerű kirakós játék , amelyet 1878 -ban Noah Chapman talált fel . A kirakós játék 15 egyforma négyzet alakú csontból áll, amelyekre számok vannak nyomtatva, négyzet alakú dobozban. A doboz oldalának hossza négyszerese a csont oldalának, így egy négyzetes mező kitöltetlenül marad a dobozban. A játék célja a lapkák növekvő sorrendbe helyezése a dobozon belüli mozgatással, lehetőleg a lehető legkevesebb mozdulattal.

Történelem

Szerzőség

1891 -től haláláig Samuel Loyd azt állította, hogy ő találta fel a rejtvényt, és sokáig azt hitték, hogy ez valóban így van [7] [8] . Azonban bizonyíték van arra, hogy nem vett részt sem a 14, sem a 15 zseton létrehozásában [9] [10] [11] [8] . A rejtvény népszerűségének csúcsa az Egyesült Államokban 1880 első felében volt; a "tizenötökkel" kapcsolatban azonban Sam Loydról 1891 januárjáig nem találtak említést [12] [10] . A The New York Times különösen kétszer publikált anyagokat a rejtvényről, 1880. március 22-én és 1880. június 11-én, anélkül, hogy egyszer is megemlítette volna Loydot, annak ellenére, hogy Loyd New Yorkban élt [13] .

A rejtvény igazi feltalálója Noah Palmer Chapman, egy canastotai postamester [ 14] [15] volt, aki még 1874-ben mutatott meg barátainak egy tizenhat számozott négyzetből álló rejtvényt, amelyet négyes sorokba kellett rakni, hogy a a számok minden sorban 34-gyel voltak egyenlők [16] .

Noah Chapman fia, Frank Chapman az elkészült rejtvényeket a New York állambeli Syracuse-ba hozta, majd Anna és James Beldennek adta [17] . Ők viszont elvitték a rejtvényt a Rhode Island állambeli Watch Hillbe , ahol a rejtvény másolatait készítettek [14] ; az egyik példány egy ismeretlen útvonalon Hartfordba [14] került , ahol az Amerikai Hallássérültek Iskolája diákjai elkezdték durva másolatokat készíteni a rejtvényről [14] . 1879-ben a puzzle-t már nemcsak Hartfordban, hanem Bostonban is árulták . Aztán Matthias J. Rice famunkás megismerte a „címkéket”. 1879 decemberében Matthias Rice új rejtvényüzletet indított Bostonban, The  Gem Puzzle [18] [ 19] [20] néven .

1880 elején egy bizonyos Charles Pevey, egy worcesteri fogorvos felkeltette a közvélemény figyelmét azzal, hogy pénzjutalmat ajánlott fel egy rejtvény összeállításának problémájának megoldásáért, ami növelte az új játék népszerűségét. Az év tavaszán a játék elérte Európát .

1880. február 21-én Noah Chapman "Block Solitaire Puzzle" ("Puzzle-Solitaire with blocks") [21] néven próbált szabadalmat kérni találmányára , de a szabadalmi kérelmet elutasították; nem maradt fenn feljegyzés, amely megmagyarázná, miért történt ez [22] . Nyilvánvalóan ez annak volt köszönhető, hogy Burke szabadalmi felügyelő szerint az új bejelentés alig különbözött az Ernest W. Kinsey (Ernest U. Kinsey) által kiadott "Cunning Blocks", "Puzzle-Blocks" szabadalomtól [23] . ) több mint egy évvel azelőtt, hogy Noah Chapman benyújtotta kérelmét [24] [25] .

Elosztás

Az Egyesült Államokban

1880. január 6-án a Boston Evening Transcript megjelent egy hirdetés a Boss Puzzle nevű rejtvényről . Január 12-én a Boston Transcript több harmadik féltől származó verziót említett, köztük a Gem Puzzle -t , a Solitaire -t , a Fifteen -t és a Number Puzzle -t . Január 19-én ugyanebben az újságban bejelentették az Új rejtvény című rejtvényt ; másnap a Worcester Gazette megjelentette a The Boss Puzzle hirdetését . A rejtvény népszerűsége gyorsan nőtt, és a vállalkozók már elkezdték gyártani és értékesíteni [26] .

Január 26. és 30. között a Boston Evening Transcript közzétette Matthias Ries bejelentését, akit bosszantott a rejtvény másolatainak megjelenése. A közlemény szerint [27] :

Óvakodj a hamisítványoktól. Győződjön meg róla, hogy ezt az egy és csak gondosan kidolgozott, gondosan tesztelt puzzle-t szerezze be.
Eredeti szöveg  (angol) : 
Rice's Gem Puzzle. A Nagy Eredeti. Óvakodj az utánzatoktól. Ügyeljen arra, hogy ezt kérje, az egyetlen pontosan elkészített, teljesen megbízható Puzzle-t a piacon, és ne vegyen mást.

1880 februárjában a rejtvényről részletes cikkek kezdtek megjelenni különböző újságokban [28] . Számos országos folyóirat, köztük a The Youth's Companion , az Illustrated Newspaper, a Harper's Weekly , a Scientific American , a The Independent hirdette a rejtvényt több héten keresztül [29] . A rejtvény híre más városokba is eljutott. Március elejére sok gyártó különböző néven adta ki a rejtvény verzióit [19] .

Február 12-én a Boston Herald közölt egy verset a rejtvényről, majd számos mű követte verses formában más lapokban 30] . Február 17-én a Rochester Democrat and Chronicle újság közölt egy cikket a rejtvény társadalomra gyakorolt ​​hatásáról. Február 20-án a New York Ontario County Journal egy cikket közölt, amely a következőképpen szól [31] :

Valószínűleg N. P. Chapman, Canastota postafőnöke lesz az ország legátkozottabb embere a következő hetekben. 15 évesen feltalálta a játékot.
Eredeti szöveg  (angol) : 
Valószínűleg NP Chapman, a New York állambeli Canastota postafőnöke lesz az elkövetkező néhány hétben a legszívesebben átkozott ember az országban. Ő találta fel a „15 játékát”.

1880. március 17-én a Boston Daily Advertiser közzétett egy cikket, amely a három hónappal ezelőtti bostoni "őrület kezdetét" írta le (1879. december) [28] .

Újsághirdetések és cikkek alapján a The 15 Puzzle szerzői, Slocum és Zonneveld arra a következtetésre jutottak, hogy a legtöbb városban az „őrület” egy-két hónapig tartott; azonban sok városban a feladvány népszerűvé vált a helyi újságokban való megjelenés előtt, és népszerű maradt a megjelenés megszűnésekor is [32] .

Az Egyesült Államokon kívül

1880 márciusában a rejtvény kezdett elterjedni az Egyesült Államokon kívül. Március végéig elérte Kanadát és Franciaországot. Április folyamán az "őrület" elérte Angliát, Németországot, Lettországot, Ausztriát, Észtországot, Norvégiát, Svédországot, Oroszországot, Finnországot, májusban Új-Zélandot, Hollandiát, Olaszországot, Mexikót, Dániát, Ausztráliát [33] .

Oroszországban

1880. április 25-én a St. Petersburg Herold feladott egy hirdetést német nyelven: "Neues Spiel - Das Spiel der Funfzehn" [34] ("Új játék - Játék 15 évesen").

Feladatok

The Gem Puzzle

Az 1879-ben Matthias Ries által készített és értékesített The Gem Puzzle -ban a játékos kiürítette a lapkákat egy dobozból, és véletlenszerűen visszatette, majd megpróbálta visszaállítani a rendelt konfigurációt [20] [10] :

Helyezze a blokkokat véletlenszerűen a dobozba, majd mozgassa őket, amíg a megfelelő sorrendben nem kerülnek sorba.
Eredeti szöveg  (angol) : 
Helyezze a blokkokat a dobozba szabálytalanul, majd mozgassa addig, amíg szabályos sorrendben van.

Ebben a verzióban a probléma pontosan az esetek felében bizonyult megoldhatatlannak.

Rejtvény 14-15

Egy másik változatban a 14-es és 15-ös kivételével minden csempe kezdetben a helyén van; a feladat a rosszul elhelyezett 14. és 15. lapkák felcserélése. Ez a feladat megoldhatatlan; azonban ebben az esetben a lapkákat elrendezheti egy üres cellával a bal felső sarokban, vagy sorba rendezheti a zsetonokat oszlopokba [35] .

  • Rizs. 1. A 14-15. rejtvény kiinduló helyzetében a 14-es és 15-ös lapkákat felcseréljük

  • Rizs. 2. Ez a hely nem érhető el a 14-15-ös kirakós kezdőhelyről (1. ábra)

  • Rizs. 3. De ez a hely elérhető a 14-15. kirakós kezdőhelyről (1. ábra)

  • Rizs. 4. Egy másik elérhető hely a 14-15. rejtvényhez (1. ábra)

Modern módosítások

A puzzle számos változata megjelent. Egyes kiviteli alakoknál a számok rendezése helyett valamilyen kép visszaállítása a cél. Számok helyett betűk is használhatók; legalább két egyforma betű jelenléte nem triviális feladattá teheti a rejtvény megfejtését.

  • Az elefánt állva alszik. És te?

  • Angolul ("Measure your mind, my friend") [8]

  • németül ("Munka nélkül nincs jutalom")

Magic Square

Az egyik feladat a csempék átrendezése oly módon, hogy az egyes sorok számainak összege (vízszintes, függőleges vagy nagy átlós) azonos számmal egyenlő legyen ; míg egy üres cella számértékét nullának tekintjük [36] [37] . Ebben az esetben a varázslat összege 30. Legalább 35 mozdulat szükséges ahhoz, hogy a varázsnégyzet a kiindulási helyről kerüljön, és csak egy varázsmező érhető el 35 mozdulattal [38] .

Matematikai leírás

Kimutatható, hogy a címkék összes lehetséges 20 922 789 888 000 (=16 ! ) kezdőpozíciójának pontosan a fele nem hozható az összeállított formába. Legyen egy számmal rendelkező csempe (ha balról jobbra és fentről lefelé számol) olyan lapkák előtt, amelyeknél kisebb a szám ; akkor jelöljük . Különösen, ha egy számmal rendelkező csempe után nincs olyan csempe, amely kisebb, mint , akkor . Beírunk egy számot is  – az üres cella sorának számát (1-től számítva). Ha az összeg

(azaz azoknak a csontpároknak az összege, amelyekben a nagyobb számú csont a kisebb számú csont elé kerül, és egy üres cella sorszámának összege) páratlan , akkor nincs megoldás a rejtvény [39] [3] .

Ha hagyjuk, hogy a doboz 90 fokkal elforduljon, amelyben a számok képei az oldalukon hevernek, akkor lehetséges a megoldhatatlan kombinációk oldhatóvá alakítása (és fordítva). Így ha a számok helyett pontokat teszünk a csuklókra, és nem rögzítjük a doboz helyzetét, akkor egyáltalán nem lesznek megoldhatatlan kombinációk.

Optimális megoldás

Az általánosított címkék esetében (több mint 15 csempével) egy adott konfigurációra a legrövidebb megoldás megtalálásának problémája NP-teljes [40] [41] .

4  ×  4

A „klasszikus” 4  × 4-es rejtvény 10 461 394 944 000 megoldható konfigurációja közül  bármelyik legfeljebb 80 mozdulattal konvertálható az eredetire, ha a lépés alatt egy lapka mozgását értjük [42] [43] [38] [44 ] , vagy legfeljebb 43 lépésben, ha mozdulat alatt legfeljebb három lapkából álló folyamatos sor egyidejű mozgását értjük [45] . A feloldható konfigurációk közül csak 17 nem oldható meg 80 lépésnél kevesebbel, vagyis ezek megoldásához 80 lépésre van szükség az egyes lapkákból [43] [38] [46] ; csak 16 feloldható konfigurációhoz van szükség 43 folyamatos lapkasor mozgatására [45] .

5  ×  5

1995-ben kimutatták, hogy egy 5  ×  5-ös rejtvény tetszőleges konfigurációja legfeljebb 219 egyszeri mozdulattal oldható meg [47] , azaz 219 lépésből álló felső korlátot kaptunk az optimális megoldás hosszára egy tetszőlegesre. konfigurációt. 1996-ban találtak egy olyan konfigurációt, amely nem oldható meg 112 lapkalépésnél kevesebbel [48] . 2000-ben a felső határt 210 lépésre javították [49] ; 2011-ben az 5  × 5-ös kirakó „ Isten száma ”  egy 152 lépésből álló alsó és egy 208 lépésből álló felső korlátot kaptak [44] .

Aktuális eredmények

A táblázat a „címkék” számos általánosításának adatait foglalja össze. Ha a pontos eredmény nem ismert, a legismertebb alsó és felső határértéket lb - ub formában adjuk meg .

A méret Célkonfiguráció
A megoldandó konfigurációk száma		 "Hosszú"
mozdulatok [K 1] 		" Isten száma "
Az "antipódok" száma [K 2]
2  ×  2 üres doboz a sarokban 12 Nem 6 [49] [50] 1 [49]
2  ×  3 üres doboz a sarokban 360 Nem 21 [49] [50] 1 [49]
2  ×  4 üres doboz a sarokban 20 160 Nem 36 [49] [50] 1 [49]
2  ×  5 üres doboz a sarokban 1 814 400 Nem 55 [51] [50] 2 [51]
2  ×  6 üres doboz a sarokban 239 500 800 Nem 80 [52] [50] 2 [52]
2  ×  7 üres doboz a sarokban 43 589 145 600 Nem 108 [53] [50]
2  ×  8 üres doboz a sarokban 10 461 394 944 000 Nem 140 [53] [50]
3  ×  3 üres doboz a sarokban 181 440 Nem 31 [49] [44] [50] 2 [49] [54]
Igen 24 [44]
3  ×  4 üres doboz a sarokban 239 500 800 Nem 53 [49] [50] 18 [49]
3  ×  5 üres doboz a sarokban 653 837 184 000 Nem 84 [50]
3  ×  5 üres cella közepén 653 837 184 000 Nem 84 [55]
4  ×  4 üres doboz a sarokban 10 461 394 944 000 Nem 80 [43] [38] [44] [50] 17 [43] [38] [46]
Igen 43 [45] 16 [45]
5  ×  5 üres doboz a sarokban 7,7556⋅10 24 Nem 152 [44]  - 208 [44]

A címkék használata a számítástechnikában

Az 1960-as évek óta rendszeresen használnak különféle méretű "tizenöt"-et az MI - kutatásban ; különösen tesztelik és hasonlítják össze a különböző heurisztikus függvényekkel [56] [57] [58] [59] rendelkező állapottér-keresési algoritmusokat és egyéb olyan optimalizációkat, amelyek befolyásolják a keresési folyamat során felkeresett rejtvénykonfigurációk (gráfcsúcsok) számát. A tanulmányokban így vagy úgy, 3  ×  3 [60] [61] , 4  ×  4 [62] [63] [43] , 5  ×  5 [48] [64] [65] , 6  × méretű rejtvények szerepeltek.  6 [66] volt , 2  ×  7 [55] , 3  ×  5 [55] .

Felsorolhatjuk a fő okokat, amelyek miatt a címkéket választották a keresési algoritmusok "tesztágyaként" [67] [40] [68] :

  1. a klasszikus címkék állapottere hozzáférhető az elemzéshez, de még mindig elég nagy ahhoz, hogy érdeklődést keltsen, és különböző heurisztikákat használjon és összehasonlítson [69] ;
  2. nem ismert olyan algoritmus , amely ésszerű időn belül megtalálja a legrövidebb megoldást általánosított n  ×  n címkékre [40] ;
  3. maga a címkék legrövidebb megoldásának megtalálása is könnyen érthető és programozottan manipulálható [56] [40] ; a rejtvény leírható egy kis és jól meghatározott egyszerű szabályrendszerrel [70] [40] ;
  4. a rejtvénymodellezés nem igényli az összetettebb tématerületekben rejlő szemantikai finomságok átadását [71] ;
  5. a címkékkel kapcsolatos problémák sikeres képviselői annak a problémaosztálynak, amelyben meg kell találni a legrövidebb utat egy irányítatlan véges gráf két adott csúcsa között [40] ;
  6. a keresési gráf mérete exponenciálisan függ az n rejtvény méretétől , bár bármely állapot leírható O ( n 2 ) memória segítségével [40] ;
  7. ugyanaz a heurisztikus függvény alkalmazható minden állapotra, mivel minden állapot leírása azonos módon történik; valós alkalmazásokban a különböző állapotok eltérő leírással rendelkezhetnek, amihez több heurisztika bevezetése szükséges [72] ;
  8. a játékok és rejtvények kutatási alkalmazása nem vet fel pénzügyi vagy etikai problémákat [71] .

Heurisztikus keresés

Algoritmus A* , IDA* [73] , szélesség első keresés használható keresési algoritmusként .

 A 3 × 3-as rejtvény  könnyen megoldható bármely keresési algoritmussal.  A 4 × 4-es címkék tetszőleges konfigurációit  modern keresőalgoritmusok segítségével néhány ezredmásodperc alatt megoldják [57] .  Az 5 × 5-ös rejtvény optimális megoldása  még a modern számítógépek és algoritmusok használatával is több erőforrást igényel [57] [64] ; a keresési folyamat több hétig is eltarthat, és több billió csomópontot generál [65] [66] .  A 6 ×  6-os rejtvény tetszőleges konfigurációinak optimális megoldása még mindig meghaladja a lehetőségeket [66] , ezért a tanulmányok csak az IDA* algoritmus relatív teljesítményét próbálják megjósolni különböző heurisztikus függvényekkel [66] .

A címkék egyik legegyszerűbb heurisztikája a következőképpen fejezhető ki [74] [75] [76] :

A megoldáshoz szükséges lépések száma nem kevesebb, mint a nem helyén lévő lapkák száma.

Az állítás helyessége, vagyis a "nem a helyükön lévő lapkák száma" heurisztikus függvény elfogadhatósága abból következik, hogy egy mozdulattal csak egy lapkát lehet a helyére tenni. Ez a heurisztika nem használja fel az összes rendelkezésre álló információt: például nem veszi figyelembe, hogy az egyes csempéket mekkora távolságra kell mozgatni.

Egy intelligensebb heurisztika hozzárendeli az egyes lapkák helyéhez az egyes lapkák aktuális pozíciója és a célpozíció közötti távolságok összegét [77] . A szakirodalomban ez a heurisztika "Manhattan távolság" (Manhattan distance) néven található [76] [78] . A függvény érvényessége abból adódik, hogy lépésenként csak egy bábu mozog, és a távolság e bábu és a végső pozíciója között 1-gyel változik. Ez a heurisztika azonban szintén nem használja fel az összes rendelkezésre álló információt, mivel egy pozícióban két lapka nem lehet egyszerre. A "Manhattan távolságnak" vannak tájékozottabb változatai, mint például a Lineáris konfliktus [58] .

 A mintaadatbázisokon [63] [64] [59] alapuló heurisztikákat fejlesztettek ki , hogy gyorsan megtalálják az optimális megoldást egy 4  ×  4-es rejtvényre, valamint képesek legyenek megtalálni az optimális megoldást egy 5  × 5-ös rejtvényre ésszerű keretek között. idő . Az ilyen heurisztika lényegében a RAM-ban előre kiszámított és tárolt táblázatok, amelyekben a részfeladatok optimális megoldásai vannak kódolva; az egyes részfeladatok egy bizonyos csempecsoport célpozíciókra való mozgatásához vezetnek [63] . Ezek a heurisztikák a Rubik-kockára és más rejtvényekre is alkalmazhatók [64] .

Lásd még

Megjegyzések

  1. ↑ Az oszlop azt jelzi, hogy több lapka egyidejű, folyamatos függőleges vagy vízszintes sort képező mozgása egy mozdulatnak számít-e.
  2. ↑ „Antipodes” – olyan rejtvénykonfigurációk, amelyek megoldásához a legtöbb lépésre van szükség

Jegyzetek

  1. ↑ Matematikai szabadidő, 1972 , p. 401.
  2. ↑ 1 2 Szórakoztató feladatok és kísérletek, 1972 , p. 365.
  3. ↑ 1 2 „15” lejátszása . Matematikai komponens . Matematikai tanulmányok .
  4. ↑ Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 43, 114, 163, 166, 168, 181-182.
  5. ↑ 1 2 Nevezze meg "Tizenöt" . TwistyPuzzles.RU.
  6. ↑ Vlagyimir Belov. Rejtvények közelről. 2. rész . Computerra (2000. január 18.). Archiválva az eredetiből 2015. november 28-án.
  7. ↑ Rejtvények ciklopédiája , p. 235
  8. ↑ 1 2 3 Jaap Scherphuis. 14-15 puzzle / Boss puzzle . Jaap rejtvényoldala .
  9. ↑ A 15 rejtvény, 2006 .
  10. ↑ 1 2 3 Aaron Archer áttekintése A 15 rejtvényről , p. egy.
  11. ↑ Puzzles for Pleasure, 1994 , p. 10-12.
  12. ↑ A 15 rejtvény, 2006 , p. 76.
  13. ↑ Puzzles for Pleasure, 1994 , p. tizenegy.
  14. ↑ 1 2 3 4 The 15 Puzzle, 2006 , p. 109.
  15. ↑ Aaron Archer áttekintése A 15 rejtvényről , p. 13.
  16. ↑ A 15 rejtvény, 2006 , p. 98-99.
  17. ↑ A 15 rejtvény, 2006 , p. 103-104, 109.
  18. ↑ A 15 rejtvény, 2006 , p. 11, 109.
  19. ↑ 1 2 Aaron Archer áttekintése A 15 rejtvényről , p. 2.
  20. ↑ 1 2 Jerry Slocum: Sam Loyd's Most Successful Hoax Archiválva : 2015. december 23., a Wayback Machine (PDF; 672 kB) . Vortrag auf: Seventh Gathering for Gardner, 2006. március, The Convention of the Association of the Association of Game and Puzzle Collectors. Kiadó: E. Pegg, A. H. Schoen és T. Rodgers: Homage to a Pied Puzzler. A.K. Peters, Wellesley/Massachusetts, 2009, S. 3-21. (első: S. 4)
  21. ↑ A 15 rejtvény, 2006 , p. 100-101.
  22. ↑ A 15 rejtvény, 2006 , p. 101.
  23. ↑ EU Kinsey. Puzzle blokkok. nem. 207124. Szabadalmaztatott aug. 20, 1878 .
  24. ↑ A 15 rejtvény, 2006 , p. 102.
  25. ↑ Aaron Archer áttekintése A 15 rejtvényről , p. 3.
  26. ↑ A 15 rejtvény, 2006 , p. 14-15.
  27. ↑ A 15 rejtvény, 2006 , p. 15-16.
  28. ↑ 1 2 A 15 rejtvény, 2006 , p. 12.
  29. ↑ A 15 rejtvény, 2006 , p. húsz.
  30. ↑ A 15 rejtvény, 2006 , p. 21.
  31. ↑ A 15 rejtvény, 2006 , p. 24, 98.
  32. ↑ A 15 rejtvény, 2006 , p. 59.
  33. ↑ A 15 rejtvény, 2006 , p. 60.
  34. ↑ A 15 rejtvény, 2006 , p. 63.
  35. ↑ Szórakoztató feladatok és kísérletek, 1972 , p. 370.
  36. ↑ Szórakoztató feladatok és kísérletek, 1972 , p. 371.
  37. ↑ Sam Loyd; Martin Gardner: Sam Loyd matematikai rejtvényei . Dover Pubs., New York 1959, pp. 19. és 20. Google könyvek
  38. ↑ 1 2 3 4 5 Herbert Kociemba. Tizenöt Rejtvény Optimális Megoldó . Archiválva az eredetiből 2015. október 2-án.
  39. ↑ Slocum J., Weisstein EW 15 Puzzle  (angol) a Wolfram MathWorld webhelyen .
  40. ↑ 1 2 3 4 5 6 7 Ratner D., Warmuth MK A legrövidebb megoldás megtalálása a 15-PUZZLE N × N kiterjesztésére megoldhatatlan // Országos Mesterséges Intelligencia Konferencia, 1986.
  41. ↑ Ratner D., Warmuth M. Az (n 2 −1)-rejtvény és a kapcsolódó áthelyezési problémák  // Journal of Symbolic Computation. - 1990. - T. 10 , 2. sz . – 111–137 . - doi : 10.1016/S0747-7171(08)80001-6 .
  42. ↑ A. Brüngger, A. Marzetta, K. Fukuda és 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. Nagyszabású párhuzamos szélesség – első keresés . – 2005.
  44. ↑ 1 2 3 4 5 6 7 OEIS szekvencia A087725 : a legtöbb mozdulat, amely az n  ×  n 15-ös rejtvény általánosításához szükséges
  45. ↑ 1 2 3 4 Bruce Norskog. A Tizenöt Rejtvény 43 „mozdulattal” megoldható . A Kocka Fórum domainje (2010. december 8.).
  46. ↑ 1 2 OEIS sorozat A089484 : azon címkekonfigurációk száma, amelyek optimális megoldása n lépést tartalmaz
  47. ↑ Ralph Udo Gasser. Számítási erőforrások felhasználása a hatékony, teljes körű keresés érdekében . – 1995.
  48. ↑ 1 2 Richard E. Korf, Larry A. Taylor. Optimális megoldások keresése a huszonnégy rejtvényre . – 1996.
  49. ↑ 1 2 3 4 5 6 7 8 9 10 11 Filip RW Karlemo és Patric RJ Östergård a Sliding Block Puzzlesről , Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107
  50. ↑ 1 2 3 4 5 6 7 8 9 10 11 OEIS szekvencia A151944 : a legtöbb mozdulat egy m  ×  n 15 rejtvényből álló feladvány általánosításához
  51. ↑ 1 2 A090036 sorozat az OEIS -ben
  52. ↑ 1 2 A090167 sorozat az OEIS -ben
  53. ↑ 1 2 A151943 sorozat az OEIS -ben
  54. ↑ OEIS szekvencia A089473 _
  55. ↑ 1 2 3 Richard E. Korf. Szélesség-első határkeresés késleltetett ismétlődésérzékeléssel . – 2004.
  56. ↑ 1 2 Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 114.
  57. ↑ 1 2 3 Mesterséges intelligencia: modern megközelítés, 2006 , p. 118.
  58. ↑ 1 2 Megengedhető heurisztikák generálása a laza modellek megoldásainak kritizálásával, 1985 .
  59. ↑ 1 2 F. Yang, J. Culberson, R. Holte, U. Zahavi és A. Felner Az additív állapottér-absztrakciók általános elmélete archiválva : 2015. december 8., the Wayback Machine , 32. kötet (2008), 631-662.
  60. ↑ Alexander Reinfeld. A Nyolc rejtvény teljes megoldása és a csomópont-rendezés előnyei az IDA-ban* . – 1993.
  61. ↑ Daniel R. Kunkle. A 8 rejtvény megoldása minimális mozdulatszámmal: Az A* algoritmus alkalmazása . – 2001.
  62. ↑ Richard E. Korf. Mélység-első iteratív elmélyülés: Optimálisan elfogadható fakeresés . – 1985.
  63. ↑ 1 2 3 Joseph C. Culberson, Jonathan Schaeffer. Mintaadatbázisok . – 1998.
  64. ↑ 1 2 3 4 Richard E. Korf. Az elfogadható heurisztikus függvények tervezésében és elemzésében elért közelmúltbeli fejlődés . – 2000.
  65. ↑ 1 2 Richard E. Korf, Ariel Felner. Disjunkt Pattern Database heuristics . – 2002.
  66. ↑ 1 2 3 4 Ariel Felner, Richard E. Korf, Sarit Hanan. Additív minta adatbázis-heurisztika . – 2004.
  67. ↑ Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 43, 114, 163.
  68. ↑ Elfogadható heurisztikák generálása a laza modellek megoldásainak bírálatával, 1985 , p. 3.
  69. ↑ Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 114, 163.
  70. ↑ Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 43, 163.
  71. ↑ 1 2 Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 43.
  72. ↑ Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 163.
  73. ↑ Borowski BS Optimal 8/15-rejtvényfejtő . // Brian's Project Gallery. Letöltve: 2013. július 29. Az eredetiből archiválva : 2013. augusztus 17..
  74. ↑ Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 156.
  75. ↑ Szórakoztató programozás: Tutorial, 2005 , p. 171.
  76. ↑ 1 2 Elfogadható heurisztikák létrehozása a laza modellek megoldásainak kritizálásával, 1985 , p. 4-5.
  77. ↑ Mesterséges intelligencia: stratégiák és módszerek összetett problémák megoldására, 2003 , p. 157.
  78. ↑ Szórakoztató programozás: Tutorial, 2005 , p. 173.

Irodalom

Könyvek
  • Gardner M. Matematikai szabadidő / Per. angolról. Yu. A. Danilova . Szerk. Ya. A. Smorodinsky . - M .: Mir , 1972.
  • Perelman Ya. I. Szórakoztató feladatok és kísérletek. - M . : Gyermekirodalom , 1972.
  • Jerry Slocum és Dic Sonneveld. A 15-ös rejtvény. - 2006. - ISBN 1-890980-15-3 .
  • Szczepan Jelensky Pythagoras nyomában: Szórakoztató matematika = Śladami Pitagorasa / Lengyelből fordította G. F. Boyarskaya, B. V. Boyarsky és A. A. Yakushev. -M.:Detgiz, 1961. - S. 231-233.
  • » Videó » Letöltés Kutató Clarke BR Puzzle for Pleasure . - Cambridge University Press, 1994. - ISBN 0-521-46634-2 .
  • Luger, George F. Mesterséges intelligencia: Struktúrák és stratégiák a komplex problémamegoldáshoz. - 4. kiadás. - Williams Publishing House, 2003. - 864 p. — ISBN 5-8459-0437-4 . — ISBN 978-5-845-90437-9 .
  • Stuart Russell, Peter Norvig . Mesterséges intelligencia: modern megközelítés = Artificial Intelligence: A Modern Approach. - 2. kiadás - M . : "Williams" kiadó, 2006. - 1408 p. — ISBN 5-8459-0887-6 .
  • Mozgovoy M. V. Szórakoztató programozás: oktatóanyag . - Szentpétervár. : Péter , 2005. - 208 p. - ISBN 5-94723-853-5 .
Cikkek

Linkek

 NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája
gráfelmélet
halmazelmélet
Algoritmikus problémák
Logikai játékok
és rejtvények