Almost everyone is familiar with FreeCell. It is a solitaire card game in which a standard deck of cards is dealt into 8 columns (four of which have 7 cards, and four of which have 6 cards). Here's a layout:
A move in FreeCell constitutes one of the following actions:
- Moving the bottom card of any column in the tableau to one of four "cells". Each cell can hold only one card.
- Moving the bottom card of any column, or a card in the cells, to the bottom of another column. An empty column can accept any card; otherwise, you can only place a card on top of a card of the opposite color and the next higher rank. (Ranks are, from lowest to highest, A 2 3 4 5 6 7 8 9 10 J Q K.)
- Moving the bottom card of any column, or a card in the cells, to the foundations. An Ace can be played to the foundations at any time. Any other card can only be played if the next lowest card of the same suit has been played.
For this optimization problem, your goal is to win the game using as few cells as possible, and then in as few moves as possible using that number of cells (so 200 moves with 0 cells is better than 100 moves with 1 cell). To make the game more challenging, and to stymie automatic FreeCell solvers as far as I am aware, I am adding one additional constraint: all four cards of a particular rank must be played to the foundations in what magicians call "chased" order (Clubs, Hearts, Spades, Diamonds). Almost any software implementation of FreeCell will automatically play the Ace and Two of Spades and Ace of Diamonds to the foundations after the first move; this is no longer allowed, as the Ace of Spades cannot be played to the foundations without the Ace of Hearts, and the Ace of Diamonds cannot be played to the foundations without the Ace of Spades.
Edit: Here's a solution I found to get the ball rolling. It uses 4 cells and 114 moves. Can you do it using fewer cells, or in fewer moves using 4 cells?
