FreeCell Puzzle Protocol DocumentPage 1 of 7

AI Puzzle Framework

FreeCell Puzzle
Protocol Document

Brian Shaver

April 11, 2005

Table of Contents

Table of Contents

Introduction

Puzzle Description

Rules

Board State

Flags

Representation

Sample Board Layout File

Module Requirements

Puzzle Number

Puzzle Module

Board Module

Player Module

Introduction

Puzzle Description

FreeCell is a card game which utilizes 1 (one) standard 52 card deck of cards. These cards are all dealt face-up into 8 tableau piles, and by moving cards between stacks, and using the 4 (four) “free cell” locations, the goal is to have all cards placed on the 4 (four) foundation piles ordered by value, and separated by suit.

Rules

  1. A card is a piece with a value and a suit.
  2. A suit is one of 4 (four) sub-categories that cards can be divided into. The four suits are Spades (♠, black), Hearts (♥, red), Clubs (♣, black), and Diamonds (♦, red).
  3. The value of a card is between 1 and 13, inclusive. A 1 is represented as an Ace (or simply “A”), values 2 through 10, inclusive, are represented as their numeric values (2-10), and values 11, 12, and 13 are represented as Jack (“J”), Queen (“Q”), and King (“K”) respectively.
  4. A tableau pile is a stack of cards that may contain between 0 (zero) and 19 cards, inclusive.
  5. A free cell is a location which can contain at between 0 (zero) and 1 (one) cards, inclusive, of any value or suit.
  6. A foundation pile is a stack of cards that may contain between 0 (zero) and 13 cards, inclusive. All cards in a given foundation pile must be of the same suit, and must be stacked in the following order (from bottom to top): A-1-2-3-4-5-6-7-8-9-10-J-Q-K.
  7. The boardfor FreeCell consists of 4 (four) free cell locations, 4 (four) foundation piles, and 8 (eight) tableau piles.
  8. Initially, cards are randomly shuffled and dealt face-up onto the tableau piles, from left to right, until all 52 cards have been dealt. The number of cards in each pile, from left to right must be 7, 7, 7, 7, 6, 6, 6, 6. The free cells and foundation piles must initially be empty.
  9. A move consists of the relocation of the top 1 (one) card from either a tableau pile or a free cell to a valid location on a free cell, tableau pile, or foundation pile.
  10. A card can only be moved to a tableau pile if the pile is empty (contains no cards), or if the top card on the pile is of the opposite color (either red or black) and the immediately following value as the card which is being moved to the pile. For example, a red 4 can only be moved to an empty pile or a pile with a black 5 on top.
  11. A card can only be moved to a foundation pile if the card of the same suit with the immediately preceding value has already been placed on the given foundation pile. For example, a 4 of diamonds can only be moved to a foundation pile which has a 3 of diamonds on top. An Ace can only be moved to a foundation pile which is empty.
  12. A card can only be moved to a free cell which is empty. Any card can be placed on a free cell.
  13. A card cannot be moved from a foundation pile at any time.
  14. A solution to the puzzle is defined as a series of moves which ends with all the cards located on the foundation piles.
  15. Every puzzle which has a solution will have an optimal solution, such that the total number of moves for the solution is the lowest of all the total moves for any possible solution in the given puzzle.
  16. The overall goal for the player is to find an optimal solution to the puzzle.
  17. It is possible to “lose” the puzzle if there are no moves remaining and all 52 cards are not located on the foundation piles.

BoardState

Flags

The following flags are used by the FreeCell Puzzle when configuring the board state:

Flag / Purpose
USE_TIME / Count time for the puzzle
USE_MOVES / Count moves for the puzzle
LIMIT_NONE / Do not limit the puzzle based on time or moves

Representation

See Appendix A for a quick conversion table. TheFreeCell Puzzle board state is represented internally and in .puz layout files as follows (which corresponding ASCII values in base 10):

Character / ASCII
Value / Meaning
Space / 32 / Unoccupied space
[A,M] / [65,77] / Ace through King of Spades, respectively
[N,Z] / [78,90] / Ace through King of Clubs, respectively
[a,m] / [97,109] / Ace through King of Hearts, respectively
[n,z] / [110,122] / Ace through King of Diamonds, respectively

Representation Tips

The first row of the board layout is used to represent the 4 (four) free cells followed by the 4 (four) foundation piles. Each column of the board layout represents 1 (one) tableau pile (with the exception of the first row, as previously noted). Thus, location (0,1) represents the lowest position on the first tableau pile on the left, (3,5) represents the fifthcard (counting from the bottom) on the fourth tableau pile, (2,0) represents the third free cell (counting from the left), and (5,0) represents the second foundation pile.

The value placed on the foundation pile space represents the value of the top card on that pile. It can be assumed that all cards of the same suit with a value less than that of the top card are located, in order, below the top card.

More specific information about different cards based off their ASCII text value can be found using several quick mathematical operations:

  1. The color of the card can be found easily, because black cards have a value between 65 and 90, inclusive, while red cards have a value between 97 and 122, inclusive.
  2. The value of the card (independent of its suit) can be found by taking the value of the card, subtracting 6 if it is a red card or 0 if it is black, doing modulus division by 13 on the resulting value, and finally adding 1. This will give the numeric value of the card.

value = ((A<97?A:(A-6))%13)+1;

Sample Board Layout File

Following the standards for board layout files (.puz files) defined in theModuleDeveloper Guide, the following is a sample board layout file for the FreeCell Puzzle:

5

208

0 0

0 0

0 0

FbRZPvIr

ekYOUTfX

dnygxuwm

NKiAEqJz

BVMLWSoc

phCjHtlG

DQas

Module Requirements

Puzzle Number

The FreeCell Puzzle has a puzzle identification number (puzID) of 5(five), which must be set in the LibraryInfo for each of the modules, and for the board layout files intended for use with the FreeCell Puzzle. Use of any other number will cause the given module or layout file to not work correctly with the given puzzle, and may also conflict with other, previously defined puzzle ID numbers.

Puzzle Module

For the FreeCell Puzzle, the puzzle module will contain an initial state, and it will not be loaded from a .puz board layout file initially. The puzzle module should generate and return a new random state when the getInitialStatefunction is called. For this reason, the hasInitialState function should always return true. Also, the checkBoardState function is still required, because the user can still save and load board layouts from a file. The board state is fully visible to the player at all times, so the full board state should always be returned by the module.

Board Module

The board module must be sure to display the cards in the tableau piles in such a way that the user can see the value and suit of all the cards in the pile. For foundation piles, only the top card must be visible.

The board module does not have to be able to handle keyboard movements from the user, because the user can move any card at any time. Mouse movements should be handled when the user clicks on the pile or free cell which has a card to move and the pile to move the top card to.

Player Module

No special requirements are necessary for the player module in the FreeCell Puzzle. It is important to note, however, that not all moves can be backtracked to the previous state; thus, the puzzle can be lost if there are no valid moves left to be made.

Appendix A – Conversion Table

AI Puzzle Framework •

FreeCell Puzzle Protocol DocumentPage 1 of 7

Character Conversion / Spades (♠) / Clubs (♣) / Hearts (♥) / Diamonds (♦)
1 – Ace / A / N / a / n
2 / B / O / b / o
3 / C / P / c / p
4 / D / Q / d / q
5 / E / R / e / r
6 / F / S / f / s
7 / G / T / g / t
8 / H / U / h / u
9 / I / V / i / v
10 / J / W / j / w
11 – Jack / K / X / k / x
12 – Queen / L / Y / l / y
13 – King / M / Z / m / z
ASCII Val. Conversion / Spades (♠) / Clubs (♣) / Hearts (♥) / Diamonds (♦)
1 – Ace / 65 / 78 / 97 / 110
2 / 66 / 79 / 98 / 111
3 / 67 / 80 / 99 / 112
4 / 68 / 81 / 100 / 113
5 / 69 / 82 / 101 / 114
6 / 70 / 83 / 102 / 115
7 / 71 / 84 / 103 / 116
8 / 72 / 85 / 104 / 117
9 / 73 / 86 / 105 / 118
10 / 74 / 87 / 106 / 119
11 – Jack / 75 / 88 / 107 / 120
12 – Queen / 76 / 89 / 108 / 121
13 – King / 77 / 90 / 109 / 122

AI Puzzle Framework •