Poate fi rezolvat fiecare joc de Klondike-Solitaire?

Nu Exemplu: Dacă toate cărțile tale cu fața în sus pe tablă sunt roșii, iar cărțile care apar în fiecare a treia carte sunt de asemenea roșii și niciuna dintre ele nu este ași. Ai pierdut. Nu treceți, nu colectați 200 USD.

Comentarii

• De fapt, am venit cu această configurare exactă pe versiunea computerului de Solitaire (dar o carte era neagră, pur și simplu complet imposibilă de plasat oriunde).
• Un alt exemplu care mi s-a întâmplat tocmai: toate cărțile afișate sunt uniforme.
• en.wikipedia.org/wiki/Klondike_%28solitaire%29#Odds_of_winning
• Și mai simplu: toți ații sunt pe aceeași coloană și 2 este deasupra lor.
• @Oltarus Aces în aceeași coloană și 2 deasupra lor este încă câștigabil. Este enervant și probabil o pierdere, dar realizabil.

Există lectură foarte interesantă pe Wikipedia despre acest subiect.

Pentru un joc „standard” al Klondike (de la forma: Draw 3, Re-Deal Infinite, Win 52) numărul de jocuri rezolvabile (presupunând toate cărțile sunt cunoscute) este între 82-91,5%.

Comentarii

• Atunci am fost De fapt, fac o treabă excelentă, aproape de 80%.

Literal, tocmai am jucat un joc în care unul dintre stivele (cea care conține 4 cărți) a fost condusă de 9 de diamante, iar cărțile din interiorul ei au fost Regele de Pică, 5 de diamante, 10 de pică și 10 de cluburi (știu asta pentru că eu a rezolvat întregul câmp, cu excepția acestei stive și a folosit procesul de eliminare). Din câte văd, acest lucru face jocul imposibil. Am un 9 de diamante în care nu pot fi mișcate niciodată, deoarece cele două 10 pe care este eligibil să se odihnească sunt prinse sub el în stiva cu fața în jos. Încercarea de a scăpa de cele 9 prin mutarea acestuia în stiva de diamante ar face De asemenea, fiți fără rezultat, deoarece 5 diamante sunt lipite și sub el. Cu excepția cazului în care cineva îmi poate spune cumva că acest lucru ar putea fi rezolvat, sunt destul de îndrăznit să știu că dacă o carte care conduce un teanc acoperă un teanc două cărți pe care este capabil să se sprijine și un număr mai mic din costumul propriu, atunci jocul este imposibil chiar din start.

Solitaire este un joc care precede versiunea computerului, ceea ce înseamnă că toate cărțile sunt amestecate cu adevărat, fără ca computerul să se uite pentru a verifica dacă jocul este rezolvabil.

Și, așa cum a menționat McKay, cu un amestec aleatoriu puteți ajunge cu siguranță la un joc de nerezolvat.

Sunt sigur că este posibil să proiectați o variantă Solitaire în care fiecare joc este rezolvabil, totuși.

Comentarii

• Ar avea nevoie de MULTE calcule, practic computerul ar trebui să joace printr-un întreg joc pentru a se asigura că acolo ‘ sa soluție, dacă nu există ‘ un fel de algoritm care îmi lipsește ‘ / li>
• @Arda, există unele condiții care ar putea fi ușor testate – de exemplu, o altă carte decât un rege poate fi jucată doar pe alte trei cărți din pachet (următoarea cea mai mică carte din costumul său sau fundația pentru un As și cărțile următoare-superioare de culoarea opusă). Dacă toate cele trei cărți sunt cu fața în jos sub acea carte pe o grămadă, jocul nu poate fi câștigat ‘. Din păcate, cred că ‘ este un procent mic, iar testarea pentru alte condiții ar putea necesita o tonă de recursivitate.
• @DaveDuPlantis Este adevărat, dar va trebui să testați pentru toate acele condiții care există. Nu ‘ nu sunt sigur dacă știm chiar pe toate.
• @Arda – ‘ este adevărat, ‘ este ceea ce mă gândeam cu privire la recursivitate. Fără o modalitate de a demonstra că o anumită poziție nu poate fi câștigată, ‘ ar trebui să joci o anumită serie de cărți până când ai fost blocat, înapoi la ultimul punct de decizie și repet …’ este un concept interesant, dar eu ‘ nu am văzut niciodată un program solitar care să facă asta.
• @Arda Aș putea pur și simplu să meargă înapoi de la soluție, mutând aleatoriu cărți în pachet și pe tablă de la cele patru piloți de costum, folosind întotdeauna reversul unui joc legal. Probabil câștigat ‘ nu are aceeași distribuție de probabilitate ca amestecarea și verificarea câștigului, dar mă îndoiesc că este importantă pentru majoritatea jucătorilor.

Cu toate acestea, dacă ați început o listă și ați enumerat condițiile inițiale – simt că am văzut asta într-o versiune Linux a Solitare: numerotarea punții ordinea, adică – și decideți definitiv că o anumită este imposibil de câștigat, puteți compara apoi notele între noduri (partajați cu prietenii) și VOILA: o listă de stive de punte de pornire care nu pot fi câștigate.

„Am început să cred că versiunea Windows 7 are pachetele care nu pot fi câștigate îndepărtate, … nu știu, este puțin cam greu și contrazic de statistici.

Comentarii

• Cu 52! începând amestecarea, ‘ veți avea nevoie de un … inconvenient lung … de timp înainte de a avea o listă bună. Chiar și după ce ați rezolvat problema determinării definitivului câștigabil.
• 52 factorial = aproximativ 8 urmat de 67 de zerouri. Asta ‘ este o mulțime de combinații. Un hard disk de 1 TB ar stoca aproximativ un trilion de acestea, iar ‘ ai nevoie de trilioane de terabyți pentru a stoca chiar și o fracțiune decentă. Nu prea practic din păcate, doar din cauza numărului de probabilități astronomice implicate. Probabil că este mai ușor să stochezi doar un anumit număr de jocuri câștigabile în mod demonstrabil.
• @JonathanHobbs Nu trebuie stocate toate pentru a face calculul. for 1 to 52! getdeck, try solving game, add to statistics în fiecare punct trebuie stocat un singur pachet, iar statisticile pot fi destul de mici.
• @McKay Trebuie să stochezi destul de mult pentru a dezvolta un sistem decent listă, totuși. (Nu ‘ nu sunt sigur despre calculul despre care vorbiți.) Ca o parte și despre răspuns: versiunea Windows 7 stochează de fapt doar câteva zeci de mii de punți, iar dvs. ‘ i se dă câte un joc în mod aleatoriu. S-ar putea să fi ales doar câteva zeci de mii de punți despre care se știe că pot fi câștigate.
• @JonathanHobbs Nu, tot ce trebuie să stochezi este pachetul pe care îl cauți ‘ at (care ar trebui să meargă până la 52 !, ceea ce înseamnă că ‘ avem nevoie de aproximativ 226 biți) și aveți nevoie de ‘ pentru a stoca câți dintre ei au fost rezolvabili (alți 226 de biți sau mai puțin), și apoi un joc de solitaire (care Windows 3.1 a fost aparent capabil să stocheze foarte bine) și algoritmul pentru a rezolva efectiv jocul. Mecanismele de stocare a datelor nu trebuie să fie foarte mult pentru a face un set complet de statistici privind solvabilitatea. ‘ vorbim mai puțin de 1k de stocare. Sigur că ar dura mult timp pentru a face toate aceste calcule. Dar nu stocare.

Nu Eric Sink a decis că va începe un micro-ISV pentru a crea o versiune de solitaire care este întotdeauna câștigabilă. Acesta a fost în mare parte doar un experiment pentru a vedea cum ar fi să conduci o companie de software cu o singură persoană, dar în cele din urmă a vândut produsul care este încă disponibil pentru cumpărare.

Au existat unele estimări cu privire la numărul de jocuri Klondike Solitaire care nu pot fi jucate (nu sunt posibile mișcări, aproximativ 1 din 400) și mai multe presupuneri despre câte jocuri sunt imposibil de câștigat , deși acest procent variază de la 30% la 10%.

Dificultatea acestei probleme provine din numărul mare de oferte inițiale 54! care ar trebui evaluat pentru a determina care sunt câștigabile și care nu.

Comentarii

• numărul de tranzacții inițiale ar fi 52!? (cu excepția cazului în care vă așteptați ca și jokerii să fie tratați)
• Din fericire, nu este nevoie să folosiți metoda forței brute (uitați-vă la toate ofertele posibile) pentru a calcula șansele de a câștiga (deoarece acest calcul ar dura mai lung decât vârsta universului – 8×10 până la 68 de punți de putere). O analiză a modalităților de a eșua oferă o linie analitică de atac. După cum sa menționat deja, există modalități clare în care o singură stivă poate eșua. Cardurile necesare ar putea fi, de asemenea, inaccesibile în două stive, trei stive sau patru stive. Odată cunoscute conformațiile cărților pentru blocarea cărților necesare, cotele lor individuale pot fi calculate și combinate pentru a obține un răspuns.

Pentru a adăuga la celelalte răspunsuri grozave, acest link are o explicație plăcută a modului în care o afacere este imposibil de câștigat.

Motive pentru a te bloca în Klondike Solitaire