example of an unsolvable FreeCell deal, the only deal among the original "Microsoft 32,000" which is unsolvable. History and variants One of the oldest ancestors of FreeCell is Eight Off. In the June 1968 edition of Scientific American, Martin Gardner described in his "Mathematical Games" column a game by C. L. Baker that is similar to FreeCell, except that cards on the tableau are built by suit rather than by alternate colors. Gardner wrote, "The game was taught to Baker by his father, who in turn learned it from an Englishman during the 1920s." This variant is now called Baker's Game. FreeCell's origins may date back even further to 1945 and to a Scandinavian game called Napoleon in St. Helena (not the solitaire game Napoleon at St Helena, also known as Forty Thieves). Paul Alfille changed Baker's Game by making cards build according to alternate colors, thus creating FreeCell. He implemented the first computerised version as a medical student at the University of Illinois, in the TUTOR programming language for the PLATO educational computer system in 1978. Alfille was able to display easily recognizable graphical images of playing cards on the monochrome display on the PLATO systems. This original FreeCell environment allowed games with 4–10 columns and 1–10 cells in addition to the standard game. For each variant, the program stored a ranked list of the players with the longest winning streaks. There was also a tournament system that allowed people to compete to win difficult hand-picked deals. Paul Alfille described this early FreeCell environment in more detail in an interview from 2000. In 2012, researchers used evolutionary computation methods to create winning FreeCell players. Other solitaire games related to or inspired by FreeCell include Seahaven Towers, Penguin, Stalactites, ForeCell, Antares (a cross with Scorpion). Solver complexity The FreeCell game has a constant number of cards. This implies that in constant time, a person or computer could list all of the possible moves from a given start configuration and discover a winning set of moves or, assuming the game cannot be solved, the lack thereof. To perform an interesting complexity analysis one must construct a generalized version of the FreeCell game with cards. This generalized version of the game is NP-complete; it is unlikely that any algorithm more efficient than a brute-force search exists that can find solutions for arbitrary generalized FreeCell configurations. There are 52! (i.e., 52 factorial), or