Solitaire este un joc de masă pentru un singur jucător, în care cheile sunt schimbate pe o tablă cu găuri. Unele truse folosesc bile și scânduri crestate. În SUA, jocul se numește Peg Solitaire (peg solitaire), iar numele Solitaire se referă la solitaire. În Marea Britanie , jocul este cunoscut sub numele de Solitaire (solitaire), iar jocul de cărți se numește Patience ( solitaire ). În unele locuri, în special în India , jocul se numește Brainvita . În URSS, a fost produs un puzzle numit Yoga [1] .
Prima mențiune despre joc poate fi găsită la curtea lui Ludovic al XIV-lea în 1697. O gravură de Claude Auguste Bereille Anne de Roan Chabot, Prințesa de Soubise , care înfățișează o prințesă jucând solitaire, este marcată anul acesta. În august 1697, o descriere a consiliului, regulile și exemplele de probleme au fost publicate în revista literară franceză Mercure galant . Aceasta este prima mențiune cunoscută a jocului tipărită.
Într-un joc standard, întregul teren este umplut cu cuie, cu excepția găurii centrale. Scopul jocului este de a elibera întreaga tablă de pe picior, lăsând ultimul cuier în centrul tablei.
Există două scânduri tradiționale cu care să te joci ('.' ca picior de pornire, 'o' ca gaură goală):
Engleză | european | ||
---|---|---|---|
• • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • | • • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • |
O mișcare legală este să săriți un cuier printr-un cuier adiacent într-o gaură liberă imediat după al doilea cuier (ca la dame, dar mișcarea este verticală sau orizontală, nu vă puteți deplasa în diagonală), apoi cuiul sărit este îndepărtat.
Simboluri din diagramele de mai jos:
• cuiu în orificiu
* cuiu în curs de deplasare
o gaură goală
¤ gaură din care a fost efectuată mutarea
* poziția finală a cuiului
sau orificiul cuiului îndepărtat.
Apoi, mișcările legale în toate cele patru direcții sunt:
* • o → ¤ o * sari la dreapta o • * → * o ¤ sari la stânga * ¤ • → o sări în jos o * o * • → o sări în sus * ¤Pe tabla engleză, primele trei mutări pot fi:
• • • • • • • • • • • • • * • • ¤ • • o • • * • • • • • • • • • • • o • • • • ¤ o * • • • • oo o • • • • • • o • • • • • * • • • • • • • • • • • • ¤ • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •Este ușor să mergi pe o cale greșită și să descoperi că două sau trei găuri goale separă un cuier singur. Mulți oameni nu au reușit să rezolve problema.
Există multe soluții diferite pentru o problemă standard și pentru a le descrie, vom da denumirile literelor găurilor:
engleză europeană abcabc defydefz ghijklmghijklm nopx PON nopx PON MLKJIHGMLKJIHG FEDZFEDY CBACBADesemnarea în oglindă a câmpurilor este folosită, printre altele, deoarece pe tabla europeană într-unul din familia de jocuri alternative jocul începe cu o gaură într-un loc arbitrar și trebuie să se termine în gaura oglinzii. Pe tabla engleză, jocurile alternative încep și se termină în aceeași gaură.
În versiunea europeană a jocului, nu există o soluție cu un pătrat inițial gol în centru, cu excepția cazului în care sunt permise mișcări în diagonală. Acest lucru este ușor de înțeles dacă luăm în considerare argumentele lui Hans Zantema. Să marchem pozițiile tablei cu literele A, B și C, după cum urmează:
ABC ABCAB ABCABCA BCABCAB CABCABC BCABC ABCVom număra numărul de cuie în poziții de fiecare tip. Dacă poziția inițială goală este în centru, numărul pozițiilor A este 12, pozițiile B sunt și ele 12 (în total 13, dar una este liberă), numărul pozițiilor C este tot 12. După fiecare mișcare, numărul de cuiele grupului A se micșorează sau crește cu unul, același lucru se întâmplă și cu pozițiile grupelor B și C. Astfel, după un număr par de mișcări, toate aceste trei numere sunt pare, iar după un număr impar, sunt impare. Astfel, nu se poate obține poziția finală, în care rămâne doar un cuier - grupul în care ajunge cuiul va avea suma unu, în timp ce celelalte două trebuie să aibă suma zero.
Există, totuși, câteva alte configurații în care o gaură liberă poate fi adusă la un singur cui.
O tactică utilă pentru rezolvarea puzzle-ului este împărțirea întregii table în tripleți, iar apoi tripleții sunt îndepărtați cu un chel suplimentar, un catalizator. În exemplul de mai sus, * este catalizatorul:
* • o ¤ o * o * • * o ¤ • → • → o → o • • ¤oAceastă tehnică poate fi folosită pentru trei cuie la rând, pentru blocuri 2x3 și pentru un model în L de 6 chei (3 unidirecțional și 4 perpendiculare).
Există jocuri care încep cu două poziții goale și se termină cu două chei în acele poziții. De asemenea, este posibil să începeți dintr-o poziție preselectată și să se încheie la o altă poziție preselectată. Pe tabla engleză, o gaură goală poate fi oriunde, iar jocul trebuie să se termine în aceeași poziție, sau într-una din cele trei poziții suplimentare permise. Deci, dacă câmpul gol inițial a fost în punctul a , jocul ar trebui să se încheie cu un singur pion în pozițiile a , p , O sau C .
Pentru o analiză completă a jocului, consultați Winning Ways for your Mathematical Plays ( ISBN 0-12-091102-7 în Marea Britanie și ISBN 1-56881-144-6 în SUA) (volumul 4, ediția a doua). Cartea introduce o notație numită funcția pagodă , care este un instrument puternic pentru a demonstra imposibilitatea rezolvării unei anumite probleme (generalizate) solitaire. Problema găsirii unei astfel de funcții este formulată ca o problemă de programare liniară cu numere întregi (vezi Kiyomi și Matsui 2001). Uehara și Iwata (1990) au studiat problemele Hi-Q generalizate care sunt echivalente cu problemele solitare și au arătat că acestea sunt NP-complete . Avis și Deza (1996) au formulat problema solitaire ca o problemă de optimizare combinatorie și au discutat o proprietate a domeniului soluțiilor fezabile numită conul solitaire. Kiyomi și Matsui (Kiyomi, Matsui, 2001) au propus o metodă eficientă de rezolvare a problemelor teniei.
Un studiu nepublicat din 1989 asupra unei versiuni generalizate a jocului pe tabla engleză a arătat că fiecare problemă fezabilă în jocul generalizat are 29 soluții diferite, excluzând simetria, deoarece tabla engleză conține 9 subpătrate diferite de 3x3. Acest studiu a dat o limită inferioară a dimensiunii posibilelor probleme de „poziții inverse” în care găurile ocupate inițial devin ocupate și invers. Orice soluție la o astfel de problemă trebuie să constea în cel puțin 11 mișcări, indiferent de formularea exactă a problemei.
Algebra poate fi folosită pentru a dovedi că există doar 5 puncte fixe în care jocul se poate încheia cu succes cu o cheie [2] .
Cea mai scurtă soluție a versiunii standard în limba engleză a jocului este 18 mișcări, numărând mai multe sărituri într-o singură mișcare:
Cea mai scurtă soluție la engleză peg solitaire |
---|
ex 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 • 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 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 oo
oooooooooo
Ordinea unor mișcări poate fi schimbată. Rețineți că, dacă utilizați * pentru găuri și o pentru cuie, puteți rezolva puzzle-ul lucrând înapoi de la ultima imagine și mergând până la prima. Cu toate acestea, acest lucru va necesita mai mult de 18 mișcări. |
Soluția a fost găsită în 1912 de Ernest Bergholt și s-a dovedit a fi cea mai scurtă soluție de către John Beasley în 1964 [3] .
Aceeași soluție poate fi văzută la [4] , care introduce și notația Wolstenholme, care este concepută pentru a face amintirea soluției mai ușoară.
Alte soluții sunt incluse în lista următoare. Lista are formatul
poziție de început: poziție finală=Urmează perechile: cuiul și poziția în care se mișcă. Perechile sunt separate printr-o virgulă sau o bară oblică (slash-ul este plasat ca sfârșitul unui grup de mișcări)
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/dpLocul unde se poate încheia jocul este centrul, sau unul din mijlocul marginilor, iar ultima mișcare trebuie să fim acolo.
Mai jos este un tabel al numărului de B poziții posibile după n mișcări, și numărul O al absenței X mutărilor, poziții în care continuarea este imposibilă.
Dacă o poziție poate fi obținută prin rotire sau oglindire, aceasta este considerată identică.
|
|
|
|
Deoarece numărul maxim de poziții pentru fiecare mutare nu depășește 3626632, iar numărul de mișcări este de 31, computerele moderne pot calcula cu ușurință toate pozițiile într-un timp rezonabil.
Secvențele de mai sus de „VP” sunt listate în OEIS sub numărul A112737 [5] . Rețineți că numărul total de poziții accesibile (suma secvenței) este 23.475.688 [5] , în timp ce numărul total de poziții posibile este 2 33 , sau aproximativ 2 33 /8 ~ 1 miliard dacă se ia în considerare simetria. Astfel, doar aproximativ 2,2% din toate pozițiile posibile de pe tablă sunt realizabile dacă pornind de la un centru gol.
Puteți obține toate pozițiile posibile pe tablă. Rezultatele prezentate în tabel pot fi obținute folosind setul de instrumente mcrl2 (vezi exemplul peg_solitaire din pachet).
|
|
|
|
sunt 3 pozitii initiale incongruente care au solutii. Aceasta:
unu)
0 1 2 3 4 5 6 0 o • • unu • • • • • 2 • • • • • • • 3 • • • • • • • patru • • • • • • • 5 • • • • • 6 • • •Soluție posibilă: [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 • • • • • • • patru • • • • • • • 5 • • • • • 6 • • •Soluție posibilă: [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]
și 3)
0 1 2 3 4 5 6 0 • • • unu • • • • • 2 • • • o • • • 3 • • • • • • • patru • • • • • • • 5 • • • • • 6 • • •Soluție posibilă: [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 joacă și pe alte table, deși acestea două sunt cele mai populare. Tabla poate fi triunghiulara, cu miscari in trei directii.
De obicei, varianta triunghiulară are cinci găuri pe latură. O soluție în care pilonul final ajunge într-un câmp inițial gol nu este posibilă în cele trei puncte centrale. O problemă cu un pătrat gol în colț poate fi rezolvată în zece mutări, dar dacă pătratul gol este situat în centrul laturii, poate fi rezolvată în nouă mutări (Bell 2008):
Cea mai scurtă soluție a variantei triunghiulare |
---|
* = cuierul care face următoarea mișcare; ¤ = gaură eliberată de mișcare; o = cuie îndepărtate (sărit peste); * = gaura in care a ajuns cuiul dupa mutare; • • • * ¤ • • • • • • • * 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 |