Consider the problem of trying to solve a game of FreeCell in the minimum number

Question

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]. Represent this as a search problem. (a) How would you represent a node/state? (b)What is the goal node? (c) What are the arcs? How would you represent them? Give an admissible heuristic; 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).

Explanation / Answer

The problem can be represented as a graph. Each node will represent the state of the board (it will have the configuration of cards in each home cell and free cell).

The goal node is the one that will have all the cards arranged in 4 home cells with all cards ordered.

The arcs will be represented by a single move of 1 card from one cell to another, that will change the congiguration of the board.

The heuristic that can be used is backtracking with transition from one state to another where a single card is placed in it's true position in the final goal state.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.