Solitaire (spel)

Solitaire  är ett brädspel för en spelare där pinnar byts ut på en bräda med hål. Vissa kit använder bollar och skårade brädor. I USA heter spelet Peg Solitaire (peg solitaire), och namnet Solitaire syftar på solitaire. I Storbritannien är spelet känt som Solitaire (patiens) och kortspelet heter Patience ( patiens ). På vissa ställen, särskilt Indien , heter spelet Brainvita . I Sovjetunionen producerades ett pussel som heter Yoga [1] .

Det första omnämnandet av spelet kan hittas i Ludvig XIV :s hov 1697. En gravyr av Claude Auguste Bereille Anne de Roan Chabot, Princess de Soubise , som föreställer en prinsessa som spelar solitär, markeras i år. I augusti 1697 publicerades en beskrivning av styrelsen, regler och exempel på problem i den franska litterära tidskriften Mercure galant . Detta är det första kända omnämnandet av spelet i tryck.

I ett standardspel är hela fältet fyllt med pinnar, med undantag för det centrala hålet. Målet med spelet är att befria hela brädet från pinnen, och lämna den sista pinnen i mitten av brädet.

Styrelse

Det finns två traditionella brädor att spela med ('.' som startpinnen, 'o' som det tomma hålet):

engelsk Europeiska
• • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • •

Spel

Ett lagligt drag är att hoppa en pinne genom en intilliggande pinne till ett fritt hål omedelbart efter den andra pinnen (som i dam, men rörelsen är vertikal eller horisontell, du kan inte flytta diagonalt), sedan tas den hoppade pinnen bort.

Symboler i diagrammen nedan:
• tapp i hål
* tapp som flyttas
o  tomt hål
¤ hål från vilket rörelsen gjordes
* ändläge för pinnen
o hål för borttagen pinne.

Sedan är de lagliga stegen i alla fyra riktningarna:

* • o → ¤ o * hoppa höger o • * → * o ¤ hoppa till vänster * ¤ • → o hoppa ner o * o * • → o hoppa upp * ¤

På den engelska brädet kan de tre första dragen vara:

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

Strategi

Det är lätt att gå fel och upptäcka att två eller tre tomma hål skiljer en ensam pinne åt. Många människor har inte kunnat lösa problemet.

Det finns många olika lösningar för ett standardproblem, och för att beskriva dem kommer vi att ge hålens bokstavsbeteckningar:

engelsk europeisk abcabc defydefz ghijklmghijklm nopx PON nopx PON MLKJIHGMLKJIHG FEDZFEDY CBACBA

Spegelbeteckningen på fälten används bland annat för att på den europeiska brädet i ett av familjen av alternativa spel börjar spelet med något hål på en godtycklig plats och måste sluta i spegelhålet. På den engelska brädan börjar och slutar alternativa spel i samma hål.

I den europeiska versionen av spelet finns det ingen lösning med en initial tom ruta i mitten, såvida inte diagonala drag är tillåtna. Detta är lätt att förstå om man tar hänsyn till Hans Zantemas argument. Låt oss markera tavlans positioner med bokstäverna A, B och C enligt följande:

ABC ABCAB ABCABCA BCABCAB CABCABC BCABC ABC

Vi kommer att räkna antalet pinnar i positioner av varje typ. Om den initiala tomma positionen är i mitten är antalet A-positioner 12, B-positionerna är också 12 (totalt 13, men en är ledig), antalet C-positioner är också 12. Efter varje drag är antalet Pinnarna i grupp A minskar eller ökar med en, samma sak händer med positionerna för grupperna B och C. Efter ett jämnt antal drag är alltså alla dessa tre tal jämna, och efter ett udda tal är de udda. Den slutliga positionen, i vilken endast en pinne återstår, kan alltså inte erhållas - gruppen där pinnen hamnar kommer att ha summan ett, medan de andra två måste ha summan noll.

Det finns dock några andra konfigurationer där ett fritt hål kan föras till en enda tapp.

En användbar taktik för att lösa pusslet är att dela upp hela brädan i trillingar, och sedan tas trillingarna bort med en extra pinne, en katalysator. I exemplet ovan är * katalysatorn:

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

Denna teknik kan användas för tre pinnar i rad, för 2x3 block, och för ett L-mönster med 6 pinnar (3 envägs och 4 vinkelräta).

Det finns spel som börjar med två tomma positioner och slutar med två pinnar i dessa positioner. Det är också möjligt att börja på en förvald position och avsluta vid en annan förvald position. På den engelska brädet kan ett tomt hål vara var som helst, och spelet måste sluta i samma position, eller i någon av de tre ytterligare tillåtna positionerna. Så om det initiala tomma fältet var vid punkt a , bör spelet sluta med en enda pinne vid positionerna a , p , O eller C .

Lära sig spela patiens

För en fullständig analys av spelet, se Vinnande sätt för dina matematiska spel ( ISBN 0-12-091102-7 i Storbritannien och ISBN 1-56881-144-6 i USA) (volym 4, andra upplagan). Boken introducerar en notation som kallas pagodfunktionen , som är ett kraftfullt verktyg för att bevisa omöjligheten att lösa ett givet (generaliserat) patiensproblem. Problemet med att hitta en sådan funktion är formulerat som ett heltalslinjärt programmeringsproblem (se Kiyomi och Matsui 2001). Uehara och Iwata (1990) studerade generaliserade Hi-Q-problem som är likvärdiga med ensamma problem och visade att de var NP-kompletta . Avis och Deza (1996) formulerade patiensproblemet som ett kombinatoriskt optimeringsproblem och diskuterade en egenskap hos domänen av genomförbara lösningar som kallas patienskonen. Kiyomi och Matsui (Kiyomi, Matsui, 2001) föreslog en effektiv metod för att lösa problem med bandmask.

En opublicerad studie från 1989 om en generaliserad version av spelet på den engelska brädet visade att alla möjliga problem i det generaliserade spelet har 29 olika lösningar, exklusive symmetri, eftersom den engelska brädet innehåller 9 olika 3x3-delkvadrater. Denna studie gav en nedre gräns för storleken på möjliga problem med "omvända positioner" där ursprungligen upptagna hål blir upptagna och vice versa. Varje lösning på ett sådant problem måste bestå av minst 11 drag, oavsett den exakta formuleringen av problemet.

Algebra kan användas för att bevisa att det bara finns 5 fasta punkter där spelet kan sluta framgångsrikt med en pinne [2] .

Lösningar för den engelska versionen av spelet

Den kortaste lösningen av den engelska standardversionen av spelet är 18 drag, räknat flera hopp i ett drag:

Lösningen hittades 1912 av Ernest Bergholt och visade sig vara den kortaste lösningen av John Beasley 1964 [3] .

Samma lösning kan ses på [4] , som också introducerar Wolstenholme-notationen, som är utformad för att göra det lättare att komma ihåg lösningen.

Andra lösningar ingår i följande lista. Listan har formatet

startposition: slutposition=

Därefter kommer paren: pinnen och positionen den flyttar till. Par skiljs åt med ett kommatecken eller ett snedstreck (snedstrecket placeras som slutet på en grupp av drag)

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,ex 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

En attack på den engelska standardversionen av solitaire

Platsen där spelet kan sluta är mitten, eller en av mitten av kanterna, och det sista draget måste vi vara där.

Nedan finns en tabell över antalet möjliga B - positioner efter n drag, och antalet O för frånvaron av X -drag, positioner där fortsättning är omöjlig.

Om en position kan erhållas genom rotation eller spegling anses den vara identisk.

n VP ÅH
ett ett 0
2 2 0
3 åtta 0
fyra 39 0
5 171 0
6 719 ett
7 2757 0
åtta 9751 0
9 31 312 0
tio 89 927 ett
n VP ÅH
elva 229 614 ett
12 517 854 0
13 1 022 224 5
fjorton 1 753 737 tio
femton 2 598 215 7
16 3 312 423 27
17 3 626 632 47
arton 3 413 313 121
19 2765623 373
tjugo 1 930 324 925
n VP ÅH
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 femtio 39
trettio 7 6
n VP ÅH
31 2 2

Eftersom det maximala antalet positioner för varje drag inte överstiger 3626632, och antalet drag är 31, kan moderna datorer enkelt beräkna alla positioner inom rimlig tid.

Ovanstående sekvenser av "VP" är listade i OEIS under numret A112737 [5] . Observera att det totala antalet nåbara positioner (summan av sekvensen) är 23 475 688 [5] , medan det totala antalet möjliga positioner är 2 33 , eller ungefär 2 33 /8 ~ 1 miljard om symmetri tas med i beräkningen. Således är endast cirka 2,2% av alla möjliga positioner på brädet möjliga om man startar från en tom center.

Du kan få alla möjliga positioner på tavlan. Resultaten som visas i tabellen kan erhållas med hjälp av verktygsuppsättningen mcrl2 (se exemplet peg_solitaire i paketet).

n VP
ett ett
2 fyra
3 12
fyra 60
5 296
6 1338
7 5648
åtta 21 842
n VP
9 77 559
tio 249 690
elva 717 788
12 1 834 379
13 4 138 302
fjorton 8 171 208
femton 14 020 166
16 20 773 236
n VP
17 26 482 824
arton 28 994 876
19 27 286 330
tjugo 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
trettio 334
31 32
32 5

Lösningar för den europeiska varianten av spelet

det finns 3 initiala inkongruenta positioner som har lösningar. Det:

ett)

0 1 2 3 4 5 6 0 o • • ett • • • • • 2 • • • • • • • 3 • • • • • • • fyra • • • • • • • 5 • • • • • 6 • • •

Möjlig lösning: [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 • • • • • • • fyra • • • • • • • 5 • • • • • 6 • • •

Möjlig lösning: [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]

och 3)

0 1 2 3 4 5 6 0 • • • ett • • • • • 2 • • • o • • • 3 • • • • • • • fyra • • • • • • • 5 • • • • • 6 • • •

Möjlig lösning: [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]

Styrelsealternativ

Solitaire spelas även på andra brädor, även om dessa två är de mest populära. Brädan kan vara triangulär, med rörelser i tre riktningar.

Vanligtvis har den triangulära varianten fem hål per sida. En lösning där den sista pinnen hamnar i ett initialt tomt fält är inte möjlig vid de tre centrala punkterna. Ett problem med en tom ruta i hörnet kan lösas i tio drag, men om den tomma rutten är placerad i mitten av sidan kan det lösas i nio drag (Bell 2008):

Se även

Anteckningar

  1. ↑ Sovjetiskt pusselspel Yoga (70-tal) . Tittut. Tillträdesdatum: 27 maj 2020.
  2. ↑ Matematik och brainvita . Datum för åtkomst: 30 december 2014. Arkiverad från originalet 23 december 2014.
  3. ↑ Se Beasleys bevis i Winning Ways for your Mathematical Plays , Volym 4 (andra upplagan).
  4. ↑ Beskrivning av lösningen (otillgänglig länk) . Datum för åtkomst: 30 december 2014. Arkiverad från originalet 21 februari 2015. 
  5. ↑ 1 2 OEIS Sekvens A112737 = På standard 33-håls korsformade peg-patiensbräda, antalet distinkta brädpositioner efter n hopp (börjar med mitten ledigt)

Litteratur

Länkar