In the game of Freecell, you are tasked with building four foundation piles in suit from ace to king, on a layout where you build downward in alternating colours. However, you can only build one card at a time, so you are given four "free cells" each of which can contain one card to help you move entire sequences. The idea is that you weave individual cards in and out of the free cells as required to help you solve the game.
Your task is to build a program that will solve these games in the fewest moves possible.
Your program will take as input a sequence of 52 cards, in the following format:
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...
Which will be dealt in the initial layout in this order:
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
And return a list of moves to solve the game. Each move will be in this format:
- A number representing the pile number (
8), or a free cell (
D), representing the source pile.
- Another number or letter representing the destination pile or free cell, or
Ffor the foundation of that suit.
The output will look something like this:
18 28 3A 8B 8C 85 B5 35 4F etc.
Once a card is put into the foundation, it cannot be removed. Since only one card is moved at a time, moving a sequence of 3 cards requires 5 moves, and a sequence of 5 cards requires 9 moves.
If a game is unsolvable, your program should indicate as such. However, your program must be able to solve any solvable game.
Your program will be judged on the 32,768 deals found in the original Microsoft FreeCell program. In order to be valid, your program must successfully solve every deal except deal #11,982, which is unsolvable. Your score will be the total number of moves it takes to solve these 32,767 deals, with shorter code being a tie-breaker.
A file with all the decks in the format required by the above specification is available for download here (5.00 MB file): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks