¿Se pueden resolver todos los juegos de Klondike-Solitaire?

No. Ejemplo: si todas tus cartas boca arriba en el tablero son rojas, y las cartas que salen cada tres cartas también son rojas, y ninguna de ellas es ases. Tú pierdes. No pase, vaya, no recolecte $ 200.

Comentarios

• De hecho, se me ocurrió casi esta configuración exacta en la versión para computadora de Solitario (pero una carta era negra, simplemente imposible de colocar en cualquier lugar).
• Otro ejemplo que me acaba de pasar: todas las cartas que se muestran son pares.
• en.wikipedia.org/wiki/Klondike_%28solitaire%29#Odds_of_winning
• Aún más sencillo: todos los ases están en la misma columna y 2 encima de ellos.
• @Oltarus Aces en la misma columna y 2 encima de ellos todavía se puede ganar. Es molesto y probablemente una pérdida, pero factible.

Hay lectura muy interesante en wikipedia sobre este tema.

Para un juego «estándar» de Klondike (de la forma: Draw 3, Re-Deal Infinite, Win 52) el número de juegos solucionables (asumiendo todas las tarjetas son conocidas) está entre 82-91.5%.

Comentarios

• Entonces estaba haciendo un gran trabajo acercándose al 80%

Literalmente, acaba de jugar un juego en el que uno de las pilas (la que contiene 4 cartas) estaba encabezada por el 9 de diamantes, y las cartas dentro eran el Rey de espadas, el 5 de diamantes, el 10 de picas y el 10 de tréboles (lo sé porque resolvió todo el campo excepto esta pila y utilizó el proceso de eliminación). Por lo que puedo ver, esto hace que el juego sea imposible. Tengo un 9 de diamantes en el que nunca se puede mover, ya que los dos decenas sobre los que puede descansar están atrapados debajo en la pila boca abajo. Intentar deshacerse del 9 moviéndolo a la pila de diamantes sería También será infructuoso, ya que el 5 de diamantes también está pegado debajo. A menos que alguien pueda decirme de alguna manera que esto podría resolverse, estoy bastante seguro de que si una carta que lidera una pila cubre una pila que contiene la dos cartas sobre las que es capaz de descansar, y un número menor de su propio palo, entonces el juego se vuelve imposible desde el principio.

El solitario es un juego que precede a su versión de computadora, y eso significa que todas las cartas están realmente barajadas, sin que la computadora se asome para verificar que el juego se puede resolver.

Y como mencionó McKay, con una mezcla aleatoria definitivamente puedes terminar con un juego sin solución.

Estoy seguro de que es posible diseñar una variante de solitario en la que cada juego sea Sin embargo, se puede resolver.

Comentarios

• Necesitaría MUCHO cálculo, básicamente la computadora tendría que jugar todo un juego para asegurarse de que haya ‘ es una solución, a menos que ‘ haya algún tipo de algoritmo que ‘ falte.
• @Arda, hay algunas condiciones que podrían probarse fácilmente; por ejemplo, una carta que no sea un Rey se puede jugar solo en otras tres cartas del mazo (la siguiente carta más baja de su palo, o la base de un As y las siguientes cartas superiores del color opuesto). Si las tres cartas están boca abajo debajo de esa carta en una pila, el juego no ‘ no se puede ganar. Desafortunadamente, creo que ‘ es un pequeño porcentaje, y las pruebas para otras condiciones pueden requerir una tonelada de recursividad.
• @DaveDuPlantis True, pero tendrás que probar todas esas condiciones que existen. ‘ no estoy seguro de si los conocemos a todos.
• @Arda – eso ‘ es cierto, que ‘ es lo que estaba pensando con respecto a la recursividad. Sin alguna forma de demostrar que una posición dada es imposible de ganar, usted ‘ esencialmente tendrá que jugar una cierta serie de cartas hasta que sea bloqueado, retroceder hasta el último punto de decisión y repetir …Es ‘ un concepto intrigante, pero ‘ nunca he visto a un programa de solitario hacer eso.
• @Arda Simplemente podría trabajar al revés desde la solución, moviendo cartas al azar al mazo y al tablero de las pilas de cuatro palos, siempre usando el reverso de una jugada legal. Probablemente ganó ‘ t tiene la misma distribución de probabilidad que barajar y verificar la posibilidad de ganar, pero dudo que eso le importe a la mayoría de los jugadores.

Sin embargo, si comenzaste una lista y enumeraste las condiciones iniciales, siento que he visto esto en una versión linux de Solitare: la numeración del mazo orden, es decir, y definitivamente decides que una determinada no se puede ganar, luego puedes comparar notas entre los nodos (compartir con amigos) y VOILA: una lista de mazos iniciales que no se pueden ganar.

He comenzado a pensar que la versión de Windows 7 ha eliminado los mazos que no se pueden ganar, … no sé, es un poco torpe y presumido acerca de las estadísticas.

Comentarios

• ¡Con 52! al empezar a barajar, ‘ necesitará un tiempo … inconvenientemente largo … antes de tener una buena lista. Incluso después de resolver el problema de determinar definitivamente la imposibilidad de ganar.
• 52 factorial = aproximadamente 8 seguido de 67 ceros. Esas ‘ son muchas combinaciones. Un disco duro de 1 TB almacenaría alrededor de un billón de estos, y ‘ necesitaría billones de terabytes para almacenar incluso una fracción decente. Desafortunadamente, no es muy práctico, solo por el número astronómico de probabilidades involucradas. Probablemente sea más fácil almacenar una cierta cantidad de juegos demostrables que se pueden ganar.
• @JonathanHobbs No es necesario almacenar todos para realizar el cálculo. for 1 to 52! getdeck, try solving game, add to statistics en cada punto solo se necesita almacenar un mazo, y las estadísticas pueden ser bastante pequeñas.
• @McKay Tienes que almacenar bastante para desarrollar un lista, sin embargo. (Yo ‘ no estoy seguro del cálculo del que habla.) Como un aparte también con respecto a la respuesta: la versión de Windows 7 en realidad solo almacena unas pocas docenas de miles de cubiertas, y usted ‘ se le da uno al azar en cada juego. Puede ser que hayan elegido unas pocas docenas de miles de mazos que se sabe que se pueden ganar.
• @JonathanHobbs No, todo lo que tienes que almacenar es qué mazo ‘ estás buscando at (¡lo que tendría que subir a 52 !, lo que significa que ‘ d necesitamos unos 226 bits), y usted ‘ necesitaría para almacenar cuántos de ellos se podían resolver (otros 226 bits, o menos), y luego un juego de solitario (que aparentemente Windows 3.1 pudo almacenar bien), y el algoritmo para resolver el juego. Los mecanismos de almacenamiento de datos no necesitan ser demasiado para hacer un conjunto completo de estadísticas sobre la solvencia. ‘ estamos hablando de menos de 1k de almacenamiento. Seguro que llevaría mucho tiempo hacer todos estos cálculos. Pero no almacenamiento.

No. Eric Sink decidió que iniciaría un micro-ISV para crear una versión del solitario que siempre se puede ganar. Esto fue principalmente un experimento para ver cómo sería administrar una empresa de software con una persona, pero finalmente vendió el producto que todavía está disponible para su compra.

Ha habido algunas estimaciones sobre el número de juegos de Klondike Solitaire que son injugable (no se pueden realizar movimientos, aproximadamente 1 en 400), y varias suposiciones sobre cuántos juegos son imposibles de ganar , aunque este porcentaje varía enormemente del 30% al 10%.

La dificultad de este problema se debe a por el gran número de ofertas iniciales 54! eso tendría que evaluarse para determinar cuáles se podían ganar y cuáles no.

Comentarios

• ¿El número de acuerdos iniciales sería 52!? (a menos que espere que también se repartan los comodines)
• Afortunadamente, no es necesario utilizar el método de fuerza bruta (ver todas las ofertas posibles) para calcular las probabilidades de ganar (ya que ese cálculo tomaría más largo que la edad del universo – 8 x 10 a las 68 barajas de poder). Un análisis de las formas de fallar proporciona una línea de ataque analítica. Como ya se señaló, hay formas claras de que una sola pila falle. Las cartas necesarias también pueden ser inalcanzables dentro de dos pilas, tres pilas o cuatro pilas. Una vez que se conocen las conformaciones de las tarjetas para bloquear las tarjetas necesarias, sus probabilidades individuales se pueden calcular y combinar para obtener una respuesta.

Para agregar a las otras excelentes respuestas, este enlace tiene una buena explicación de cómo un trato no se puede ganar.

Razones para quedarse atascado en Klondike Solitaire