Kan elk spel Klondike-Solitaire worden opgelost?

Nee. Voorbeeld: als al uw kaarten open op het bord rood zijn, en de kaarten die op elke derde kaart verschijnen ook rood zijn, en geen van hen azen zijn. Jij verliest. Ga niet voorbij, verzamel geen $ 200.

Reacties

• In feite heb ik bijna deze exacte setup op de computerversie bedacht van Solitaire (maar één kaart was zwart, gewoon helemaal onmogelijk om ergens te plaatsen).
• Nog een voorbeeld dat mij net is overkomen: alle getoonde kaarten zijn even.
• en.wikipedia.org/wiki/Klondike_%28solitaire%29#Odds_of_winning
• Nog eenvoudiger: alle azen staan in dezelfde kolom en 2 staat erboven.
• @Oltarus Azen in dezelfde kolom en 2 erboven is nog steeds te winnen. Het is vervelend en waarschijnlijk een gemis, maar uitvoerbaar.

Er is zeer interessante lezing op wikipedia over dit onderwerp.

Voor een “standaard” spel Klondike (in de vorm: Draw 3, Re-Deal Infinite, Win 52) het aantal oplosbare spellen (ervan uitgaande alle kaarten zijn bekend) ligt tussen 82-91,5%.

Reacties

• Toen was ik doet echt geweldig werk en benadert 80%

Letterlijk gewoon een spel gespeeld waarin een van de stapels (die met 4 kaarten) werden aangevoerd door de ruiten 9, en de kaarten erin waren de schoppenheer, de ruiten 5, de schoppen 10 en de klaveren 10 (ik weet dit omdat ik had het hele veld opgelost behalve deze stack en het gebruikte eliminatieproces). Voor zover ik kan zien, maakt dit het spel onmogelijk. Ik heb een 9 met diamanten die nooit kunnen worden verplaatst, aangezien de twee 10-en waarop hij in aanmerking komt om op te rusten, eronder in de stapel vastzitten met de afbeelding naar beneden. Proberen om de 9 kwijt te raken door hem naar de diamantstapel te verplaatsen zou wees ook vruchteloos, want de diamant 5 zit er ook onder vast. Tenzij iemand me op de een of andere manier kan vertellen dat dit kan worden opgelost, ben ik er vrij zeker van dat als een kaart die leidt een stapel een stapel bedekt die de twee kaarten waarop hij kan rusten, en een lager aantal van zijn eigen reeks, dan wordt het spel vanaf het begin onmogelijk gemaakt.

Solitaire is een spel dat voorafgaat aan zijn computerversie, en dat betekent dat alle kaarten echt worden geschud, zonder dat de computer naar binnen gluurt om te controleren of het spel oplosbaar is.

En zoals McKay al zei, met een willekeurige shuffle kun je zeker eindigen met een onoplosbaar spel.

Ik weet zeker dat het mogelijk is om een Solitaire-variant te ontwerpen waarin elk spel is oplosbaar.

Opmerkingen

• Zou VEEL berekening nodig hebben, in feite zou de computer een heel spel moeten doorlopen om er zeker van te zijn ‘ is een oplossing, tenzij er ‘ een algoritme is dat ik ‘ m ontbreekt.
• @Arda, er zijn enkele voorwaarden die gemakkelijk kunnen worden getest – een andere kaart dan een koning kan bijvoorbeeld op slechts drie andere kaarten in de stapel worden gespeeld (de eerstvolgende laagste kaart in zijn reeks, of de basis voor een aas, en de volgende hogere kaarten van de tegenovergestelde kleur). Als alle drie deze kaarten met de afbeelding naar beneden onder die kaart op een stapel liggen, is het spel niet ‘ te winnen. Helaas denk ik dat ‘ een klein percentage is, en het testen op andere condities kan een hoop recursie vereisen.
• @DaveDuPlantis Waar, maar je zult moeten testen op al die voorwaarden die er zijn. Ik ‘ weet niet zeker of we ze allemaal kennen.
• @Arda – dat ‘ waar is, dat ‘ is wat ik dacht met betrekking tot recursie. Zonder enige manier om aan te tonen dat een bepaalde positie niet kan worden gewonnen, moet je ‘ in wezen een bepaalde reeks kaarten spelen totdat je werd geblokkeerd, teruggaan naar het laatste beslissingspunt en herhalen …het ‘ is een intrigerend concept, maar ik ‘ heb nog nooit een solitaire-programma dat zien doen.
• @Arda Zou eenvoudig achteruit kunnen werken vanuit de oplossing, willekeurig kaarten in de stapel en op het bord verplaatsen van de vier kleurstapels, altijd het omgekeerde van een legaal spel gebruiken. Waarschijnlijk heeft ‘ t dezelfde kansverdeling als het schudden en controleren op winbaarheid, maar ik betwijfel of dat voor de meeste spelers belangrijk is.

Als je echter een lijst hebt gestart en de beginvoorwaarden hebt opgesomd, heb ik het gevoel dat ik dit heb gezien op een Linux-versie van Solitare: de nummering van het kaartspel volgorde, dat wil zeggen – en je beslist definitief dat een bepaalde niet te winnen is, je zou dan notities over knooppunten kunnen vergelijken (delen met vrienden) en VOILA: een lijst met niet te winnen startdekstapels.

Ik begon te denken dat de Windows 7-versie de niet te winnen spellen heeft verwijderd, … Ik weet het niet, het is een beetje hardhandig en zelfvoldaan over de statistieken.

Opmerkingen

• Met 52! als je shuffles start, heb je ‘ een … ongemakkelijke lange … tijd nodig voordat je een goede lijst hebt. Zelfs nadat je het probleem van het definitief bepalen van het niet te winnen hebt opgelost.
• 52 factorial = ongeveer 8 gevolgd door 67 nullen. Dat ‘ zijn veel combinaties. Op een harde schijf van 1 TB zou ongeveer een biljoen hiervan kunnen worden opgeslagen, en u ‘ zou biljoenen terabytes nodig hebben om zelfs maar een behoorlijke fractie op te slaan. Helaas niet erg praktisch, alleen vanwege het astronomische aantal betrokken kansen. Waarschijnlijk gemakkelijker om gewoon een bepaald aantal aantoonbaar te winnen spellen op te slaan.
• @JonathanHobbs Ze hoeven niet allemaal te worden opgeslagen om de berekening te maken. for 1 to 52! getdeck, try solving game, add to statistics op elk punt hoeft slechts één kaartspel te worden opgeslagen, en de statistieken kunnen vrij klein zijn.
• @McKay Je moet nogal wat opslaan om een fatsoenlijke lijst. (Ik ‘ weet niet zeker van welke berekening u spreekt.) Even terzijde, ook wat betreft het antwoord: de Windows 7-versie slaat eigenlijk slechts enkele tientallen duizenden decks op, en u ‘ wordt elke game willekeurig een gegeven. Het kan zijn dat ze zojuist een paar dozijn duizenden decks hebben uitgekozen waarvan bekend is dat ze te winnen zijn.
• @JonathanHobbs Nee, je hoeft alleen maar op te slaan naar welk deck je ‘ kijkt at (wat omhoog zou moeten gaan tot 52 !, wat betekent dat we ‘ ongeveer 226 bits nodig hebben), en jij ‘ d nodig hebt om op te slaan hoeveel ervan oplosbaar waren (nog eens 226 bits of minder), en vervolgens één spel solitaire (dat Windows 3.1 blijkbaar prima kon opslaan), en het algoritme om het spel daadwerkelijk op te lossen. De mechanismen voor gegevensopslag hoeven niet veel te zijn om een volledige reeks statistieken over solvabiliteit te kunnen maken. We ‘ hebben het over minder dan 1k opslagruimte. Het zou natuurlijk veel tijd kosten om al deze berekeningen uit te voeren. Maar niet opslag.

Nee. Eric Sink besloot dat hij een micro-ISV zou starten om een versie van solitaire te maken die altijd te winnen is. Dit was meestal slechts een experiment om te zien hoe het zou zijn om met één persoon een softwarebedrijf te runnen, maar uiteindelijk verkocht het product dat nog steeds te koop is.

Er zijn enkele schattingen geweest over het aantal Klondike Solitaire-spellen dat niet speelbaar is (geen zetten mogelijk, ongeveer 1 op 400), en verschillende gissingen over hoeveel spellen niet te winnen zijn , hoewel dit percentage enorm varieert van 30% -10%.

De moeilijkheid van dit probleem komt voort uit van het enorme aantal eerste deals 54! dat zou moeten worden geëvalueerd om te bepalen welke winbaar waren en welke niet.

Reacties

• zou het aantal initiële deals 52!? (tenzij je verwacht dat de jokers ook gedeeld worden)
• Gelukkig hoef je de brute force-methode niet te gebruiken (kijk naar alle mogelijke deals) om de winkansen te berekenen (aangezien die berekening zou duren langer dan de leeftijd van het universum – 8×10 tot de 68e power decks). Een analyse van manieren om te falen, biedt een analytische aanvalslijn. Zoals reeds opgemerkt, zijn er duidelijke manieren waarop een enkele stapel kan mislukken. De benodigde kaarten kunnen ook onbereikbaar zijn binnen twee stapels, drie stapels of vier stapels. Zodra de conformaties van kaarten voor het vergrendelen van de benodigde kaarten bekend zijn, kunnen hun individuele kansen worden berekend en gecombineerd om een antwoord te krijgen.

Om toe te voegen aan de andere geweldige antwoorden, bevat deze link een mooie uitleg over hoe een deal niet te winnen is.

Redenen om vast te lopen in Klondike Solitaire