Pasziánsz (játék)

A Solitaire  egy egyjátékos társasjáték , amelyben a lyukakat tartalmazó deszkán csapokat cserélnek. Egyes készletek golyókat és rovátkolt táblákat használnak. Az Egyesült Államokban a játék neve Peg Solitaire (Peg Solitaire), a Solitaire név pedig a pasziánszra utal. Az Egyesült Királyságban a játék Solitaire (pasziánsz) néven ismert, a kártyajáték pedig Patience ( pasziánsz ). Egyes helyeken, különösen Indiában , a játék neve Brainvita . A Szovjetunióban a Jóga [1] nevű rejtvényt készítettek .

A játék első említése XIV. Lajos udvarában található 1697-ben. Ebben az évben Claude Auguste Bereille Anne de Roan Chabot, Soubise hercegnő metszetét , amely egy pasziánszozni játszó hercegnőt ábrázol. 1697 augusztusában a Mercure galant című francia irodalmi folyóiratban megjelent a tábla leírása, a szabályok és a problémák példái . Ez a játék első ismert említése nyomtatásban.

Egy szabványos játékban a központi lyuk kivételével az egész mezőt csapok töltik ki. A játék célja, hogy az egész táblát kiszabadítsa a csapból, az utolsó szöget a tábla közepén hagyva.

Board

Két hagyományos táblával lehet játszani ("." mint kezdőcsap, "o" mint üres lyuk):

angol európai
• • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • •

Játék

Legális lépés az, hogy egy szöget a szomszédos csapon keresztül közvetlenül a második ütő után szabad lyukba ugranak (mint a dáma esetén, de a mozgás függőleges vagy vízszintes, átlósan nem mozoghat), majd az ugrott szöget eltávolítják.

Szimbólumok az alábbi ábrákon:
• csap a lyukban
* a csap mozgatva
o  üres lyuk
¤ lyuk, ahonnan mozgás történt
* a csap véghelyzete
o az eltávolított csap furata.

Ezután a jogi lépések mind a négy irányban a következők:

* • o → ¤ o * ugrás jobbra o • * → * o ¤ balra ugrás * ¤ • → o ugrás le o * o * • → o felugrás * ¤

Az angol táblán az első három lépés lehet:

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

Stratégia

Könnyű rossz irányba menni, és rájönni, hogy két vagy három üres lyuk választ el egymástól egy magányos csapot. Sokan nem tudták megoldani a problémát.

Egy szabványos problémára sokféle megoldás létezik, ezek leírásához a lyukakat betűjelekkel látjuk el:

angol európai abcabc defydefz ghijklmghijklm nopx PON nopx PON MLKJIHGMLKJIHG FEDZFEDY CBACBA

A mezők tükörmegjelölését többek között azért használják, mert az európai táblán az alternatív játékok egyik családjában a játék tetszőleges helyen lévő lyukkal kezdődik, és a tükörlyukban kell végződnie. Az angol táblán az alternatív játékok ugyanabban a lyukban kezdődnek és végződnek.

A játék európai változatában nincs olyan megoldás, ahol a kezdeti üres négyzet a közepén van, kivéve, ha az átlós mozgások megengedettek. Ez könnyen érthető, ha figyelembe vesszük Hans Zantema érveit. Jelöljük a tábla pozícióit A, B és C betűkkel az alábbiak szerint:

ABC ABCAB ABCABCA BCABCAB CABCABC BCABC ABC

Megszámoljuk a csapok számát az egyes típusok pozícióiban. Ha a kezdeti üres pozíció középen van, az A pozíciók száma 12, a B pozíciók is 12 (összesen 13, de egy szabad), a C pozíciók száma szintén 12. Minden lépés után a Az A csoport csapjai eggyel csökkennek vagy nőnek, ugyanez történik a B és C csoport pozícióival is. Így páros számú lépés után ez a három szám páros, páratlan után pedig páratlan. Így a végső pozíciót, amelyben csak egy csap marad, nem lehet megszerezni - a csoport, ahol a peg végül kikerül, egy összegű lesz, míg a másik kettőnek nullának kell lennie.

Vannak azonban más konfigurációk is, amelyekben egy szabad lyukat egyetlen csaphoz lehet hozni.

Hasznos taktika a rejtvény megoldásához, hogy az egész táblát hármasokra osztjuk, majd a hármasokat egy plusz pöcökkel, katalizátorral távolítjuk el. A fenti példában a * a katalizátor:

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

Ez a technika egymás után három csaphoz, 2x3 tömbhöz és 6 csapból álló L mintázathoz használható (3 egyirányú és 4 merőleges).

Vannak olyan játékok, amelyek két üres pozícióval kezdődnek, és ezeken a pozíciókon két pöccsel végződnek. Lehetőség van arra is, hogy egy előre kiválasztott pozícióban kezdjen, és egy másik előre kiválasztott pozícióban fejezze be. Az angol táblán egy üres lyuk bárhol lehet, és a játéknak ugyanabban a pozícióban kell végződnie, vagy a további három megengedett pozíció valamelyikében. Tehát, ha a kezdeti üres mező az a pontban volt , a játéknak egyetlen pöccsel kell végződnie az a , p , O vagy C pozíciókban .

Megtanulni pasziánszozni

A játék teljes elemzéséhez lásd: Winning Ways for your Mathematical Plays ( ISBN 0-12-091102-7 az Egyesült Királyságban és ISBN 1-56881-144-6 az Egyesült Államokban) (4. kötet, második kiadás). A könyv bemutatja a pagoda függvénynek nevezett jelölést , amely hatékony eszköz egy adott (általánosított) pasziánsz probléma megoldásának lehetetlenségének bizonyítására. Az ilyen függvény megtalálásának problémája egész szám lineáris programozási problémaként van megfogalmazva (lásd Kiyomi és Matsui 2001). Uehara és Iwata (1990) általánosított Hi-Q problémákat vizsgáltak, amelyek egyenértékűek a magányos problémákkal, és kimutatták, hogy NP-teljesek . Avis és Deza (1996) a pasziánsz problémát kombinatorikus optimalizálási problémaként fogalmazta meg, és a megvalósítható megoldások tartományának egy tulajdonságát tárgyalta, amelyet a pasziánsz kúpnak neveznek. Kiyomi és Matsui (Kiyomi, Matsui, 2001) egy hatékony módszert javasoltak a galandféreggel kapcsolatos problémák megoldására.

Egy 1989-ben publikálatlan tanulmány a játék általánosított változatáról az angol táblán azt mutatta, hogy az általánosított játékban minden megvalósítható problémának 2 9 különböző megoldása van, kivéve a szimmetriát, mivel az angol tábla 9 különböző 3x3-as résznégyzetet tartalmaz. Ez a tanulmány alsó korlátot adott a lehetséges „fordított pozíciók” problémáinak méretére, amelyekben az eredetileg foglalt lyukak foglaltakká válnak, és fordítva. Egy ilyen probléma megoldásának legalább 11 mozdulatból kell állnia, függetlenül a probléma pontos megfogalmazásától.

Az algebra segítségével be lehet bizonyítani, hogy csak 5 fix pont van, ahol a játék sikeresen véget érhet egy pöccsel [2] .

Megoldások a játék angol verziójához

A játék standard angol verziójának legrövidebb megoldása 18 lépés, több ugrást számolva egy lépésben:

A megoldást 1912-ben Ernest Bergholt találta meg, és 1964-ben John Beasley bizonyult a legrövidebb megoldásnak [3] .

Ugyanezt a megoldást láthatjuk a [4] oldalon is, amely bevezeti a Wolstenholme-jelölést is, amely a megoldás könnyebb megjegyezését hivatott megkönnyíteni.

A többi megoldást a következő lista tartalmazza. A listának megvan a formátuma

kezdőpozíció: véghelyzet=

Következnek a párok: a csap és az a pozíció, ahová mozog. A párokat vesszővel vagy perjellel választjuk el (a perjel egy lépéscsoport végeként kerül elhelyezésre)

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, ox/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, ox/xe/AI/BJ,JH,Hl,lj,pl 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

Támadás a pasziánsz standard angol verziója ellen

A hely, ahol a játék véget érhet, az a középpont, vagy a szélek egyik közepe, és az utolsó lépésben ott kell lennünk.

Az alábbiakban egy táblázat látható a lehetséges B pozíciók számáról n lépés után, és az O számról , ahol nincs X lépés, olyan pozíciók, amelyekben a folytatás nem lehetséges.

Ha egy pozíciót elforgatással vagy tükrözéssel lehet elérni, akkor azt azonosnak tekintjük.

n VP Ó
egy egy 0
2 2 0
3 nyolc 0
négy 39 0
5 171 0
6 719 egy
7 2757 0
nyolc 9751 0
9 31 312 0
tíz 89 927 egy
n VP Ó
tizenegy 229 614 egy
12 517 854 0
13 1 022 224 5
tizennégy 1 753 737 tíz
tizenöt 2 598 215 7
16 3 312 423 27
17 3 626 632 47
tizennyolc 3 413 313 121
19 2765623 373
húsz 1 930 324 925
n VP Ó
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 ötven 39
harminc 7 6
n VP Ó
31 2 2

Mivel az egyes mozdulatok maximális pozíciói száma nem haladja meg a 3626632-t, a lépések száma pedig 31, a modern számítógépek könnyen ésszerű időn belül ki tudják számítani az összes pozíciót.

A "VP" fenti szekvenciái az OEIS -ben A112737 számon szerepelnek [5] . Vegyük észre, hogy az elérhető pozíciók teljes száma (a sorozat összege) 23 475 688 [5] , míg a lehetséges pozíciók teljes száma 2 33 , vagyis nagyjából 2 33 /8 ~ 1 milliárd, ha a szimmetriát is figyelembe vesszük. Így a táblán az összes lehetséges pozíciónak csak körülbelül 2,2%-a érhető el, ha üres középről indulunk.

Minden lehetséges pozíciót megszerezhet a táblán. A táblázatban látható eredmények az mcrl2 eszközkészlettel érhetők el (lásd a peg_pasziánsz példát a csomagban).

n VP
egy egy
2 négy
3 12
négy 60
5 296
6 1338
7 5648
nyolc 21 842
n VP
9 77 559
tíz 249 690
tizenegy 717 788
12 1 834 379
13 4 138 302
tizennégy 8 171 208
tizenöt 14 020 166
16 20 773 236
n VP
17 26 482 824
tizennyolc 28 994 876
19 27 286 330
húsz 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
harminc 334
31 32
32 5

Megoldások a játék európai változatához

3 kezdeti inkongruens pozíció van, amelyeknek megoldásai vannak. Azt:

egy)

0 1 2 3 4 5 6 0 o • • egy • • • • • 2 • • • • • • • 3 • • • • • • • négy • • • • • • • 5 • • • • • 6 • • •

Lehetséges megoldás: [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 • • • • • • • négy • • • • • • • 5 • • • • • 6 • • •

Lehetséges megoldás: [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]

és 3)

0 1 2 3 4 5 6 0 • • • egy • • • • • 2 • • • o • • • 3 • • • • • • • négy • • • • • • • 5 • • • • • 6 • • •

Lehetséges megoldás: [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]

Tábla opciók

A pasziánszot más táblákon is játsszák, bár ez a kettő a legnépszerűbb. A tábla lehet háromszög alakú, három irányban mozoghat.

Általában a háromszög alakú változat oldalanként öt lyukkal rendelkezik. A három központi ponton nem lehetséges olyan megoldás, hogy a végső csap egy kezdetben üres mezőbe kerüljön. A sarokban lévő üres négyzet problémája tíz mozdulattal megoldható, de ha az üres mező az oldal közepén található, akkor kilenc mozdulattal megoldható (Bell 2008):

Lásd még

Jegyzetek

  1. ↑ Szovjet kirakós játék Jóga (70-es évek) . Kukucs. Hozzáférés időpontja: 2020. május 27.
  2. ↑ Matematika és brainvita . Hozzáférés időpontja: 2014. december 30. Az eredetiből archiválva : 2014. december 23.
  3. ↑ Lásd Beasley bizonyítékát a Winning Ways for your Mathematical Plays 4. kötetében (második kiadás).
  4. ↑ A megoldás leírása (elérhetetlen link) . Hozzáférés dátuma: 2014. december 30. Az eredetiből archiválva : 2015. február 21. 
  5. ↑ 1 2 OEIS szekvencia A112737 = A szabványos 33 lyukú, kereszt alakú pasziánsztáblán a különböző táblapozíciók száma n ugrás után (a középső ürestől kezdve)

Irodalom

Linkek