Solitaire er et brætspil for én spiller, hvor pløkker byttes på et bræt med huller. Nogle sæt bruger bolde og brædder med kærv. I USA hedder spillet Peg Solitaire (peg solitaire), og navnet Solitaire refererer til solitaire. I Storbritannien er spillet kendt som Solitaire (kabale), og kortspillet hedder Patience ( kabale ). Nogle steder, især Indien , hedder spillet Brainvita . I USSR blev et puslespil kaldet Yoga [1] fremstillet .
Den første omtale af spillet kan findes i Ludvig XIV 's hof i 1697. En gravering af Claude Auguste Bereille Anne de Roan Chabot, Prinsesse de Soubise , som forestiller en prinsesse, der spiller kabale, er markeret i år. I august 1697 blev en beskrivelse af bestyrelsen, regler og eksempler på problemer offentliggjort i det franske litterære magasin Mercure galant . Dette er den første kendte omtale af spillet på tryk.
I et standardspil er hele feltet fyldt med pløkker, med undtagelse af det centrale hul. Målet med spillet er at frigøre hele brættet fra tappen, og efterlade den sidste stift i midten af brættet.
Der er to traditionelle brædder at spille med ('.' som startpinden, 'o' som det tomme hul):
| engelsk | europæisk | ||
|---|---|---|---|
| • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • | • • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • |
Et lovligt træk er at hoppe en pind gennem en tilstødende pind til et frit hul umiddelbart efter den anden pind (som i dam, men bevægelsen er lodret eller vandret, du kan ikke flytte diagonalt), så fjernes den hoppede pind.
Symboler i diagrammerne nedenfor:
• pind i hul
* pind flyttes
o tomt hul
¤ hul, hvorfra der blev flyttet
* endeposition af pind
o hul af fjernet pind.
Så er de juridiske træk i alle fire retninger:
* • o → ¤ o * hop til højre o • * → * o ¤ hop til venstre * ¤ • → o hoppe ned o * o * • → o spring op * ¤På det engelske bræt kan de første tre træk være:
• • • • • • • • • • • • * • • ¤ • • o • • * • • • • • • • • • • o • • • • ¤ o * • • • • oo o • • • • • • o • • • • • * • • • • • • • • • • • ¤ • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •Det er nemt at gå den forkerte vej og opdage, at to eller tre tomme huller adskiller en enlig pind. Mange mennesker har ikke været i stand til at løse problemet.
Der findes mange forskellige løsninger på et standardproblem, og for at beskrive dem vil vi give hullerne bogstavbetegnelser:
engelsk europæisk abcabc defydefz ghijklmghijklm nopx PON nopx PON MLKJIHGMLKJIHG FEDZFEDY CBACBAFelternes spejlbetegnelse bruges blandt andet, fordi spillet på det europæiske bord i et af familien af alternative spil starter med et eller andet hul på et vilkårligt sted og skal ende i spejlhullet. På det engelske bræt begynder og slutter alternative spil i samme hul.
I den europæiske version af spillet er der ingen løsning med et indledende tomt felt i midten, medmindre diagonale træk er tilladt. Dette er let at forstå, hvis man tænker på Hans Zantemas argumenter. Lad os markere placeringerne af tavlen med bogstaverne A, B og C som følger:
ABC ABCAB ABCABCA BCABCAB CABCABC BCABC ABCVi tæller antallet af pinde i positioner af hver type. Hvis den indledende tomme position er i midten, er antallet af A-positioner 12, B-positionerne er også 12 (i alt 13, men en er ledig), antallet af C-positioner er også 12. Efter hvert træk er antallet af pinde i gruppe A falder eller øges med én, det samme sker med positionerne i gruppe B og C. Efter et lige antal træk er alle disse tre tal således lige, og efter et ulige tal er de ulige. Den endelige position, hvor der kun er én pind tilbage, kan således ikke opnås - gruppen hvor pinden ender vil have summen af én, mens de to andre skal have summen nul.
Der er dog nogle andre konfigurationer, hvor et frit hul kan bringes til en enkelt pind.
En nyttig taktik til at løse puslespillet er at dele hele brættet i trillinger, og derefter fjernes trillingerne med en ekstra pind, en katalysator. I eksemplet ovenfor er * katalysatoren:
* • o ¤ o * o * • * o ¤ • → • → o → o • • ¤oDenne teknik kan bruges til tre pinde i træk, til 2x3 blokke og til et L-mønster på 6 pinde (3 envejs og 4 vinkelrette).
Der er spil, der starter med to tomme positioner og slutter med to pinde i disse positioner. Det er også muligt at starte ved én forudvalgt position og slutte ved en anden forudvalgt position. På det engelske bræt kan et tomt hul være hvor som helst, og spillet skal ende i samme position, eller i en af de tre yderligere tilladte positioner. Så hvis det indledende tomme felt var ved punkt a , skulle spillet slutte med en enkelt pind på positionerne a , p , O eller C .
For en komplet analyse af spillet, se Winning Ways for your Mathematical Plays ( ISBN 0-12-091102-7 i Storbritannien og ISBN 1-56881-144-6 i USA) (bind 4, anden udgave). Bogen introducerer en notation kaldet pagodefunktionen , som er et kraftfuldt værktøj til at bevise umuligheden af at løse et givet (generaliseret) kabaleproblem. Problemet med at finde en sådan funktion er formuleret som et heltals lineært programmeringsproblem (se Kiyomi og Matsui 2001). Uehara og Iwata (1990) undersøgte generaliserede Hi-Q-problemer, der svarer til ensomme problemer, og viste, at de var NP-komplette . Avis og Deza (1996) formulerede kabaleproblemet som et kombinatorisk optimeringsproblem og diskuterede en egenskab ved domænet af mulige løsninger kaldet solitairekeglen. Kiyomi og Matsui (Kiyomi, Matsui, 2001) foreslog en effektiv metode til at løse bændelormproblemer.
En upubliceret undersøgelse fra 1989 af en generaliseret version af spillet på den engelske bræt viste, at ethvert muligt problem i det generaliserede spil har 29 forskellige løsninger, eksklusive symmetri, da det engelske bræt indeholder 9 forskellige 3x3 underkvadrater. Denne undersøgelse gav en nedre grænse for størrelsen af mulige problemer med 'omvendte positioner', hvor oprindeligt besatte huller bliver besat og omvendt. Enhver løsning på et sådant problem skal bestå af mindst 11 træk, uanset problemets præcise formulering.
Algebra kan bruges til at bevise, at der kun er 5 faste punkter, hvor spillet kan afsluttes med én pind [2] .
Den korteste løsning af den engelske standardversion af spillet er 18 træk, der tæller flere hop i et træk:
| Korteste løsning på engelsk peg solitaire |
|---|
|
eks lj ck
• • • • • • • • • • • ¤
• * • • ¤ • • • o • • o 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
• åååååååååååååååååååååååååååååååååååååå _ _
• • • • • 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 oooooo
• 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 o oo
åååååååå
Rækkefølgen af nogle træk kan ændres. Bemærk, at hvis du bruger * til huller og o til pløkker, kan du løse puslespillet ved at arbejde baglæns fra det sidste billede og arbejde dig frem til det første. Dette vil dog kræve mere end 18 træk. |
Løsningen blev fundet i 1912 af Ernest Bergholt og viste sig at være den korteste løsning af John Beasley i 1964 [3] .
Den samme løsning kan ses på [4] , som også introducerer Wolstenholme-notationen, som er designet til at gøre det nemmere at huske løsningen.
Andre løsninger er inkluderet i den følgende liste. Listen har formatet
startposition: slutposition=Dernæst kommer parrene: pinden og den position, den bevæger sig til. Par adskilles med et komma eller en skråstreg (skråstregen placeres som slutningen af en gruppe træk)
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/dpStedet, hvor spillet kan slutte, er midten, eller en af midten af kanterne, og det sidste træk, vi skal være der.
Nedenfor er en tabel over antallet af B mulige positioner efter n træk, og tallet O for fraværet af X træk, positioner hvor fortsættelse er umulig.
Hvis en position kan opnås ved rotation eller spejling, anses den for at være identisk.
|
|
|
|
Da det maksimale antal positioner for hvert træk ikke overstiger 3626632, og antallet af træk er 31, kan moderne computere nemt beregne alle positioner inden for rimelig tid.
Ovenstående sekvenser af "VP" er opført i OEIS under nummeret A112737 [5] . Bemærk, at det samlede antal tilgængelige positioner (summen af sekvensen) er 23.475.688 [5] , mens det samlede antal mulige positioner er 2 33 , eller omtrent 2 33 /8 ~ 1 milliard, hvis symmetri tages i betragtning. Således er kun omkring 2,2% af alle mulige positioner på bestyrelsen opnåelige, hvis man starter fra et tomt center.
Du kan få alle mulige positioner på tavlen. Resultaterne vist i tabellen kan opnås ved hjælp af mcrl2-værktøjssættet (se peg_solitaire-eksemplet i pakken).
|
|
|
|
der er 3 indledende inkongruente positioner, der har løsninger. Det:
en)
0 1 2 3 4 5 6 0 o • • en • • • • • 2 • • • • • • • 3 • • • • • • • fire • • • • • • • 5 • • • • • 6 • • •Mulig 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 • • • • • • • fire • • • • • • • 5 • • • • • 6 • • •Mulig 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]
og 3)
0 1 2 3 4 5 6 0 • • • en • • • • • 2 • • • o • • • 3 • • • • • • • fire • • • • • • • 5 • • • • • 6 • • •Mulig 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]
Solitaire spilles også på andre brædder, selvom disse to er de mest populære. Brættet kan være trekantet, med bevægelser i tre retninger.
Normalt har den trekantede variant fem huller pr. side. En løsning, hvor den sidste pind ender i et oprindeligt tomt felt, er ikke mulig på de tre centrale punkter. Et problem med et tomt felt i hjørnet kan løses i ti træk, men hvis det tomme felt er placeret i midten af siden, kan det løses i ni træk (Bell 2008):
| Den korteste løsning af den trekantede variant |
|---|
|
* = pinden, der gør det næste træk; ¤ = hul frigjort ved træk; o = pløkker fjernet (over hoppet over); * = hul, hvori pinden endte efter træk; • • • * ¤ • • • • • • • * 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 oo o o o * * o • o ¤ ¤ o • oooo * oooo ¤ oo * oo |