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.
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 • • • • • • • • • • • • • • • • • • |
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 • • • • • * • • • • • • • • • • • • • ¤ • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •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 CBACBAZrcadlové 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 ABCBudeme 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 • • ¤oTuto 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 .
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] .
Nejkratší řešení standardní anglické verze hry je 18 tahů, které počítají více skoků v jednom tahu:
Nejkratší řešení anglického peg solitaire |
---|
ex lj ck
• • • • • • • • • • • • ¤ •
* • • ¤ • • • o • • o o •
• • • • • • • o •
• • • o • • • • • * • • • • • • • • • • • • •
• • • • • • • • • • • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
Pf DP GI JH
• • o • • o • • o • • o
• o * • o • • o • • o •
• • • • o o • • • • • oo • • • • • oo • • • • • oo •
• • • • ¤ • • • • • • • • • • • • • • • • • •
• • • • • • • • • • • o • • • • • * o ¤ • • • ¤ o * o
• • • • • ¤ • • o • • o
• • • • • • • • • • • • •
mGI ik gi LJHljh
• • o • • o • • o • • o
• o • • o • • o • • o •
• • • • oo ¤ • • ¤ o * oo ¤ o * o • ooo * o o o o o
• • • • • • o • • • • • • o • • • • • • o • • • • • o o
• • • o * o o • • • o • oo • • • o • oo • ¤ o o o o o
• • o • • o • • o • • o
• • • • • • • • • • • • •
CK pF ACK Mgi
• • o • • o • • o • • o
• o • • o • • o • • o •
o • oooooo • oooooo • ooooo o o * oooo
• • • • • oo • • ¤ • • oo • • o • • oo o • o • • oo
• o * oooo • o o oooo • o * oooo ¤ o • oooo
o • o * • o o • oo • o
¤ • • o • • o o ¤ ooo
ackI dpFDPp ox
¤ o o ooooo
• o o ¤ ooooo
oo • o o oooo o oooooooooooo
o • o • o ooo • * o o ooo ¤ o * ooo
oo • o * oooo o o o ooooooooo
o • o o o o o oo
ooooooooo
Pořadí některých tahů lze změnit. Všimněte si, že pokud použijete * pro díry a o pro kolíky, můžete hádanku vyřešit tak, že budete postupovat od posledního obrázku a propracujete se k prvnímu. To však bude vyžadovat více než 18 tahů. |
Ř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/dpMí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.
|
|
|
|
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).
|
|
|
|
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]
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):
Nejkratší řešení trojúhelníkové varianty |
---|
* = kolík, který provede další tah; ¤ = otvor uvolněný pohybem; o = kolíky odstraněny (přeskočeno); * = díra, ve které kolík po tahu skončil; • • • * ¤ • • • • • • • * o ¤ • • • • • • * • • ¤ • • * o • • • • • • • • • • • • • • o • • * * • * * • o • • ¤ o * * • o * o ¤ • o • * o • o • • o • ooooo * * * * ¤ ¤ oooo o o o o * * o o o oo * oo ¤ ¤ • • ¤ o o o ooo * * oo • o o o o o o * * o • o ¤ ¤ o • oooo * oooo ¤ oo * oo |