Peg solitaire - Peg solitaire - Wikipedia

The Princezna Soubise hraje solitaire, 1697

Peg solitaire (nebo Solo Noble) je desková hra pro jednoho hráče zahrnujícího pohyb kolíků na desce s otvory. Některé sady používají kuličky na desce s odsazením. Tato hra je známá jednoduše jako Solitaire v Spojené království kde se karetní hry nazývají Trpělivost. To je také označováno jako Brainvita (hlavně v Indie, kde se sady komerčně prodávají pod tímto názvem).

První důkazy o hře lze vysledovat zpět k soudu Louis XIV a konkrétní datum roku 1697 s rytinou, kterou o deset let později vytvořil Claude Auguste Berey z Anne de Rohan-Chabot Princezna Soubise s puzzle po jejím boku. Srpen 1687 vydání francouzského literárního časopisu Mercure galant obsahuje popis herního plánu, pravidla a ukázkové problémy. Toto je první známý odkaz na hru v tisku.

Standardní hra zaplňuje celou desku kolíky, kromě středové díry. Cílem je pomocí platných tahů vyprázdnit celou desku kromě osamělého kolíku ve středové díře.

Prkno

Anglický solitaire board
Evropská hrací deska solitair

Existují dvě tradiční desky („.“ Jako počáteční kolík, „o“ jako počáteční otvor):

Angličtinaevropský
     · · · · · · · · · · · · · · O · · · · · · · · · · · · · · · ·
     · · · · · · · · · · · · · · · · O · · · · · · · · · · · · · · · · · · ·

Hrát si

Hra Peg solitaire
Muž hrající trojúhelníkový kolík solitaire na a Cracker Barrel restaurace.

Platným tahem je seskočení kolíku kolmo přes sousední kolík do otvoru o dvě pozice dál a poté odstranit vyskočený kolík.

V následujících diagramech · označuje kolík v díře, * povzbuzený označuje kolík, který má být přesunut, a Ó označuje prázdnou díru. Modrou ¤ je otvor, ze kterého se aktuální kolík přesunul; červená * je konečná poloha tohoto kolíku, červená Ó je otvor kolíku, který byl vyskočen a odstraněn.

Platné pohyby v každém ze čtyř ortogonálních směrů jsou tedy:

* · O → ¤ Ó *  Přejít doprava
o · *  →  * Ó ¤  Skočit doleva
*     ¤·  →  Ó  Skočit dolůÓ *
Ó *·  →  Ó  Vyskočit*     ¤

Na anglické desce mohou být první tři tahy:

    · · ·             · · ·             · · ·             · · ·     · * ·             · ¤ · · O · · * · · · · · · · ·     · · · Ó · · ·     · ¤ Ó * · · · O o Ó · · · · · · O · · · · · · * · · ·     · · · · · · ·     · · · ¤ · · ·· · · · · · ·     · · · · · · ·     · · · · · · ·     · · · · · · ·    · · ·             · · ·             · · ·             · · ·    · · ·             · · ·             · · ·             · · ·

Strategie

Existuje mnoho různých řešení standardního problému a jedna notace použitá k jejich popisu přiřazuje písmena děrám:

   Angličtina Evropská a b c a b c d e f y d e f zg h i j k l m g h i j k l mn o p x P O N n o p x P O NM L K J I H G M L K J I H G F E D Z F E D Y C B A C B A

Tento zápis zrcadlového obrazu se používá mimo jiné i proto, že na evropské desce je jednou sadou alternativních her začít s dírou v určité poloze a končit jediným kolíkem v její zrcadlené poloze. Na anglické desce jsou ekvivalentní alternativní hry začínající dírou a končí kolíčkem ve stejné pozici.

Pro evropskou desku s počátečním otvorem umístěným ve středu neexistuje řešení, pokud jsou povoleny pouze ortogonální pohyby. To lze snadno vidět následovně, argumentem od Hans Zantema. Rozdělte pozice desky na pozice A, B a C následujícím způsobem:

    A B C A B C A BA B C A B C AB C A B C A BC A B C A B C B C A B C A B C

Zpočátku pouze s volnou centrální pozicí je počet krytých pozic A 12, počet krytých pozic B je 12 a také počet krytých pozic C je 12. Po každém pohybu se počet krytých pozic A zvyšuje nebo snižuje o jedna a stejná pro počet krytých pozic B a počet krytých pozic C. Proto po sudém počtu tahů jsou všechna tato tři čísla sudá a po lichém počtu tahů jsou všechna tato tři čísla lichá. Proto nelze dosáhnout konečné polohy pouze s jedním kolíkem, protože by to vyžadovalo, aby jedno z těchto čísel bylo jedno (poloha kolíku, jedno liché), zatímco další dvě čísla jsou nulová, tedy sudá.

Existuje však několik dalších konfigurací, kde lze jednu počáteční díru zmenšit na jediný kolík.

Taktikou, kterou lze použít, je rozdělit desku na balíčky po třech a zcela je očistit (odstranit) pomocí jednoho dalšího kolíku, katalyzátoru, který vyskočí a pak skočí zpět. V níže uvedeném příkladu je * je katalyzátor .:

* · O ¤ Ó *      Ó * ·      * Ó ¤  ·     →    ·    →     Ó     → o · · ¤          Ó

Tuto techniku ​​lze použít s řadou 3, blokem 2 · 3 a 6-kolíkovým tvarem L se základnou délky 3 a svisle délky 4.

Mezi další alternativní hry patří začátek se dvěma prázdnými jamkami a dokončení se dvěma kolíky v těchto jamkách. Také začíná s jednou dírou tady a končí s jedním kolíkem tam. Na anglické desce může být díra kdekoli a finální kolík může skončit až tam, kde to dovolí násobky tří. Tedy díra v A může ponechat pouze jeden kolík na A, str, Ó nebo C.

Studie o peg solitaire

Je známa důkladná analýza hry.[1] Tato analýza zavedla pojem nazvaný funkce pagoda což je silný nástroj k prokázání neproveditelnosti daného, ​​zobecněného, ​​peg solitaire problému.

Řešení pro nalezení pagodové funkce, které demonstruje neproveditelnost daného problému, je formulováno jako problém lineárního programování a je řešitelné v polynomiálním čase.[2]

Článek v roce 1990 se zabýval zobecněnými problémy Hi-Q, které jsou ekvivalentní problémům peg solitaire, a ukázal jejich NP-úplnost.[3]

Článek z roku 1996 formuloval problém peg solitaire jako problém kombinatorické optimalizace a diskutoval o vlastnostech proveditelné oblasti zvané „solitaire cone“.[4]

V roce 1999 byl peg solitaire kompletně vyřešen na počítači pomocí vyčerpávajícího hledání všech možných variant. Bylo toho dosaženo využitím symetrií, efektivního ukládání konstelací desek a hašování.[5]

V roce 2001 byla vyvinuta efektivní metoda řešení problémů s peg solitaire.[2]

Nepublikovaná studie z roku 1989 o zobecněné verzi hry na anglické desce ukázala, že každý možný problém v zobecněné hře má 29 možná odlišná řešení, kromě symetrií, protože anglická deska obsahuje 9 odlišných dílčích čtverců 3 × 3. Jedním z důsledků této analýzy je stanovení spodní hranice velikosti možných problémů s „obrácenou polohou“, ve kterých jsou původně obsazené buňky ponechány prázdné a naopak. Jakékoli řešení takového problému musí obsahovat minimálně 11 tahů, bez ohledu na přesné podrobnosti problému.

To lze prokázat pomocí abstraktní algebra že existuje pouze 5 pozic na pevné desce, kde může hra úspěšně skončit jedním kolíkem.[6]

Řešení anglické hry

Nejkratší řešení standardní anglické hry zahrnuje 18 tahů a počítá několik skoků jako jednotlivé tahy:

Toto řešení našel v roce 1912 Ernest Bergholt a ukázalo se jako nejkratší možné John Beasley v roce 1964.[7]

Toto řešení lze také vidět na stránka, která také zavádí Wolstenholme notaci, který má usnadnit zapamatování řešení.

Mezi další řešení patří následující seznam. V nich je použitá notace

  • Seznam počátečních jamek
  • Dvojtečka
  • Seznam koncových cílových kolíků
  • Znaménko rovná se
  • Kolík zdroje a cílová díra (přeskočené kolíky jsou ponechány jako cvičení pro čtenáře)
  • , nebo / (lomítko se používá k oddělení „chunků“, jako je šestičlenné vyčištění)
x: x = ex, lj, ck, Pf, DP, GI, JH, mG, GI, ik, gi, LJ, JH, Hl, lj, jh, CK, pF, AC, CK, Mg, gi, ac, ck, kI, dp, pF, FD, DP, Pp, oxx: x = ex, lj, xe / hj, Ki, jh / ai, ca, fd, hj, ai, jh / MK, gM, hL, Fp, MK, pF / CK, DF, AC, JL, CK, LJ / PD, GI, mG, JH, GI, DP / Oxj: j = lj, Ik, jl / hj, Ki, jh / mk, Gm, Hl, fP, mk, Pf / ai, ca, fd, hj, ai, jh / MK, gM, hL, Fp, MK, pF / CK, DF, AC, JL, CK, LJ / Jji: i = ki, Jj, ik / lj, Ik, jl / AI, FD, CA, HJ, AI, JH / mk, Hl, Gm, fP, mk, Pf / ai, ca, fd, hj, ai, jh / gi, Mg, Lh, pd, gi, dp / Kie: e = xe / lj, Ik, jl / ck, ac, df, lj, ck, jl / GI, lH, mG, DP, GI, PD / AI, FD, CA, JH, AI, HJ / pF, MK, gM, JL, MK, Fp / hj, ox, xed: d = fd, xe, df / lj, ck, ac, Pf, ck, jl / DP, KI, PD / GI, lH, mG, DP, GI, PD / CK, DF, AC, LJ, CK, JL / MK, gM, hL, pF, MK, Fp / pdb: b = jb, lj / ck, ac, Pf, ck / DP, GI, mG, JH, GI, PD / LJ, CK, JL / MK, gM, hL, pF, MK, Fp / xo, dp, ox / xe / AI / BJ, JH, Hl, lj, jbb: x = jb, lj / ck, ac, Pf, ck / DP, GI, mG, JH, GI, PD / LJ, CK, JL / MK, gM, hL, pF, MK, Fp / xo, dp, ox / xe / AI / BJ, JH, Hl, lj, exa: a = ca, jb, ac / lj, ck, jl / Ik, pP, KI, lj, Ik, jl / GI, lH, mG, DP, GI, PD / CK, DF, AC, LJ, CK, JL / dp, gi, pd, Mg, Lh, gi / iaa: p = ca, jb, ac / lj, ck, jl / Ik, pP, KI, lj, Ik, jl / GI, lH, mG, DP, GI, PD / CK, DF, AC, LJ, CK, JL / dp, gi, pd, Mg, Lh, gi / dp

Útok hrubou silou na standardní anglický kolík solitaire

Jediným místem, kde je možné skončit s osamělým kolíkem, je střed nebo střed jednoho z okrajů; na posledním skoku bude vždy možnost zvolit, zda skončit ve středu nebo na okraji.

Následuje tabulka nad číslem (Possible Board Pmožných pozic desky po n skoky a možnost tažení stejného pěšce k dalšímu skoku (NÓ Further Jumps).

POZNÁMKA: Pokud lze jednu pozici desky otočit a / nebo převrátit do jiné polohy desky, pozice desky se počítají jako identické.

Jelikož skoků může být pouze 31, mohou moderní počítače snadno prozkoumat všechny herní pozice v rozumném čase.[8]

Výše uvedená sekvence „PBP“ byla zadána jako A112737 v OEIS. Všimněte si, že celkový počet dosažitelných pozic desky (součet sekvence) je 23 475 688, zatímco celkový počet možných pozic desky je 8 589 934 590 (33 bitů-1) (2 ^ 33), takže pouze asi 2,2% všech možných desek pozic lze dosáhnout počínaje prázdným středem.

Je také možné generovat všechny pozice na desce. Níže uvedené výsledky byly získány pomocí sada nástrojů mcrl2 (viz příklad peg_solitaire v distribuci).

Ve výsledcích níže je to generování všech pozic na palubě opravdu dosáhl počínaje středem prázdným a skončil ve střední díře.

Řešení evropské hry

Existují 3 počáteční nekongruentní pozice, které mají řešení.[9] Tyto jsou:

1)

          0 1 2 3 4 5 6 0 o · · 1 · · · · 2 · · · · · · 3 · · · · · · 4 · · · · · 5 · · · · 6 · · ·

Možné řešení: [2: 2-0: 2, 2: 0-2: 2, 1: 4-1: 2, 3: 4-1: 4, 3: 2-3: 4, 2: 3-2: 1, 5: 3–3: 3, 3: 0–3: 2, 5: 1–3: 1, 4: 5–4: 3, 5: 5–5: 3, 0: 4–2: 4, 2: 1–4: 1, 2: 4–4: 4, 5: 2–5: 4, 3: 6–3: 4, 1: 1–1: 3, 2: 6–2: 4, 0: 3-2: 3, 3: 2-5: 2, 3: 4-3: 2, 6: 2-4: 2, 3: 2-5: 2, 4: 0-4: 2, 4: 3- 4: 1, 6: 4-6: 2, 6: 2-4: 2, 4: 1-4: 3, 4: 3-4: 5, 4: 6-4: 4, 5: 4-3: 4, 3: 4-1: 4, 1: 5-1: 3, 2: 3-0: 3, 0: 2-0: 4]

2)

          0 1 2 3 4 5 6 0 · · · 1 · · o · · 2 · · · · · · 3 · · · · · · 4 · · · · · 5 · · · 6 · · ·

Možné řešení: [1: 1-1: 3, 3: 2-1: 2, 3: 4-3: 2, 1: 4-3: 4, 5: 3-3: 3, 4: 1-4: 3, 2: 1-4: 1, 2: 6-2: 4, 4: 4-4: 2, 3: 4-1: 4, 3: 2-3: 4, 5: 1-3: 1, 4: 6-2: 6, 3: 0-3: 2, 4: 5-2: 5, 0: 2-2: 2, 2: 6-2: 4, 6: 4-4: 4, 3: 4-5: 4, 2: 3-2: 1, 2: 0-2: 2, 1: 4-3: 4, 5: 5-5: 3, 6: 3-4: 3, 4: 3- 4: 1, 6: 2-4: 2, 3: 2-5: 2, 4: 0-4: 2, 5: 2-3: 2, 3: 2-1: 2, 1: 2-1: 4, 0: 4-2: 4, 3: 4-1: 4, 1: 5-1: 3, 0: 3-2: 3]

a 3)

          0 1 2 3 4 5 6 0 · · · 1 · · · · 2 · · · o · · 3 · · · · · · 4 · · · · · 5 · · · 6 · · ·

Možné řešení: [2: 1-2: 3, 0: 2-2: 2, 4: 1-2: 1, 4: 3-4: 1, 2: 3-4: 3, 1: 4-1: 2, 2: 1-2: 3, 0: 4-0: 2, 4: 4-4: 2, 3: 4-1: 4, 6: 3-4: 3, 1: 1-1: 3, 4: 6-4: 4, 5: 1-3: 1, 2: 6-2: 4, 1: 4-1: 2, 0: 2-2: 2, 3: 6-3: 4, 4: 3-4: 1, 6: 2-4: 2, 2: 3-2: 1, 4: 1-4: 3, 5: 5-5: 3, 2: 0-2: 2, 2: 2- 4: 2, 3: 4-5: 4, 4: 3-4: 1, 3: 0-3: 2, 6: 4-4: 4, 4: 0-4: 2, 3: 2-5: 2, 5: 2-5: 4, 5: 4-3: 4, 3: 4-1: 4, 1: 5-1: 3]

Varianty desek

Peg solitaire se hraje na deskách jiných velikostí, ačkoli dva výše uvedené jsou nejoblíbenější. Hraje se také na trojúhelníkové desce s povolenými skoky ve všech 3 směrech. Pokud má varianta správnou „paritu“ a je dostatečně velká, bude pravděpodobně řešitelná.

Peg solitaire tvary herních desek:
(1) Francouzský (evropský) styl, 37 jamek, 17. století;
(2) J. C. Wiegleb, 1779, Německo, 45 děr;
(3) Asymetrické 3-3-2-2, jak je popsáno v George Bell, 20. století;
(4) Anglický styl (standardní), 33 děr;
(5) Diamant, 41 otvorů;
(6) Trojúhelníkový, 15 otvorů.
Šedá = díra pro přeživšího.

Běžná trojúhelníková varianta má pět kolíků na boku. Řešení, kdy konečný kolík dorazí na počáteční prázdnou díru, není možné pro díru v jedné ze tří středových poloh. Nastavení prázdné rohové díry lze vyřešit deseti tahy a nastavení prázdné středové díry devíti (Bell 2008):

Video hra

26. června 1992 byla pro Game Boy vydána videohra založená na peg solitaire. Pod názvem „Solitaire“ byla hra vyvinuta společností Hect. V Severní Americe vydala společnost DTMC hru jako „Lazlosův skok“.

Reference

  1. ^ Berlekamp, ​​E. R.; Conway, J. H.; Guy, R. K. (2001) [1981], Vítězné způsoby pro vaše matematické hry (brožura) | formát = vyžaduje | url = (Pomoc) (2. vyd.), A K Peters / CRC Press, ISBN  978-1568811307, OCLC  316054929
  2. ^ A b Kiyomi, M .; Matsui, T. (2001), „Integer Algorithms Programming Based Algorithms for Peg Solitaire Problems“, Proc. 2. int. Konf. Počítače a hry (CG 2000): Celočíselné algoritmy založené na programování problémů s peg solitaire, Přednášky v informatice, 2063, str. 229–240, CiteSeerX  10.1.1.65.6244, doi:10.1007/3-540-45579-5_15, ISBN  978-3-540-43080-3
  3. ^ Uehara, R .; Iwata, S. (1990). "Zobecněný Hi-Q je NP-úplný". Trans. IEICE. 73: 270–273.
  4. ^ Avis, D.; Deza, A. (2001), „Kužel solitairu a jeho vztah k multikomoditním tokům“, Matematické programování, 90 (1): 27–57, doi:10.1007 / PL00011419
  5. ^ Eichler; Jäger; Ludwig (1999), c't 07/1999 Spielverderber, Solitaire mit dem Computer lösen (v němčině), 7, str. 218
  6. ^ „Matematika a brainvita“, Poznámky k matematice, 28. srpna 2012, vyvoláno 6. září 2018
  7. ^ Pro Beasleyho důkaz viz Vítězné způsoby, svazek # 4 (druhé vydání).
  8. ^ "soloboard". github. 2020-08-31. Citováno 2020-08-31. Implementace výpočtu hrubé síly hry Peg solitaire
  9. ^ Brassine, Michel (prosinec 1981), "Découvrez ... le solitaire", Jeux et Stratégie (francouzsky)

Další čtení

externí odkazy