Consider the problem of trying to solve a game of FreeCell i

Consider the problem of trying to solve a game of FreeCell in the minimum number of moves. You can play the game at http://www.freecell-cardgame.com/. FreeCell comes standard on nearly every version of Microsoft Windows, and full rules are also available at the Wikipedia entry: “FreeCell”.

The object of FreeCell is to move all the cards to the home cells [foundations], using the free cells as placeholders. To win, make four stacks of cards on the home cells [foundations], one for each suit, stacked in order of rank, from lowest (ace) to highest (king).

• When moving cards to columns, cards must be moved in order from highest (king) to lowest (ace), alternating suit colors.

• When moving cards to home cells [foundations], cards must be moved in order from lowest (ace) to highest (king), same suit.

• A card from the bottom of a column can move to a free cell, the bottom of another column, or a home cell [foundation].

• A card from a free cell can move to the bottom of a column, or to a home cell [foundation].

Give an admissible heuristic for this problem; explain why your heuristic is admissible. More points will be given for tighter lower bounds (h=0 is a trivial heuristic, thus it is not acceptable).

Solution

A)

1.FreeCell is to play all 52 cards onto four piles in the upper right of the screen, starting with the ace of each suit, and continuing with the two, three up to the king of each suit. Any ace which is free can be moved to one of the homecell paces at the upper right. In fact, once you start the game by moving any card, any free aces will be moved there automatically by the program. Once an ace is on a homecell pile, the two of the same suit can be moved there whenever it is free, etc.

Let\'s start play the game, number 5. There are three kinds of legal moves:

-moving a free ace of a suit to a homecell. The ace of diamonds can be moved to any homecell by clicking it once to select it, then clicking on one of the homecells.
-moving any free card to a freecell or an empty column. The nine of spades, seven of clubs, or ten of spades, etc., can be moved to a freecell by clicking it to select it, then clicking on an empty freecell. Once on a freecell, a card is available at any time, and can be moved to a homecell if allowed by rule (1) or onto a column if allowed by rule.
- moving any free card onto another free card, provided it is of the opposite color and one lower in rank. If you\'re familiar with the ordinary kind of solitaire

-free up aces and to start clearing out columns, without using up too many of the freecells. You\'ve already moved the six of hearts onto the seven of clubs. Now try out the following moves in game 5: the six of clubs to a freecell, the queen of diamonds onto the king of spades, the jack of hearts onto the queen of clubs, the jack of spades onto the queen of diamonds. Now move the six of clubs from its freecell onto the seven of diamonds, and the five of hearts onto the six of clubs. The free two of clubs now moves automatically onto the club homecell. We\'re off to a good start, with two homecell piles started, and all four of the freecells empty. Move the ten of clubs onto the jack of hearts, and the nine of hearts onto the ten of clubs. First let\'s continue by working on column 1. Move the nine of spades to a freecell and the two of hearts to another freecell.Move the five of spades onto the six of hearts, and the ten of diamonds onto the jack of spades. Now move the three of spades and the five of clubs each to a freecell, and the ace of hearts and two of hearts automatically move to a new homecell.

4.Normally only one card at a time can be moved, but if you have several cards in sequence you can move them all at once if you have enough freecells empty.Since you have two freecells available, you can move three cards in sequence from the bottom of one column to an empty column, or, provided you are continuing a legal sequence, to the bottom of another column

5.Whenever you try to move a sequence of cards from the bottom of a column to an empty column, the program will put up a dialogue box, asking you whether you want to move a sequence of cards or just a single card. Click on the five of hearts now to select it, then click on the empty sixth column. When the dialogue box comes up, click on theMove Column box. The three-card sequence will then move to the empty sixth column.

6.When you have both empty columns and freecells available, it is possible to move longer sequences. For example, two freecells and an empty column allow you to move up tosix cards in sequence: three of them will temporarily go to the empty column, using the two freecells, the other three will go to the destination column, then the first three will go to the destination.In this case, we want to move five cards from column seven onto the queen of spades in column eight. Select the seven of hearts, and then move the five card sequence onto the eighth column by clicking on the queen.

7.Now we can get to the lower-ranking cards in the seventh column: move the queen of clubs to a freecell, the four of hearts to its homecell Now move the jack of clubs onto the queen of hearts, and the six of spades onto the seven of hearts. Move the three of clubs to its homecell, a perfectly safe move since the two of diamonds can go to its homecell when it is free.

8.Move the five of spades through seven of clubs from column three to column four, the ten of hearts onto the jack of clubs, the eight of clubs onto the nine of diamonds, the queen of clubs from its freecell to the empty seventh column, and the jack of diamonds onto it. Move the king of clubs to a freecell, and the nine of clubs onto the ten of hearts .Move the king of clubs back into the empty third column, and the entire first column onto it. Move the entire second column onto the seventh column, then the sixth column onto the seventh column. These consolidation moves are not necessary in this position, since we have plenty of empty spaces, but it\'s generally good technique to create as much space as possible, and there are times when moves like that are very valuable. The long nine-card sequence at the bottom of the fifth column can be moved in two pieces: first select the five of clubs, then any empty column. Clicking the Move Column button in the dialogue box will move five cards to the empty column you selected. Now select the ten of diamonds, and another empty column, to move the other four cards of the sequence.To finish the game, move the eight of hearts onto the nine of clubs, and the king of diamonds into an empty column. The 38 cards remaining are now in sequence, and will all go automatically to the homecells.