Solitaire (hra)

Solitaire  je desková hra pro jednoho hráče, ve které se kolíčky vyměňují na desce s otvory. Některé stavebnice používají kuličky a vroubkované desky. V USA se hra nazývá Peg Solitaire (peg solitaire) a název Solitaire odkazuje na solitaire. Ve Velké Británii je tato hra známá jako Solitaire (solitaire) a karetní hra se nazývá Patience ( solitaire ). Na některých místech, zejména v Indii , se hra nazývá Brainvita . V SSSR byl vyroben hlavolam s názvem Yoga [1] .

První zmínky o hře najdeme na dvoře Ludvíka XIV . v roce 1697. Letos je označena rytina od Claude Auguste Bereille Anne de Roan Chabot, Princess de Soubise , která zobrazuje princeznu hrající solitaire. V srpnu 1697 byl ve francouzském literárním časopise Mercure galant zveřejněn popis desky, pravidel a příklady problémů . Toto je první známá zmínka o hře v tisku.

Ve standardní hře je celé pole zaplněno kolíky, s výjimkou středového otvoru. Cílem hry je osvobodit celou desku z kolíčku, přičemž poslední kolík zůstane ve středu desky.

Deska

Hraje se se dvěma tradičními deskami ('.' jako počáteční kolík, 'o' jako prázdná jamka):

Angličtina evropský
• • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • •

Hra

Legálním tahem je přeskočit kolík sousedním kolíkem do volné díry bezprostředně po druhém kolíku (jako v dámě, ale pohyb je vertikální nebo horizontální, nemůžete se pohybovat diagonálně), pak je vyskočený kolík odstraněn.

Symboly v níže uvedených diagramech:
• kolík v otvoru
* kolík se pohybuje
o  prázdný otvor
¤ otvor, ze kterého byl pohyb proveden
* koncová poloha kolíku
o otvor odstraněného kolíku.

Pak jsou legální kroky ve všech čtyřech směrech:

* • o → ¤ o * skok doprava o • * → * o ¤ skok doleva * ¤ • → o skok dolů o * o * • → o skok nahoru * ¤

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

• • • • • • • • • • • • • • * • • ¤ • • o • • * • • • • • • • • • • • o • • • • ¤ o * • • • • oo o • • • • • • o • • • • • * • • • • • • • • • • • • • ¤ • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •

Strategie

Je snadné jít špatným směrem a zjistit, že dva nebo tři prázdné otvory oddělují osamělý kolík. Mnoho lidí nedokázalo problém vyřešit.

Existuje mnoho různých řešení pro standardní problém a abychom je popsali, uvedeme označení písmen:

Angličtina evropská abcabc defydefz ghijklmghijklm nopx PON nopx PON MLKJIHGMLKJIHG FEDZFEDY CBACBA

Zrcadlové označení polí se používá mimo jiné proto, že na evropské desce v jedné z rodiny alternativních her hra začíná nějakou dírou na libovolném místě a musí končit v zrcadlové jamce. Na anglické desce začínají a končí alternativní hry ve stejné jamce.

V evropské verzi hry neexistuje žádné řešení s počátečním prázdným čtvercem ve středu, pokud nejsou povoleny diagonální pohyby. To lze snadno pochopit, vezmeme-li v úvahu argumenty Hanse Zantemy. Označme pozice desky písmeny A, B a C takto:

ABC ABCAB ABCABCA BCABCAB CABCABC BCABC ABC

Budeme počítat počet kolíčků na pozicích každého typu. Pokud je počáteční prázdná pozice ve středu, počet pozic A je 12, pozic B je také 12 (celkem 13, ale jedna je volná), počet pozic C je také 12. Po každém tahu se počet pozic kolíčky skupiny A se sníží nebo zvýší o jednu, totéž se stane s pozicemi skupin B a C. Po sudém počtu tahů jsou tedy všechna tato tři čísla sudá a po lichém lichá. Nelze tedy získat konečnou pozici, ve které zůstane pouze jeden kolík – skupina, kde kolíček skončí, bude mít součet jedna, zatímco další dva musí mít součet nula.

Existují však některé další konfigurace, ve kterých lze jednu volnou díru přivést k jedinému kolíku.

Užitečnou taktikou pro vyřešení hádanky je rozdělení celé hrací desky do trojic a poté jsou trojice odstraněny pomocí dalšího kolíčku, katalyzátoru. Ve výše uvedeném příkladu je * katalyzátor:

* • o ¤ o * o * • * o ¤ • → • → o → o • • ¤o

Tuto techniku ​​lze použít pro tři kolíčky v řadě, pro 2x3 bloky a pro L vzor se 6 kolíčky (3 jednosměrné a 4 kolmé).

Existují hry, které začínají dvěma prázdnými pozicemi a končí dvěma kolíky na těchto pozicích. Je také možné začít na jedné předvolené pozici a skončit na jiné předvolené pozici. Na anglické šachovnici může být prázdná jamka kdekoli a hra musí skončit na stejné pozici nebo na jedné ze tří dalších povolených pozic. Pokud tedy počáteční prázdné pole bylo v bodě a , hra by měla skončit s jedním kolíčkem na pozicích a , p , O nebo C .

Učíme se hrát solitaire

Kompletní analýzu hry naleznete v tématu Vítězné cesty pro vaše matematické hry ( ISBN 0-12-091102-7 ve Velké Británii a ISBN 1-56881-144-6 v USA) (svazek 4, druhé vydání). Kniha zavádí zápis zvaný pagoda function , který je mocným nástrojem pro prokázání nemožnosti řešení daného (zobecněného) solitérního problému. Problém nalezení takové funkce je formulován jako celočíselný problém lineárního programování (viz Kiyomi a Matsui 2001). Uehara a Iwata (1990) studovali zobecněné Hi-Q problémy, které jsou ekvivalentní osamělým problémům, a ukázali, že jsou NP-úplné . Avis a Deza (1996) formulovali problém solitéru jako kombinatorický optimalizační problém a diskutovali o vlastnosti domény proveditelných řešení nazývané solitérní kužel. Kiyomi a Matsui (Kiyomi, Matsui, 2001) navrhli účinnou metodu pro řešení problémů s tasemnicí.

Nepublikovaná studie z roku 1989 o zobecněné verzi hry na anglickém plánu ukázala, že každý proveditelný problém v zobecněné hře má 2 9 různých řešení, s výjimkou symetrie, protože anglická deska obsahuje 9 různých podčtverců 3x3. Tato studie stanovila spodní hranici velikosti možných problémů „obrácených pozic“, při kterých se původně obsazené díry stávají obsazenými a naopak. Každé řešení takového problému se musí skládat minimálně z 11 tahů, bez ohledu na přesnou formulaci problému.

Algebra může být použita k prokázání, že existuje pouze 5 pevných bodů, kde může hra skončit úspěšně s jedním kolíčkem [2] .

Řešení pro anglickou verzi hry

Nejkratší řešení standardní anglické verze hry je 18 tahů, které počítají více skoků v jednom tahu:

Řešení bylo nalezeno v roce 1912 Ernestem Bergholtem a jako nejkratší se ukázalo Johnem Beasleym v roce 1964 [3] .

Stejné řešení můžeme vidět na [4] , kde se také zavádí Wolstenholmeův zápis, který má usnadnit zapamatování řešení.

Další řešení jsou uvedena v následujícím seznamu. Seznam má formát

počáteční poloha: koncová poloha=

Dále následují dvojice: kolík a pozice, do které se pohybuje. Dvojice jsou odděleny čárkou nebo lomítkem (lomítko je umístěno jako konec skupiny tahů)

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,ox x: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/Ox j: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/Jj i: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/Ki e: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,xe d: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/pd b:b=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp, vůl/xe/AI/BJ,JH,Hl,lj,jb b:x=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp, vůl/xe/AI/BJ,JH,Hl,lj,př a: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/ia a: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 na standardní anglickou verzi solitaire

Místo, kde může hra skončit, je střed, nebo jeden ze středů okrajů, a tam musíme být posledním tahem.

Níže je uvedena tabulka počtu B možných pozic po n tahech a počet O nepřítomnosti X tahů, pozic, ve kterých není možné pokračovat.

Pokud lze polohu získat rotací nebo zrcadlením, je považována za identickou.

n VP ACH
jeden jeden 0
2 2 0
3 osm 0
čtyři 39 0
5 171 0
6 719 jeden
7 2757 0
osm 9751 0
9 31 312 0
deset 89 927 jeden
n VP ACH
jedenáct 229 614 jeden
12 517 854 0
13 1 022 224 5
čtrnáct 1 753 737 deset
patnáct 2 598 215 7
16 3 312 423 27
17 3 626 632 47
osmnáct 3 413 313 121
19 2765623 373
dvacet 1 930 324 925
n VP ACH
21 1 160 977 1972
22 600 372 3346
23 265 865 4356
24 100 565 4256
25 32 250 3054
26 8688 1715
27 1917 665
28 348 182
29 padesáti 39
třicet 7 6
n VP ACH
31 2 2

Vzhledem k tomu, že maximální počet pozic pro každý tah nepřesahuje 3626632 a počet tahů je 31, moderní počítače mohou snadno vypočítat všechny pozice v rozumném čase.

Výše uvedené sekvence „VP“ jsou uvedeny v OEIS pod číslem A112737 [5] . Všimněte si, že celkový počet dosažitelných pozic (součet posloupnosti) je 23 475 688 [5] , zatímco celkový počet možných pozic je 2 33 nebo zhruba 2 33 /8 ~ 1 miliarda, vezmeme-li v úvahu symetrii. Tedy pouze asi 2,2 % všech možných pozic na šachovnici je dosažitelných, pokud začínáte z prázdného středu.

Na šachovnici můžete získat všechny možné pozice. Výsledky uvedené v tabulce lze získat pomocí sady nástrojů mcrl2 (viz příklad peg_solitaire v balíčku).

n VP
jeden jeden
2 čtyři
3 12
čtyři 60
5 296
6 1338
7 5648
osm 21 842
n VP
9 77 559
deset 249 690
jedenáct 717 788
12 1 834 379
13 4 138 302
čtrnáct 8 171 208
patnáct 14 020 166
16 20 773 236
n VP
17 26 482 824
osmnáct 28 994 876
19 27 286 330
dvacet 22 106 348
21 15 425 572
22 9 274 496
23 4 792 664
24 2 120 101
n VP
25 800 152
26 255 544
27 68 236
28 14 727
29 2529
třicet 334
31 32
32 5

Řešení pro evropskou variantu hry

existují 3 počáteční nekongruentní pozice, které mají řešení. To:

jeden)

0 1 2 3 4 5 6 0 o • • jeden • • • • • 2 • • • • • • • • 3 • • • • • • • • čtyři • • • • • • • • 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 • • • • • • • • čtyři • • • • • • • • 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 • • • jeden • • • • • 2 • • • o • • • 3 • • • • • • • • čtyři • • • • • • • • 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]

Možnosti desky

Solitaire se hraje i na jiných deskách, i když tyto dva jsou nejoblíbenější. Deska může být trojúhelníková, s pohyby ve třech směrech.

Obvykle má trojúhelníková varianta pět otvorů na každé straně. Řešení, ve kterém poslední kolík skončí v původně prázdném poli, není možné ve třech centrálních bodech. Problém s prázdným polem v rohu lze vyřešit deseti tahy, ale pokud se prázdné pole nachází ve středu strany, lze jej vyřešit devíti tahy (Bell 2008):

Viz také

Poznámky

  1. ↑ Sovětská logická hra Jóga (70. léta) . Hra na schovávanou. Datum přístupu: 27. května 2020.
  2. ↑ Matematika a brainvita . Datum přístupu: 30. prosince 2014. Archivováno z originálu 23. prosince 2014.
  3. ↑ Viz Beasleyho důkaz ve Winning Ways for your Mathematical Plays , svazek 4 (druhé vydání).
  4. ↑ Popis řešení (nepřístupný odkaz) . Datum přístupu: 30. prosince 2014. Archivováno z originálu 21. února 2015. 
  5. ↑ 1 2 OEIS sekvence A112737 = Na standardním 33-jamkovém kolíčkovém solitérním prkně je počet odlišných pozic na prkně po n skocích (počínaje středem)

Literatura

Odkazy