FreeCell
# FreeCell

FreeCell (Carta blanca) es un solitario de cartas, jugado con una baraja francesa de 52 cartas. Es fundamentalmente diferente de la mayoría de juegos de solitario en que casi todos los escenarios pueden ser resueltos. Aunque varían las implementaciones de software, la mayoría de las versiones etiqueta los escenarios con un número, derivado de la siembra de números aleatorios usada para generar la mano.

Una versión de FreeCell fue creada por Microsoft para su lanzamiento con el sistema operativo Windows.

## Reglas

Construcción y distribución:

* Es utilizado un mazo estándar de 52 cartas.
* Existen cuatro casillas abiertas y cuatro sitios de llegada abiertos. Algunas reglas alternativas usan de una a diez casillas.
* Las cartas son repartidas en ocho columnas en cascada, cuatro de ellas con siete cartas y las otras cuatro con seis cartas. Algunas reglas alternativas utilizan entre cuatro y diez columnas.

Construcción durante el juego:

* La carta más al frente de cada columna comienza una pila de cartas.
* Las pilas deben ser colocadas haciendo una cascada hacia abajo alternando colores.
* Las cartas en las casillas de llegada son colocadas ordenadas por pintas (palos).

Movimientos:

* Cualquier carta que esté en una de las cuatro casillas auxiliares o la carta más frontal de una pila puede ser movida ya sea a otra pila, a una casilla vacía, una columna vacía, o a su casilla de llegada.
* Pueden ser movidas pilas completas o parciales a pilas ya existentes, o a columnas vacías, colocando y removiendo cartas de manera recursiva a través de localizaciones intermedias. Mientras que las implementaciones de computadora suelen mostrar este movimiento, los jugadores que utilizan mazos de cartas físicos típicamente mueven la pila de una sola vez.

Victoria:

* El juego es ganado después de que todas las cartas son movidas a sus respectivas pilas en las casillas de llegada.

En el caso de los juegos con la distribución estándar, cuatro casillas abiertas y ocho columnas, la mayoría de los juegos son fácilmente resueltos.

## Historia

Uno de los ancestros más viejos de FreeCell es Eight Off. En la edición de junio de 1968 de Scientific American, Martin Gardner describió en su columna "Juegos matemáticos" un juego por C. L. Baker que es similar a FreeCell, excepto que las cartas en las pilas son construidas por palos en vez de hacerlo por color alternativo. Gardner escribió: "El juego fue enseñado a Baker por su padre, quien a su vez lo aprendió de un inglés durante los años 1920's". Esta variante es ahora llamada Baker's Game. Los orígenes de FreeCell pueden remontarse aún más lejos de 1945 y un juego escandinavo llamado "Napoleon in St. Helena" (no el juego llamado "Napoleon at St. Helena", también conocido como Forty Thieves).

Paul Alfille cambió el Baker's Game haciendo la construcción de las pilas de acuerdo a colores alternativos, creando así FreeCell. Él implementó la primera versión computarizada del juego en el lenguaje de programación TUTOR para el sistema de computadora educativo PLATO en 1978. Alfille fue capaz de mostrar imágenes gráficas fácilmente reconocibles de juegos de cartas en la pantalla monocromática 512 × 512 de los sistemas PLATO.

Este ambiente original de FreeCell permitía juegos con 4–10 columnas y 1–10 casillas además del juego estándar de 8 × 4. Para cada variante, el programa almacenaba una lista ordenada de los jugadores con las mayores rachas ganadoras. Había también un sistema de torneo que le permitía a la gente competir para ganar repartos de cartas difíciles escogidos manualmente. Paul Alfille describe este primer ambiente de FreeCell con más detalle en una entrevista del año 2000.

## Resolución

### Complejidad

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; 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^{67},$ 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^{64}$ juegos únicos.

### Solucionadores

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.

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.

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. 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.

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 y posteriormente utilizó el solucionador de Fish y el Patsolve de Holroyd. PySolFC ha integrado el Freecell Solver, 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.

### Juegos imposibles

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. Actualmente, ninguna simulación de computadora ha sido capaz de resolver el juego #11982 utilizando solo cuatro casillas vacías.

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.

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%.

### Huevos de pascua

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.

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.

