一、FreeCell游戏规则与算法目标
FreeCell（空当接龙）是经典的纸牌益智游戏。一副牌52张随机分8列，右上角4个空位为”Home Cell”（按花色从A到K顺序收纳），左上角4个空位为”Free Cell”（临时存放单张牌）。玩家可将牌在列之间移动（必须按交替颜色、降序排列），或放入Free Cell/Home Cell。
本文目标是实现一个自动求解器，核心算法为：
– A*搜索：在巨大的状态空间中寻找最短解路径
– 空位约束传播：利用Free Cell数量限制进行剪枝
– 死锁检测：提前识别无法推进的死局状态
二、状态表示与哈希编码
FreeCell状态包含：8列牌堆、4个Free Cell、4个Home Cell。为支持A*的closed set去重，需要高效的状态哈希。
import java.util.*;
/**
* FreeCell游戏状态
* 使用字符串编码实现快速哈希与去重
*/
public class FreeCellState implements Comparable<FreeCellState> {
// 8列牌堆，每列是一个栈（底到顶）
List<Deque<Card>> columns;
// 4个FreeCell，null表示空
Card[] freeCells;
// 4个HomeCell，记录当前已放置的最大牌面（0表示空）
int[] homeCells; // 0~13，分别对应4种花色
// A*搜索所需字段
int g; // 已走步数
int h; // 启发式估计值
FreeCellState parent; // 父状态，用于路径回溯
String move; // 到达此状态的移动描述
public FreeCellState() {
columns = new ArrayList<>(8);
for (int i = 0; i < 8; i++) columns.add(new ArrayDeque<>());
freeCells = new Card[4];
homeCells = new int[4];
g = 0;
h = 0;
}
/**
* 核心：状态编码为唯一字符串，用于HashSet去重
* 格式：FreeCell|HomeCell|每列牌序列
*/
public String encode() {
StringBuilder sb = new StringBuilder();
// FreeCell编码（按花色排序保证唯一性）
Card[] sortedFree = Arrays.copyOf(freeCells, 4);
Arrays.sort(sortedFree, Comparator.nullsLast(Comparator.comparingInt(c -> c.id)));
for (Card c : sortedFree) sb.append(c == null ? "0" : c.id).append(',');
sb.append('|');
// HomeCell编码
for (int h : homeCells) sb.append(h).append(',');
sb.append('|');
// 列编码：每列从底到顶的牌ID序列
for (Deque<Card> col : columns) {
for (Card c : col) sb.append(c.id).append(',');
sb.append(';');
}
return sb.toString();
}
@Override
public int compareTo(FreeCellState o) {
return Integer.compare(this.g + this.h, o.g + o.h);
}
@Override
public int hashCode() {
return encode().hashCode();
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof FreeCellState)) return false;
return encode().equals(((FreeCellState) obj).encode());
}
}
/**
* 纸牌定义：13点数 × 4花色 = 52张牌
* id范围1~52，便于编码
*/
class Card {
int id; // 1~52
int rank; // 1(A)~13(K)
int suit; // 0=♠,1=♥,2=♣,3=♦
boolean red; // 红色为true（♥♦）
public Card(int id) {
this.id = id;
this.rank = (id - 1) % 13 + 1;
this.suit = (id - 1) / 13;
this.red = (suit == 1 || suit == 3);
}
@Override
public String toString() {
String[] ranks = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
String[] suits = {"♠","♥","♣","♦"};
return ranks[rank-1] + suits[suit];
}
}
三、A*搜索与启发式函数
FreeCell求解本质是状态空间搜索。A*算法需要设计一个可采纳的启发式函数（admissible heuristic），即永远不高估实际代价。
public class FreeCellSolver {
/**
* 启发式函数 h(state)
* 组合多个可采纳启发式，取最大值保持可采纳性
*/
int heuristic(FreeCellState s) {
int h1 = cardsNotInHome(s); // 未归位牌数（最松上界）
int h2 = blockedCards(s); // 被压住无法移动的牌数
int h3 = sequenceBreaks(s); // 列内序列断裂数
return Math.max(Math.max(h1, h2), h3);
}
/** 统计尚未放入HomeCell的牌数 */
int cardsNotInHome(FreeCellState s) {
int count = 0;
for (int h : s.homeCells) count += h;
return 52 - count;
}
/**
* 统计被"锁住"的牌：上方有牌且无法直接放入HomeCell的牌
* 一张牌被锁住当且仅当：
* 1. 它在某列中且上方有牌，或
* 2. 它在FreeCell中但其rank不是当前HomeCell+1
*/
int blockedCards(FreeCellState s) {
int blocked = 0;
// 列中被压住的牌
for (Deque<Card> col : s.columns) {
boolean above = false;
for (Card c : col) {
if (above && !canMoveToHome(s, c)) blocked++;
above = true;
}
}
// FreeCell中无法直接归位的牌
for (Card c : s.freeCells) {
if (c != null && !canMoveToHome(s, c)) blocked++;
}
return blocked;
}
/** 判断一张牌是否可以直接放入HomeCell */
boolean canMoveToHome(FreeCellState s, Card c) {
return s.homeCells[c.suit] == c.rank - 1;
}
/**
* 列内序列断裂数：连续递减交替序列越长，越容易移动
* 断裂点 = 颜色相同 或 非连续递减的位置数
*/
int sequenceBreaks(FreeCellState s) {
int breaks = 0;
for (Deque<Card> col : s.columns) {
Card prev = null;
for (Card c : col) {
if (prev != null) {
if (prev.red == c.red || prev.rank != c.rank + 1) {
breaks++;
}
}
prev = c;
}
}
return breaks;
}
/**
* A*搜索主算法
*/
public List<String> solve(FreeCellState initial) {
PriorityQueue<FreeCellState> open = new PriorityQueue<>();
Set<String> closed = new HashSet<>();
initial.h = heuristic(initial);
open.add(initial);
closed.add(initial.encode());
int explored = 0;
while (!open.isEmpty()) {
FreeCellState cur = open.poll();
explored++;
// 终止条件：所有牌归位
if (isGoal(cur)) {
return reconstructPath(cur);
}
// 生成所有合法移动
for (FreeCellState next : generateMoves(cur)) {
String enc = next.encode();
if (closed.contains(enc)) continue;
next.h = heuristic(next);
next.g = cur.g + 1;
next.parent = cur;
// 死锁检测剪枝
if (isDeadlock(next)) continue;
open.add(next);
closed.add(enc);
}
// 搜索深度限制，防止无限搜索
if (explored > 5_000_000) {
System.out.println("Search limit exceeded, no solution found within bound.");
return null;
}
}
return null; // 无解
}
boolean isGoal(FreeCellState s) {
for (int h : s.homeCells) if (h != 13) return false;
return true;
}
List<String> reconstructPath(FreeCellState goal) {
List<String> path = new ArrayList<>();
FreeCellState cur = goal;
while (cur != null && cur.move != null) {
path.add(cur.move);
cur = cur.parent;
}
Collections.reverse(path);
return path;
}
}
四、移动生成与约束传播
移动生成是A*的性能瓶颈。需要高效枚举所有合法移动，并利用超级移动（supermove）将多个步骤压缩为一次状态转移。
public class FreeCellSolver {
/**
* 生成所有合法后继状态
* 包含：单牌移动、序列移动、自动归位
*/
List<FreeCellState> generateMoves(FreeCellState s) {
List<FreeCellState> moves = new ArrayList<>();
// 1. 自动归位：任何可以直接放入HomeCell的牌立即移动
// 这是FreeCell的确定性规则，减少分支因子
boolean moved = true;
while (moved) {
moved = false;
// 检查列顶牌
for (int i = 0; i < 8; i++) {
Deque<Card> col = s.columns.get(i);
if (col.isEmpty()) continue;
Card top = col.peekLast();
if (canMoveToHome(s, top)) {
s = cloneAndMoveToHome(s, i, -1); // -1表示来自列
moved = true;
break;
}
}
// 检查FreeCell
if (!moved) {
for (int i = 0; i < 4; i++) {
Card c = s.freeCells[i];
if (c != null && canMoveToHome(s, c)) {
s = cloneAndMoveToHome(s, -1, i);
moved = true;
break;
}
}
}
}
// 2. 列顶牌 → FreeCell
for (int i = 0; i < 8; i++) {
if (s.columns.get(i).isEmpty()) continue;
for (int j = 0; j < 4; j++) {
if (s.freeCells[j] == null) {
moves.add(cloneAndMoveToFreeCell(s, i, j));
}
}
}
// 3. 列顶牌 → 其他列（可移动整个合法序列）
for (int from = 0; from < 8; from++) {
Deque<Card> src = s.columns.get(from);
if (src.isEmpty()) continue;
// 计算从该列可移动的最大序列长度
int maxMove = maxMovableSequence(s);
List<Card> seq = getTopSequence(src, maxMove);
for (int to = 0; to < 8; to++) {
if (from == to) continue;
Deque<Card> dst = s.columns.get(to);
Card dstTop = dst.isEmpty() ? null : dst.peekLast();
// 尝试移动长度为1~seq.size()的序列
for (int len = 1; len <= seq.size(); len++) {
Card moveCard = seq.get(len - 1);
if (canPlaceOn(moveCard, dstTop)) {
moves.add(cloneAndMoveSequence(s, from, to, len));
break; // longer sequences handled by recursive supermoves
}
}
}
}
// 4. FreeCell → 列
for (int i = 0; i < 4; i++) {
Card c = s.freeCells[i];
if (c == null) continue;
for (int to = 0; to < 8; to++) {
Deque<Card> dst = s.columns.get(to);
Card dstTop = dst.isEmpty() ? null : dst.peekLast();
if (canPlaceOn(c, dstTop)) {
moves.add(cloneAndMoveFreeToCol(s, i, to));
}
}
}
return moves;
}
/**
* 计算当前状态下可移动的最大序列长度
* 公式：空FreeCell数 + 1 的 空列数 + 1 次方
* 经典FreeCell理论：可移动序列长度 = (f+1) * 2^e，其中f=空FreeCell数，e=空列数
*/
int maxMovableSequence(FreeCellState s) {
int freeCellsEmpty = 0;
for (Card c : s.freeCells) if (c == null) freeCellsEmpty++;
int emptyCols = 0;
for (Deque<Card> col : s.columns) if (col.isEmpty()) emptyCols++;
// 保守估计：(freeCellsEmpty + 1) * (1 << emptyCols)
return (freeCellsEmpty + 1) * (1 << emptyCols);
}
/** 获取列顶的可移动序列（最长连续交替降序） */
List<Card> getTopSequence(Deque<Card> col, int maxLen) {
List<Card> seq = new ArrayList<>();
Card prev = null;
for (Card c : col) {
if (prev == null || (prev.red != c.red && prev.rank == c.rank + 1)) {
seq.add(c);
if (seq.size() >= maxLen) break;
} else {
break;
}
prev = c;
}
return seq;
}
boolean canPlaceOn(Card src, Card dst) {
if (dst == null) return true; // 空列可放
return src.red != dst.red && src.rank == dst.rank - 1;
}
// 以下为cloneAndMoveXxx辅助方法，实现状态拷贝与移动...
// （为节省篇幅，此处省略具体实现，完整代码包含深拷贝与移动逻辑）
}
五、死锁检测
死锁检测能提前剪掉大量无效分支。常见死锁场景包括：
- 同色压牌：同一列中两张同花色、rank相邻的牌按错误顺序堆叠
- King陷阱：所有空列被King占据且无法引出
- FreeCell满载：4个FreeCell都被非HomeCell-ready牌占据，且列顶无法互相移动
public class FreeCellSolver {
/**
* 死锁检测：判断当前状态是否已进入死局
*/
boolean isDeadlock(FreeCellState s) {
// 检测1：FreeCell全满且列顶无法互相移动、无法归位
int freeFull = 0;
for (Card c : s.freeCells) if (c != null) freeFull++;
if (freeFull == 4) {
boolean anyMove = false;
// 检查列顶牌是否可以归位或移动到别的列
for (int i = 0; i < 8; i++) {
Deque<Card> col = s.columns.get(i);
if (col.isEmpty()) { anyMove = true; break; }
Card top = col.peekLast();
if (canMoveToHome(s, top)) { anyMove = true; break; }
for (int j = 0; j < 8; j++) {
if (i == j) continue;
Deque<Card> dst = s.columns.get(j);
Card dstTop = dst.isEmpty() ? null : dst.peekLast();
if (canPlaceOn(top, dstTop)) { anyMove = true; break; }
}
if (anyMove) break;
}
if (!anyMove) return true; // 完全锁死
}
// 检测2：某列中低rank牌被同花色的高rank牌压住，且中间无交替颜色牌
for (Deque<Card> col : s.columns) {
List<Card> list = new ArrayList<>(col);
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
Card a = list.get(i), b = list.get(j);
if (a.suit == b.suit && a.rank > b.rank) {
// 检查i到j之间是否有合法序列允许b被移出
boolean validSequence = true;
for (int k = i + 1; k <= j; k++) {
Card prev = list.get(k - 1), cur = list.get(k);
if (prev.red == cur.red || prev.rank != cur.rank + 1) {
validSequence = false; break;
}
}
if (!validSequence) return true; // b被同色大rank牌锁住
}
}
}
}
return false;
}
}
六、主程序与复杂度分析
public class FreeCellMain {
public static void main(String[] args) {
// 初始化一个随机牌局（Microsoft FreeCell #1为经典测试用例）
FreeCellState initial = dealGame(1);
FreeCellSolver solver = new FreeCellSolver();
long start = System.currentTimeMillis();
List<String> solution = solver.solve(initial);
long time = System.currentTimeMillis() - start;
if (solution != null) {
System.out.println("Solution found in " + solution.size() + " moves!");
System.out.println("Time: " + time + "ms");
for (int i = 0; i < Math.min(solution.size(), 20); i++) {
System.out.println((i+1) + ". " + solution.get(i));
}
if (solution.size() > 20) System.out.println("... (" + (solution.size()-20) + " more moves)");
} else {
System.out.println("No solution found.");
}
}
/** 发牌：使用确定性的伪随机序列模拟经典FreeCell牌局 */
static FreeCellState dealGame(int seed) {
FreeCellState s = new FreeCellState();
List<Card> deck = new ArrayList<>();
for (int i = 1; i <= 52; i++) deck.add(new Card(i));
// 线性同余发牌器（Microsoft FreeCell标准）
long state = seed;
for (int i = 51; i >= 0; i--) {
state = (state * 214013 + 2531011) & 0xFFFFFFFFL;
int j = (int)((state >> 16) % (i + 1));
Collections.swap(deck, i, j);
}
// 8列发牌：前4列7张，后4列6张
int idx = 0;
for (int col = 0; col < 8; col++) {
int count = (col < 4) ? 7 : 6;
for (int i = 0; i < count; i++) {
s.columns.get(col).addLast(deck.get(idx++));
}
}
return s;
}
}
复杂度分析：
– 状态空间：FreeCell约52!/(8!·4!·4!)量级，实际可达状态约10^20
– A*分支因子：平均约5~10（自动归位大幅降低分支）
– 时间复杂度：依赖启发式质量，实际通常在数秒内求解
– 空间复杂度：O(b^d)，其中b为分支因子，d为解深度（典型解60~100步）
七、总结
本文从FreeCell的状态编码出发，实现了完整的A*自动求解器。核心收获：
1. 可采纳启发式的设计原则：组合多个下界取最大值
2. 超级移动压缩搜索深度：利用空位公式一次移动长序列
3. 约束传播与死锁检测：自动归位和死锁剪枝将分支因子降低一个数量级
4. 状态哈希：排序无关编码保证HashSet去重效率
FreeCell已被数学证明几乎所有牌局可解（约99.999%），是研究启发式搜索的经典案例。
