FreeCell

El juego tiene un número constante de cartas. Esto implica que en un tiempo constante, una persona o computadora podría listar todos los posibles movimientos de una configuración inicial dada y descubrir un conjunto de movimientos ganadores o, asumiendo que el juego no puede ser resuelto, la falta del mismo. Para realizar un interesante análisis de complejidad se debe construir una versión generalizada del juego de FreeCell con 4 × n cartas. Esta versión generalizada del juego es NP-completa;[5] es improbable que cualquier algoritmo más eficiente que una búsqueda de fuerza bruta exista tal que pueda encontrar soluciones para configuraciones de FreeCell arbitrariamente generalizadas.

Existen 52! (es decir, 52 factorial), o aproximadamente 8×10⁶⁷, repartos únicos. Sin embargo, algunos juegos son efectivamente idénticos a otros debido a que los palos asignados a las cartas son arbitrarios o las columnas pueden ser intercambiadas. Después de tomar estos factores en cuenta, hay aproximadamente 1,75×10⁶⁴ juegos únicos.[2]

Una de las pasiones de varios entusiastas de FreeCell fue el construir programas de computadora que pudieran resolver automáticamente el juego. Don Woods escribió un solucionador para FreeCell y varios juegos similares en 1997.[6]

Otro conocido solucionador es Patsolve de Tom Holroyd. Patsolve utiliza movimientos atómicos, y desde la versión 3.0 ha incorporado una función de peso basada en los resultados de un algoritmo genético que lo hace mucho más rápido.[7]

Shlomi Fish inició su propio solucionador en 2000, escrito en el lenguaje de programación C y distribuido con su código fuente en el dominio público, más tarde relicenciado bajo la Licencia MIT.[8][9] Este solucionador fue simplemente denominado Freecell Solver.

Gary Campbell escribió su solucionador FCELL para DOS en lenguaje ensamblador para 8086. Este solucionador pesa 12 kilobytes, y es bastante rápido. FCELL fue incorporado en el Faslo FreeCell AutoPlayer en 2007.[10]

Algunos de estos solucionadores y otros se han incorporado dentro de grandes programas de FreeCell o de solitario. FreeCell Pro, la implementación mejorada de solitario basada en Windows por Adrian Ettlinger y Wilson Callan (anteriormente freeware, después licenciado bajo la GPL), integró primero el solucionador de Don Woods[2] y posteriormente utilizó el solucionador de Fish y el Patsolve de Holroyd.[11] PySolFC ha integrado el Freecell Solver,[12] mientras que los juegos de solitario KPatience de KDE tenían integrado inicialmente el Freecell Solver también, pero después cambiaron a una versión muy modificada de Patsolve.[13]

Se cree que el juego #11982 es el único sin solución de los 32.000 juegos originales del FreeCell de Windows. En la versión de FreeCell de Windows XP, con un millón de manos, hay ocho repartos que se ha demostrado que son irresolubles.[2] Actualmente, ninguna simulación de computadora ha sido capaz de resolver el juego #11982 utilizando solo cuatro casillas vacías.[14]

Cuando el FreeCell de Microsoft se volvió muy popular durante la década de los 1990, no estaba claro cuál de los 32.000 repartos en el programa podían resolverse. Para aclarar la situación, Dave Ring inició The Internet FreeCell Project (El Proyecto FreeCell de Internet) y tomó el desafío de tratar de resolver todos los repartos usando solucionadores humanos. Ring asignó 100 bloques de juegos consecutivos a humanos voluntarios y recolectó los juegos que ellos reportaban como irresolubles, y se los asignó a otras personas. Este proyecto utilizó el poder del crowdsourcing (búsqueda de información en masa) para convergir rápidamente en la respuesta. El proyecto fue finalizado en octubre de 1995, y solo un juego venció cada intento de los jugadores humanos: #11.982. Este reparto ha vencido también cada intento de solución por varios programas solucionadores de búsqueda exhaustiva, y por tanto se asume que es imposible.[2]

El juego 11.982 es inherentemente difícil debido al gran número de ases y otras cartas pequeñas hasta atrás en las columnas, así como a que las cartas altas que están distribuidas de manera relativamente uniforme en las columnas, requieren el uso de muchas de las casillas para llegar a cualquier carta útil.

Fuera de los actuales juegos de Microsoft Windows, hay ocho que son irresolubles: los juegos numerados 11.982; 146.692; 186.216; 455.889; 495.505; 512.118; 517.776 y 781.948. La búsqueda exhaustiva ha mostrado que para estos juegos se requieren 5 casillas libres, en vez de las cuatro casillas estándar. Adrian Ettlinger, usando el solucionador de Don Woods, ha usado el mismo generador de manos aleatorias que el FreeCell de Microsoft Windows para explorar más de 10 millones de juegos. De los 130 juegos sin solución en los primeros 10 millones, todos ellos requieren de 5 casillas libres. Ryan L. Miller, con la ayuda de otros exploró 100 millones de juegos, con un total de 1282 juegos irresolubles. Esto le da a FreeCell una tasa ganadora de alrededor de 99,998718%.[2]

En las primeras versiones, los juegos numerados como -1 y -2 estaban incluidos como un tipo de huevo de pascua para demostrar que había algunas combinaciones de cartas posibles que claramente no podrían ser ganadas. Para esto, las cartas son colocadas en orden de valor, tales como Rey, Reina, Jack, 10, 9 y 8 en las primeras cuatro columnas, y los números restantes en las otras.

En las versiones previas a Windows Vista, si el usuario tecleaba la combinación de Ctrl+Shift+F10 en cualquier momento durante el juego, al usuario se le presentaría una herramienta utilizada por los desarrolladores durante las pruebas.[15]

En las versiones de Windows Vista y Windows 7, si el usuario hace clic en "Seleccionar juego" y escribe -3 o -4 en la caja de diálogo, entonces, cuando el juego se cargue, se mueve un as a la casilla de llegada, las otras cartas automáticamente se colocarán en sus respectivas casillas de llegada, ganando el juego. El seleccionar -1 o -2 en la caja de diálogo resulta en dos manos no aleatorias altamente ordenadas imposible de ganar.