# FreeCell (Windows)

FreeCell ist ein Computer-Patience-Spiel.
Ziel ist es, alle Karten so lange um- oder abzulegen, bis sie in vorgegebener Reihenfolge aufeinander liegen.

## Geschichte

Das Spiel erlangte Bekanntheit durch Jim Horne, der es vom PLATO-System kennenlernte und eine Version für Windows implementierte. Es war zunächst in Win32s als Testprogramm, dann im Microsoft Entertainment Pack Volume 2 und später im Best Of Microsoft Entertainment Pack. Freecell blieb relativ unbekannt, bis es Teil von Windows 95 wurde.
Seit Windows 10 wird zwischen den Spielen Werbung gezeigt, der man sich nur durch ein Abonnement entledigen kann. Es gibt auch andere Versionen des Spiels.

## Lösungsmöglichkeiten

Es gibt $52!$ Möglichkeiten, die Spielkarten auf die Plätze zu verteilen. Die Aufgabe bleibt dieselbe, wenn man Spalten mit sieben Karten miteinander vertauscht. Hier gibt es $4!$ Permutationen, ebenso für die Spalten mit sechs Karten. Auch kann man folgenlos die beiden schwarzen Farben vertauschen oder die beiden roten Farben, ebenso Schwarz und Rot. Deshalb gibt es ${\frac {52!}{4!\cdot 4!\cdot 2!\cdot 2!\cdot 2!}}$ verschieden zu spielende Kartenverteilungen.
Das ursprüngliche Microsoft-FreeCell-Spiel bietet 32.000 verschiedene Spiele, erzeugt von einem 15-bit Pseudo-Zufallsgenerator. Diese Spiele sind bekannt als „Microsoft 32000“. Spätere Versionen von Microsoft FreeCell beinhalten mehr Spiele, von denen die ursprünglichen 32.000 eine Untermenge sind. Alle Spiele dieser Microsoft 32.000 wurden gelöst, außer #11982. Viele Menschen und Computerprogramme zur Lösung von Freecell-Spielen waren bisher nicht in der Lage, eine Lösung zu finden, aber ohne mathematischen Beweis kann die Unlösbarkeit nur angenommen werden. Eine weitere Möglichkeit wäre der Einsatz der Brute-Force-Methode.
Der ursprüngliche Hilfetext findet sich auch in aktuellen Versionen: „Es wird davon ausgegangen, dass jedes Spiel zu gewinnen ist, obwohl der Beweis dafür noch aussteht.“ Dieses wurde als Falschaussage in strengem Sinne widerlegt. Die Spiele mit der Nummer -1 und -2 wurden als Kuckucksei hinzufügt, um zu zeigen, dass es Kartenkombinationen gibt, die eindeutig nicht gelöst werden können. Daraufhin kam die Frage auf, ob alle 32.000 Spiele gewonnen werden können.
In späteren Versionen von Windows enthält FreeCell mindestens 1.000.000 Spiele.

### Das Internet FreeCell Projekt

Als die Bekanntheit von FreeCell in den 1990er Jahren stieg, war noch unklar, welche der 32.000 Spiele gelöst werden können. Um diese Frage zu beantworten, startete Dave Ring das Internet FreeCell Project, welches sich der Aufgabe widmet, Lösungen für alle bekannten Spiele durch Menschen zu finden.
Dazu teilte Ring die Menge von 32.000 Spielen in Ketten von je 100 Spielen auf. Unlösbare Spiele wurden an Freiwillige weitergeleitet. Insofern nutzte das Projekt die Stärke des Multiprozessing in Form von realen Teilnehmern. Das Projekt endete im Oktober 1995, und nur Spiel 11.982 widerstand jeglichem menschlichen Lösungsversuch. Das ist jedoch noch kein sicherer Beweis, dass diese Kartenkombination prinzipiell unlösbar ist.

### Ungelöste Kombinationen

Unter den aktuellen Spielen gelten bisher acht als ungelöst. Sie tragen die Nummern 11982, 146692, 186216, 455889, 495505, 512118, 517776 sowie 781948. Diese Folgerung ergibt sich aus der Auswertung verschiedener Autoren von Free-Cell-Lösungsprogrammen. Die Programme von Danny A. Jones und Gary D. Campbell lösten alle FreeCell-Spiele bis auf die genannten Kombinationen. Auch weitere Programme konnten bisher keine Lösung für diese Ausgangssituationen finden.