En solitario, ¿hay algún algoritmo o estrategia para organizar un mazo barajado para asegurarse de que sea solucionable?

Answer 1

No puedo imaginar que haya una manera simple de hacer esto, dada la complejidad de las reglas del Solitario. Y el conjunto de mazos con los que puedes ganar cambiaría dramáticamente con ligeros cambios en las reglas. Además, la mayoría de los algoritmos en los que puedo pensar que te garantizarían un juego que se puede ganar no te darían algo que probablemente querías pero que no estableciste, a saber, una distribución uniforme en todos los juegos que se pueden ganar. Si tratas de comenzar desde la secuencia de movimientos utilizados para resolver el juego y luego rellenas las tarjetas para que encajen, por ejemplo, terminarías con una probabilidad desproporcionada de obtener barajaduras que podrían resolverse de varias maneras.

Entonces, lo que probablemente quiera hacer es usar el muestreo de aceptación / rechazo aquí, que elimina todos sus problemas a costa de no sonar particularmente increíble. Baraja el mazo de la forma habitual, luego ejecuta una función que determine si ese barajado se puede ganar, y si no, descártalo y comienza de nuevo.

Este tipo de técnica funciona con una probabilidad del 100% [1] (suponiendo que la probabilidad de ganar un shuffle no sea cero) y siempre le proporciona una distribución uniforme, pero puede ser costosa si (1) solo se puede ganar un pequeño porcentaje de shuffle , lo que significa que tendrá que reorganizar una y otra vez, y / o (2) es realmente difícil determinar si una mano en particular se puede ganar. Ninguno de estos parece ser un problema en este caso particular: sabemos por experiencia jugando al solitario que la fracción de barajos que se puede ganar es bastante alta (Wikipedia afirma ~ 80% para Klondike), y escribir un programa de computadora eficiente que pueda resolver el juego de solitario con todas las cartas boca arriba no es tan difícil de hacer.

[1] Teóricamente es posible que puedas seguir eligiendo el mismo shuffle una y otra vez para siempre, pero la probabilidad de ese tipo de cosas es cero.