引言
自由细胞（FreeCell）是Windows系统自带的一款经典纸牌接龙游戏。与多数纸牌游戏不同，FreeCell的几乎所有牌局都是可解的（约99.999%），这使得它成为研究搜索算法的理想对象。本文用Java实现FreeCell的核心求解器，采用深度优先回溯搜索配合空位调度启发式，演示如何系统地探索巨大的纸牌状态空间。
游戏规则与状态建模
FreeCell使用一副标准52张扑克牌，布局如下：
– 8个级联列（Cascades）：初始时每列发牌，前4列7张、后4列6张；
– 4个自由细胞（FreeCells）：临时存放单张牌的空位；
– 4个目标基座（Foundations）：按花色从A到K依次构建的收牌区。
移动规则：
1. 级联列中的牌可按红黑交替、点数递减的规则移动；
2. 自由细胞每次只能放一张牌；
3. 目标基座按同花色、点数递增收牌；
4. 一次可移动的牌组数量受空自由细胞与空级列数限制。
可移动牌组数量的计算
这是FreeCell搜索的核心约束。假设有 f 个空自由细胞、e 个空级列，则一次可移动的连续递减牌组最大长度为：
maxMove = (f + 1) × 2^e
该公式源于：每多一个空自由细胞可多带1张牌；每多一个空级列，可借助其作为中转站实现指数级倍增。
Java实现
import java.util.*;
/**
* FreeCell 求解器：回溯搜索 + 空位调度启发式
*/
public class FreeCellSolver {
// 牌面编码：0~51，花色=suit/13，点数=rank%13（0=A,12=K）
static final int SUITS = 4;
static final int RANKS = 13;
static final int TOTAL_CARDS = 52;
/**
* 游戏状态：级联列 + 自由细胞 + 目标基座
*/
static class State {
List<Deque<Integer>> cascades; // 8个级联列，每列是一个栈
Integer[] freeCells; // 4个自由细胞，null表示空
int[] foundations; // 4个目标基座当前最高点数（-1表示空）
int moveCount; // 已走步数
State parent; // 前驱状态（用于回溯）
String moveDesc; // 移动描述
State() {
cascades = new ArrayList<>();
for (int i = 0; i < 8; i++) cascades.add(new ArrayDeque<>());
freeCells = new Integer[4];
foundations = new int[]{-1, -1, -1, -1};
moveCount = 0;
}
@Override
public int hashCode() {
int h = Arrays.hashCode(freeCells);
h = h * 31 + Arrays.hashCode(foundations);
for (Deque<Integer> col : cascades) {
h = h * 31 + col.hashCode();
}
return h;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof State)) return false;
State other = (State) o;
return Arrays.equals(freeCells, other.freeCells)
&& Arrays.equals(foundations, other.foundations)
&& cascadesEquals(other.cascades);
}
boolean cascadesEquals(List<Deque<Integer>> other) {
if (cascades.size() != other.size()) return false;
for (int i = 0; i < cascades.size(); i++) {
if (!cascades.get(i).equals(other.get(i))) return false;
}
return true;
}
State copy() {
State s = new State();
for (int i = 0; i < 8; i++) {
s.cascades.set(i, new ArrayDeque<>(cascades.get(i)));
}
s.freeCells = freeCells.clone();
s.foundations = foundations.clone();
s.moveCount = moveCount;
return s;
}
}
static int suit(int card) { return card / RANKS; }
static int rank(int card) { return card % RANKS; }
static boolean isRed(int card) { return suit(card) < 2; }
static boolean canPlaceOnCascade(int top, int card) {
return isRed(top) != isRed(card) && rank(top) == rank(card) + 1;
}
static int maxMovableSequence(State s) {
int freeCount = 0;
for (Integer c : s.freeCells) if (c == null) freeCount++;
int emptyCascade = 0;
for (Deque<Integer> col : s.cascades) if (col.isEmpty()) emptyCascade++;
return (freeCount + 1) * (1 << emptyCascade);
}
static List<Integer> getMovableSequence(Deque<Integer> col) {
List<Integer> seq = new ArrayList<>();
if (col.isEmpty()) return seq;
Iterator<Integer> it = col.descendingIterator();
int prev = -1;
while (it.hasNext()) {
int card = it.next();
if (prev == -1 || canPlaceOnCascade(prev, card)) {
seq.add(card);
prev = card;
} else {
break;
}
}
return seq;
}
static List<State> generateMoves(State s) {
List<State> moves = new ArrayList<>();
int maxMove = maxMovableSequence(s);
// 1. 尝试将牌直接移到目标基座（优先操作，加速收敛）
for (int i = 0; i < 4; i++) {
if (s.freeCells[i] != null) {
int card = s.freeCells[i];
if (canMoveToFoundation(s, card)) {
State ns = s.copy();
ns.freeCells[i] = null;
ns.foundations[suit(card)] = rank(card);
ns.moveCount = s.moveCount + 1;
ns.parent = s;
ns.moveDesc = "FreeCell " + cardName(card) + " -> Foundation";
moves.add(ns);
}
}
}
for (int c = 0; c < 8; c++) {
Deque<Integer> col = s.cascades.get(c);
if (!col.isEmpty()) {
int card = col.peekLast();
if (canMoveToFoundation(s, card)) {
State ns = s.copy();
ns.cascades.get(c).pollLast();
ns.foundations[suit(card)] = rank(card);
ns.moveCount = s.moveCount + 1;
ns.parent = s;
ns.moveDesc = "Cascade " + c + " " + cardName(card) + " -> Foundation";
moves.add(ns);
}
}
}
// 2. 级联列之间的移动
for (int src = 0; src < 8; src++) {
List<Integer> seq = getMovableSequence(s.cascades.get(src));
int maxLen = Math.min(seq.size(), maxMove);
for (int len = 1; len <= maxLen; len++) {
int topCard = seq.get(len - 1);
for (int dst = 0; dst < 8; dst++) {
if (src == dst) continue;
Deque<Integer> dstCol = s.cascades.get(dst);
if (dstCol.isEmpty() || canPlaceOnCascade(dstCol.peekLast(), topCard)) {
State ns = s.copy();
Deque<Integer> srcCol = ns.cascades.get(src);
List<Integer> moved = new ArrayList<>();
for (int k = 0; k < len; k++) moved.add(srcCol.pollLast());
Collections.reverse(moved);
for (int card : moved) ns.cascades.get(dst).addLast(card);
ns.moveCount = s.moveCount + 1;
ns.parent = s;
ns.moveDesc = "Cascade " + src + " -> " + dst + " (" + len + " cards)";
moves.add(ns);
}
}
}
}
// 3. 级联列 -> 自由细胞
for (int c = 0; c < 8; c++) {
if (s.cascades.get(c).isEmpty()) continue;
for (int f = 0; f < 4; f++) {
if (s.freeCells[f] == null) {
State ns = s.copy();
int card = ns.cascades.get(c).pollLast();
ns.freeCells[f] = card;
ns.moveCount = s.moveCount + 1;
ns.parent = s;
ns.moveDesc = "Cascade " + c + " " + cardName(card) + " -> FreeCell";
moves.add(ns);
break;
}
}
}
// 4. 自由细胞 -> 级联列
for (int f = 0; f < 4; f++) {
if (s.freeCells[f] == null) continue;
int card = s.freeCells[f];
for (int c = 0; c < 8; c++) {
Deque<Integer> col = s.cascades.get(c);
if (col.isEmpty() || canPlaceOnCascade(col.peekLast(), card)) {
State ns = s.copy();
ns.freeCells[f] = null;
ns.cascades.get(c).addLast(card);
ns.moveCount = s.moveCount + 1;
ns.parent = s;
ns.moveDesc = "FreeCell " + cardName(card) + " -> Cascade " + c;
moves.add(ns);
}
}
}
return moves;
}
static boolean canMoveToFoundation(State s, int card) {
return rank(card) == s.foundations[suit(card)] + 1;
}
static String cardName(int card) {
String[] suits = {"♠", "♥", "♦", "♣"};
String[] ranks = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
return ranks[rank(card)] + suits[suit(card)];
}
static boolean isSolved(State s) {
for (int f : s.foundations) {
if (f != RANKS - 1) return false;
}
return true;
}
static int heuristic(State s) {
int sum = 0;
for (int f : s.foundations) sum += f + 1;
int freeCount = 0;
for (Integer c : s.freeCells) if (c == null) freeCount++;
return sum * 10 + freeCount;
}
static State solve(State initial, int maxDepth) {
Set<Integer> visited = new HashSet<>();
return dfs(initial, 0, maxDepth, visited);
}
static State dfs(State s, int depth, int maxDepth, Set<Integer> visited) {
if (isSolved(s)) return s;
if (depth >= maxDepth) return null;
int hash = s.hashCode();
if (visited.contains(hash)) return null;
visited.add(hash);
List<State> moves = generateMoves(s);
moves.sort((a, b) -> heuristic(b) - heuristic(a));
for (State next : moves) {
State result = dfs(next, depth + 1, maxDepth, visited);
if (result != null) return result;
}
visited.remove(hash);
return null;
}
static State iddfsSolve(State initial) {
for (int depth = 1; depth <= 200; depth++) {
System.out.println("尝试深度限制：" + depth);
Set<Integer> visited = new HashSet<>();
State result = dfs(initial, 0, depth, visited);
if (result != null) return result;
}
return null;
}
static void printSolution(State goal) {
List<String> path = new ArrayList<>();
State cur = goal;
while (cur.parent != null) {
path.add(cur.moveDesc);
cur = cur.parent;
}
Collections.reverse(path);
System.out.println("\n解法步数：" + path.size());
for (int i = 0; i < path.size(); i++) {
System.out.println((i + 1) + ". " + path.get(i));
}
}
static State createSimpleState() {
State s = new State();
int card = 0;
for (int c = 0; c < 4; c++) {
for (int r = 0; r < 3; r++) {
s.cascades.get(c).addLast(card++);
}
}
return s;
}
public static void main(String[] args) {
State initial = createSimpleState();
System.out.println("开始求解简化版 FreeCell...");
State goal = iddfsSolve(initial);
if (goal != null) {
System.out.println("求解成功！");
printSolution(goal);
} else {
System.out.println("未找到解法（在搜索深度限制内）。");
}
}
}
复杂度分析
- 状态空间：52张牌的排列极为庞大，但实际可达状态受规则约束。
- 分支因子：平均每步约20~40种合法移动。
- 时间复杂度：
O(b^d)，其中b为分支因子，d为解深度。迭代加深将空间控制在O(bd)。 - 优化手段：优先将可收牌移至基座、启发式排序减少无效搜索、哈希判重避免循环状态。
总结
FreeCell求解器展示了回溯搜索在组合博弈中的应用。核心难点在于状态表示的精确性、可移动牌组数量的正确计算，以及搜索策略的剪枝效率。本文的框架可进一步扩展为完整52张牌求解器，引入更强的启发式（如优先清空列、避免将低牌压在高牌下）和双向搜索，以应对真实牌局的挑战。
