Magic FreeCell

Here's an optimization puzzle. I was tempted to make a contest out of it, like the optimization contests Games Magazine has had in the past, but eh, I just want new blog content, and making a contest would require thought about what to actually give away.

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:
(If this deal doesn't look very random to you, that's because it's not; I got the deal from this video. Note that there is no "What the hell?" card in FreeCell, as surprising as that may be. Also, I got the card graphics from here.)

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.
The goal in FreeCell is to move all 52 cards to the foundations.

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?

2 comments

cyrebjr said...

Did you get my three-cell, 117-move solution?

Grant Fikes said...

cyrebjr: I have seen it, but not checked it. I also have a two-cell solution from a reader who used computer assistance; I optimized it to 113 moves.