Kan varje spel i Klondike-Solitaire lösas?

Nej. Exempel: Om alla dina kort med framsidan uppåt på brädet är röda, och korten som kommer upp vart tredje kort också är röda, och inget av dem är ess. Du förlorar. Passera inte gå, samla inte in $ 200.

Kommentarer

• Som ett faktum har jag kommit med nästan den här exakta installationen på datorversionen av Solitaire (men ett kort var svart, helt omöjligt att placera någonstans).
• Ett annat exempel som just hände mig: Alla kort som visas är jämna.
• sv.wikipedia.org/wiki/Klondike_%28solitaire%29#Odds_of_winning
• Ännu enklare: alla ess finns i samma kolumn och 2 ligger ovanför dem.
• @Oltarus Ess i samma kolumn och 2 ovanför dem kan fortfarande vinnas. Det är irriterande och förmodligen en förlust men genomförbart.

Det finns mycket intressant läsning på wikipedia om detta ämne.

För ett ”standard” -spel av Klondike (av formen: Draw 3, Re-Deal Infinite, Win 52) antalet lösbara spel (förutsatt alla kort är kända) är mellan 82-91,5%.

Kommentarer

• Då var jag faktiskt gör ett bra jobb närmar sig det till 80%

Bokstavligen spelade bara ett spel där en av stackarna (den som innehåller 4 kort) leddes av de 9 diamanterna, och korten inuti den var kungen av spader, 5 av diamanter, de 10 spaderna och de 10 klubbarna (jag vet detta för att jag hade löst hela fältet förutom denna stapel och använt eliminationsprocess). Såvitt jag kan se gör detta spelet omöjligt. Jag har en 9 diamanter som aldrig kan flyttas, eftersom de två 10-talet som den kan vila på sitter fast under den i stacken med framsidan nedåt. Att försöka bli av med 9 genom att flytta den till diamantstacken skulle var också fruktlös, eftersom de fem diamanterna sitter fast under den också. Om inte någon kan säga mig på något sätt att detta skulle kunna lösas, var jag ganska säker på att om ett kort som leder en stack täcker en stack som innehåller två kort det kan vila på, och ett lägre antal av det är sin egen färg, då görs spelet omöjligt direkt från början.

Solitaire är ett spel som föregår dess datorversion, och det betyder att alla kort verkligen blandas utan att datorn kikar in för att verifiera att spelet är lösbart.

Och som McKay nämnde, med en slumpmässig blandning kan du definitivt sluta med ett olösligt spel.

Jag är säker på att det är möjligt att designa en Solitaire-variant där varje spel är dock lösbar.

Kommentarer

• Skulle behöva MYCKET beräkning, i princip skulle datorn behöva spela igenom ett helt spel för att se till att det ’ en lösning, såvida det inte finns ’ någon typ av algoritm jag ’ saknas.
• @Arda, det finns vissa villkor som lätt kan testas – till exempel kan ett annat kort än en kung spelas på endast tre andra kort i kortlek (det näst lägsta kortet i sin färg, eller grunden för ett ess och nästa kort av motsatt färg). Om alla tre av dessa kort är vända nedåt under det kortet på en hög, är spelet inte ’ som inte kan vinnas. Tyvärr tror jag att ’ är en liten procentsats, och att testa för andra förhållanden kan kräva massor av rekursion.
• @DaveDuPlantis Det är sant, men du måste testa för alla dessa förhållanden som finns. Jag ’ är inte säker på om vi ens känner till dem alla.
• @Arda – det ’ är sant, att ’ är vad jag tänkte med avseende på rekursion. Utan något sätt att visa att en viss position inte kan vinnas måste du ’ i huvudsak spela en viss kortserie tills du blockerades, säkerhetskopiera till den sista beslutpunkten och upprepa …det ’ är ett spännande koncept, men jag ’ har aldrig sett ett patiensprogram göra det.
• @Arda Kan helt enkelt arbeta bakåt från lösningen, slumpmässigt flytta kort in i kortlekarna och på brädet från de fyra färgstaplarna, alltid med det motsatta av ett lagligt spel. Förmodligen vann ’ inte samma sannolikhetsfördelning som blandning och kontroll av vinst, men jag tvivlar på att det är viktigt för de flesta spelare.

Men om du startade en lista och räknade upp de ursprungliga villkoren – känns det som att jag har sett detta på en Linux-version av Solitare: numreringen av däcket ordning, det vill säga – och du bestämmer dig definitivt för att en viss inte kan vinnas, du kan sedan jämföra anteckningar över noder (dela med vänner) och VOILA: en lista över startbara kortstackar som inte kan vinnas.

Jag har börjat tro att Windows 7-versionen har borttagbara däck som inte kan vinnas … Jag vet inte, det är lite tunghänt och självbelåten om statistiken.

Kommentarer

• Med 52! när du börjar blanda, behöver du ’ en … obekvämt lång … tid innan du har en bra lista. Även efter att du har löst problemet med att bestämma oövervinnligt definitivt.
• 52 faktor = ungefär 8 följt av 67 nollor. Att ’ är många kombinationer. En 1 TB hårddisk skulle lagra ungefär en biljon av dessa och du ’ d behöver biljoner terabyte för att lagra till och med en anständig bråkdel. Inte särskilt praktiskt, bara på grund av det astronomiska antalet sannolikheter som är inblandade. Förmodligen lättare att bara lagra ett visst antal bevisligen vinnbara spel.
• @JonathanHobbs Inte alla behöver lagras för att göra beräkningen. for 1 to 52! getdeck, try solving game, add to statistics vid varje punkt behöver bara ett kort lagras och statistiken kan vara ganska liten.
• @McKay Du måste lagra en hel del för att utveckla en anständig lista, dock. (Jag ’ är inte säker på vilken beräkning du talar om.) Som en åsidosättning även när det gäller svaret: Windows 7-versionen lagrar faktiskt bara några dussin tusen kortlekar och du ’ ges slumpmässigt ett varje spel. Det kan hända att de bara valde några dussin tusen däck som är kända för att vara vinnbara.
• @JonathanHobbs Nej, allt du behöver lagra är vilket däck du ’ du letar efter vid (vilket skulle behöva gå upp till 52 !, vilket betyder att vi ’ d behöver cirka 226 bitar), och du ’ d behöver för att lagra hur många av dem som var lösbara (ytterligare 226 bitar eller mindre), och sedan ett spel patiens (vilket Windows 3.1 tydligen kunde lagra bra), och algoritmen för att faktiskt lösa spelet. Datalagringsmekanismerna behöver inte vara så mycket för att kunna göra en fullständig uppsättning statistik om lösbarhet. Vi ’ talar mindre än 1 000 lagringsutrymme. Visst att det skulle ta lång tid att göra alla dessa beräkningar. Men inte lagring.

Nej. Eric Sink bestämde att han skulle starta en mikro-ISV för att skapa en version av patiens som alltid är vinnbar. Detta var mest bara ett experiment för att se hur det skulle vara att driva ett mjukvaruföretag med en person, men så småningom sålde produkten som fortfarande finns att köpa.

Det har gjorts några uppskattningar av antalet Klondike Solitaire-spel som är ospelbara (inga drag möjliga, ungefär 1 av 400) och flera gissningar om hur många spel som inte kan vinnas , även om denna procentsats varierar vilt från 30% -10%.

Problemets svårighet beror på från det stora antalet initiala erbjudanden 54! som måste utvärderas för att avgöra vilka som kan vinnas och vilka som inte kan.

Kommentarer

• skulle antalet initiala erbjudanden vara 52!? (såvida du inte förväntar dig att skämtarna också delas ut)
• Lyckligtvis behöver man inte använda brute force-metoden (titta på alla möjliga erbjudanden) för att beräkna oddsen för att vinna (eftersom den beräkningen skulle ta längre än universums ålder – 8×10 till 68: e kraftdäck). En analys av sätt att misslyckas ger en analytisk attacklinje. Som redan nämnts finns det tydliga sätt att en enda stack misslyckas. De kort som behövs kan också vara oåtkomliga inom två stackar, tre stackar eller fyra stackar. När kortkonformationerna för att låsa upp de kort som behövs är kända kan deras individuella odds beräknas och kombineras för att få svar.