引言
空当接龙（FreeCell）是Windows系统自带的一款经典纸牌游戏，以其极高的可解率（超过99%的牌局有解）而闻名。与许多纸牌游戏依赖运气不同，空当接龙几乎纯粹是技巧的考验。
本文将用Java实现空当接龙的自动求解器，核心算法采用A*搜索结合精心设计的启发式函数，在庞大的状态空间中高效寻找最优解。
游戏规则与状态表示
游戏规则
- 牌桌布局：8列牌叠（Cascade）、4个空闲单元（FreeCell）、4个目标堆（Foundation）
- 移动规则：
- 牌叠中的牌按降序、红黑交替排列
- 任意单张牌可移至空闲单元（每单元最多一张）
- A可移至目标堆，同花色牌按升序（A-2-3-…-K）依次叠加到目标堆
- 空的牌叠可放置任意牌
- 胜利条件：所有52张牌按花色分别移至4个目标堆
状态表示
一个状态需要完整描述52张牌的位置：
// 状态表示的关键要素
- cascade[8]: 8列牌叠，每列是一个栈（列表）
- freeCell[4]: 4个空闲单元，null表示空
- foundation[4]: 4个目标堆，记录当前顶部牌面值（0~13）
核心算法：A*搜索
A*搜索是寻路算法中的经典方法，其评估函数为：
$$f(n) = g(n) + h(n)$$
其中：
– $g(n)$：从初始状态到当前状态的代价（步数）
– $h(n)$：启发式函数，估计从当前状态到目标的代价
启发式函数设计
好的启发式函数是A*搜索效率的关键。我们采用多因素加权组合：
- ** foundation完成度**：已移至目标堆的牌数（最大化）
- 空闲单元利用率：空闲单元为空是危险信号
- 牌叠有序度：每列中按规则排列的连续牌组数量
- 埋深度：目标牌（如A）被压在下面的层数
Java实现
项目结构
freecell-solver/
├── src/
│ └── com/
│ └── freecell/
│ ├── Card.java // 扑克牌表示
│ ├── GameState.java // 游戏状态
│ ├── Move.java // 移动操作
│ ├── Heuristic.java // 启发式函数
│ ├── AStarSolver.java // A*求解器
│ └── Main.java // 入口
扑克牌与游戏状态
package com.freecell;
import java.util.*;
/**
* 扑克牌类
*/
class Card {
enum Suit { SPADES, HEARTS, CLUBS, DIAMONDS }
enum Color { BLACK, RED }
final Suit suit;
final int rank; // 1=A, 11=J, 12=Q, 13=K
Card(Suit suit, int rank) {
this.suit = suit;
this.rank = rank;
}
Color color() {
return (suit == Suit.SPADES || suit == Suit.CLUBS) ? Color.BLACK : Color.RED;
}
boolean canPlaceOnCascade(Card other) {
if (other == null) return true;
return this.color() != other.color() && this.rank == other.rank - 1;
}
boolean canPlaceOnFoundation(int topRank) {
return this.rank == topRank + 1;
}
@Override
public String toString() {
String[] ranks = {"", "A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
String[] suits = {"♠", "♥", "♣", "♦"};
return ranks[rank] + suits[suit.ordinal()];
}
}
/**
* 移动操作
*/
class Move {
enum Type { CASCADE_TO_CASCADE, CASCADE_TO_FREECELL, CASCADE_TO_FOUNDATION,
FREECELL_TO_CASCADE, FREECELL_TO_FOUNDATION }
final Type type;
final int from; // 源位置索引
final int to; // 目标位置索引
final int count; // 移动的牌数（级联移动时可能>1）
Move(Type type, int from, int to, int count) {
this.type = type;
this.from = from;
this.to = to;
this.count = count;
}
@Override
public String toString() {
return String.format("%s: %d -> %d (x%d)", type, from, to, count);
}
}
/**
* 游戏状态
*/
class GameState implements Comparable<GameState> {
final List<Card>[] cascade; // 8列牌叠
final Card[] freeCell; // 4个空闲单元
final int[] foundation; // 4个目标堆当前顶部值（0=空）
int gScore; // 从初始状态到当前状态的步数
int hScore; // 启发式估计值
GameState parent; // 父状态（用于回溯解路径）
Move moveFromParent; // 从父状态到当前状态的移动
@SuppressWarnings("unchecked")
GameState() {
cascade = new ArrayList[8];
for (int i = 0; i < 8; i++) cascade[i] = new ArrayList<>();
freeCell = new Card[4];
foundation = new int[4]; // 全部初始化为0
}
/**
* 深拷贝构造函数
*/
@SuppressWarnings("unchecked")
GameState(GameState other) {
cascade = new ArrayList[8];
for (int i = 0; i < 8; i++) {
cascade[i] = new ArrayList<>(other.cascade[i]);
}
freeCell = other.freeCell.clone();
foundation = other.foundation.clone();
}
/**
* 生成所有可能的合法移动
*/
List<Move> generateMoves() {
List<Move> moves = new ArrayList<>();
int emptyFreeCells = 0;
for (Card c : freeCell) if (c == null) emptyFreeCells++;
int emptyCascades = 0;
for (List<Card> col : cascade) if (col.isEmpty()) emptyCascades++;
// 1. 牌叠 -> 目标堆（优先，通常是好移动）
for (int i = 0; i < 8; i++) {
if (cascade[i].isEmpty()) continue;
Card card = cascade[i].get(cascade[i].size() - 1);
int suitIdx = card.suit.ordinal();
if (card.canPlaceOnFoundation(foundation[suitIdx])) {
moves.add(new Move(Move.Type.CASCADE_TO_FOUNDATION, i, suitIdx, 1));
}
}
// 2. 空闲单元 -> 目标堆
for (int i = 0; i < 4; i++) {
if (freeCell[i] == null) continue;
Card card = freeCell[i];
int suitIdx = card.suit.ordinal();
if (card.canPlaceOnFoundation(foundation[suitIdx])) {
moves.add(new Move(Move.Type.FREECELL_TO_FOUNDATION, i, suitIdx, 1));
}
}
// 3. 牌叠 -> 空闲单元
for (int i = 0; i < 8; i++) {
if (cascade[i].isEmpty()) continue;
for (int j = 0; j < 4; j++) {
if (freeCell[j] == null) {
moves.add(new Move(Move.Type.CASCADE_TO_FREECELL, i, j, 1));
break; // 任意空闲单元等价，只添加一个
}
}
}
// 4. 牌叠 -> 牌叠（单张或级联移动）
for (int from = 0; from < 8; from++) {
if (cascade[from].isEmpty()) continue;
// 找到可移动的连续序列
int seqStart = findMovableSequenceStart(from, emptyFreeCells, emptyCascades);
for (int idx = seqStart; idx < cascade[from].size(); idx++) {
Card card = cascade[from].get(idx);
for (int to = 0; to < 8; to++) {
if (from == to) continue;
Card top = cascade[to].isEmpty() ? null :
cascade[to].get(cascade[to].size() - 1);
if (card.canPlaceOnCascade(top)) {
moves.add(new Move(Move.Type.CASCADE_TO_CASCADE, from, to,
cascade[from].size() - idx));
}
}
}
}
// 5. 空闲单元 -> 牌叠
for (int i = 0; i < 4; i++) {
if (freeCell[i] == null) continue;
for (int j = 0; j < 8; j++) {
Card top = cascade[j].isEmpty() ? null :
cascade[j].get(cascade[j].size() - 1);
if (freeCell[i].canPlaceOnCascade(top)) {
moves.add(new Move(Move.Type.FREECELL_TO_CASCADE, i, j, 1));
}
}
}
return moves;
}
/**
* 计算可移动序列的起始位置（考虑超级移动）
*/
private int findMovableSequenceStart(int colIdx, int emptyFreeCells, int emptyCascades) {
List<Card> col = cascade[colIdx];
if (col.size() <= 1) return Math.max(0, col.size() - 1);
// 从底部向上找到最长的可移动有序序列
int maxMovable = 1;
// 超级移动公式：可移动牌数 = (1 + 空闲单元数) * 2^空牌叠数
int superMoveCount = (1 + emptyFreeCells) * (1 << emptyCascades);
for (int i = col.size() - 2; i >= 0; i--) {
Card current = col.get(i);
Card below = col.get(i + 1);
if (current.canPlaceOnCascade(below)) {
maxMovable++;
if (maxMovable >= superMoveCount) break;
} else {
break;
}
}
return Math.max(0, col.size() - maxMovable);
}
/**
* 应用移动，返回新状态
*/
GameState applyMove(Move move) {
GameState next = new GameState(this);
next.parent = this;
next.moveFromParent = move;
next.gScore = this.gScore + 1;
switch (move.type) {
case CASCADE_TO_CASCADE:
List<Card> fromCol = next.cascade[move.from];
List<Card> toCol = next.cascade[move.to];
int startIdx = fromCol.size() - move.count;
List<Card> moving = new ArrayList<>(fromCol.subList(startIdx, fromCol.size()));
fromCol.subList(startIdx, fromCol.size()).clear();
toCol.addAll(moving);
break;
case CASCADE_TO_FREECELL:
next.freeCell[move.to] = next.cascade[move.from].remove(
next.cascade[move.from].size() - 1);
break;
case CASCADE_TO_FOUNDATION:
Card c1 = next.cascade[move.from].remove(
next.cascade[move.from].size() - 1);
next.foundation[move.to] = c1.rank;
break;
case FREECELL_TO_CASCADE:
next.cascade[move.to].add(next.freeCell[move.from]);
next.freeCell[move.from] = null;
break;
case FREECELL_TO_FOUNDATION:
Card c2 = next.freeCell[move.from];
next.foundation[move.to] = c2.rank;
next.freeCell[move.from] = null;
break;
}
return next;
}
/**
* 检查是否达到胜利状态
*/
boolean isGoal() {
for (int val : foundation) {
if (val != 13) return false;
}
return true;
}
/**
* 生成状态的唯一哈希（用于判重）
*/
String getHash() {
StringBuilder sb = new StringBuilder();
for (List<Card> col : cascade) {
for (Card c : col) sb.append(c.toString());
sb.append("|");
}
sb.append("#");
for (Card c : freeCell) sb.append(c == null ? "-" : c.toString());
sb.append("#");
for (int val : foundation) sb.append(val);
return sb.toString();
}
@Override
public int compareTo(GameState other) {
int f1 = this.gScore + this.hScore;
int f2 = other.gScore + other.hScore;
return Integer.compare(f1, f2);
}
}
启发式函数
package com.freecell;
/**
* 启发式函数评估器
*/
public class Heuristic {
/**
* 综合启发式函数
* 值越小表示状态越接近目标
*/
public static int evaluate(GameState state) {
int score = 0;
// 1. 未上foundation的牌数（主要指标）
int onFoundation = 0;
for (int val : state.foundation) onFoundation += val;
score += (52 - onFoundation) * 10;
// 2. 空闲单元占用惩罚（空闲单元越少越差）
int usedFreeCells = 0;
for (Card c : state.freeCell) if (c != null) usedFreeCells++;
score += usedFreeCells * 5;
// 3. 空牌叠奖励（空牌叠是宝贵的资源）
int emptyCascades = 0;
for (var col : state.cascade) if (col.isEmpty()) emptyCascades++;
score -= emptyCascades * 8;
// 4. 牌叠有序度：每个"好序列"减少惩罚
for (var col : state.cascade) {
if (col.size() <= 1) continue;
int orderedCards = 1;
for (int i = col.size() - 2; i >= 0; i--) {
if (col.get(i).canPlaceOnCascade(col.get(i + 1))) {
orderedCards++;
} else {
break;
}
}
// 无序的牌每张+3分惩罚
score += (col.size() - orderedCards) * 3;
}
// 5. buried Aces惩罚：A被压在下面会导致foundation无法推进
for (var col : state.cascade) {
for (int i = 0; i < col.size(); i++) {
if (col.get(i).rank == 1) { // 找到A
score += (col.size() - i - 1) * 2; // 上面每张牌+2
}
}
}
return Math.max(0, score);
}
}
A*求解器
package com.freecell;
import java.util.*;
/**
* A*搜索求解器
*/
public class AStarSolver {
private int nodesExplored = 0;
private int maxQueueSize = 0;
/**
* 使用A*搜索求解空当接龙
* @param initialState 初始状态
* @return 移动序列，如果无解返回null
*/
public List<Move> solve(GameState initialState) {
initialState.gScore = 0;
initialState.hScore = Heuristic.evaluate(initialState);
// 优先队列：按f(n) = g(n) + h(n)排序
PriorityQueue<GameState> openSet = new PriorityQueue<>();
openSet.add(initialState);
// 已访问状态集合
Set<String> closedSet = new HashSet<>();
while (!openSet.isEmpty()) {
maxQueueSize = Math.max(maxQueueSize, openSet.size());
GameState current = openSet.poll();
nodesExplored++;
if (current.isGoal()) {
return reconstructPath(current);
}
String hash = current.getHash();
if (closedSet.contains(hash)) continue;
closedSet.add(hash);
// 生成所有合法移动
List<Move> moves = current.generateMoves();
for (Move move : moves) {
GameState next = current.applyMove(move);
next.hScore = Heuristic.evaluate(next);
String nextHash = next.getHash();
if (!closedSet.contains(nextHash)) {
openSet.add(next);
}
}
}
return null; // 无解
}
/**
* 回溯重构解路径
*/
private List<Move> reconstructPath(GameState goal) {
LinkedList<Move> path = new LinkedList<>();
GameState current = goal;
while (current.moveFromParent != null) {
path.addFirst(current.moveFromParent);
current = current.parent;
}
return path;
}
public int getNodesExplored() { return nodesExplored; }
public int getMaxQueueSize() { return maxQueueSize; }
}
主程序与演示
package com.freecell;
import java.util.*;
/**
* 空当接龙求解器演示
*/
public class Main {
public static void main(String[] args) {
// 初始化一副牌并洗牌
List<Card> deck = new ArrayList<>();
for (Card.Suit suit : Card.Suit.values()) {
for (int rank = 1; rank <= 13; rank++) {
deck.add(new Card(suit, rank));
}
}
Collections.shuffle(deck, new Random(42)); // 固定种子便于复现
// 发牌到8列（前4列7张，后4列6张）
GameState initial = new GameState();
int cardIdx = 0;
for (int col = 0; col < 8; col++) {
int count = (col < 4) ? 7 : 6;
for (int i = 0; i < count; i++) {
initial.cascade[col].add(deck.get(cardIdx++));
}
}
System.out.println("=== 空当接龙 A*求解器 ===\n");
System.out.println("初始牌局：");
printState(initial);
AStarSolver solver = new AStarSolver();
long startTime = System.currentTimeMillis();
List<Move> solution = solver.solve(initial);
long endTime = System.currentTimeMillis();
if (solution != null) {
System.out.println("\n求解成功！");
System.out.println("移动步数：" + solution.size());
System.out.println("搜索节点数：" + solver.getNodesExplored());
System.out.println("最大队列长度：" + solver.getMaxQueueSize());
System.out.println("耗时：" + (endTime - startTime) + "ms");
System.out.println("\n前10步移动：");
for (int i = 0; i < Math.min(10, solution.size()); i++) {
System.out.println(" " + (i + 1) + ". " + solution.get(i));
}
if (solution.size() > 10) {
System.out.println(" ... 共" + solution.size() + "步");
}
} else {
System.out.println("\n该牌局无解！");
}
}
private static void printState(GameState state) {
for (int i = 0; i < 8; i++) {
System.out.print("列" + (i + 1) + ": ");
for (Card c : state.cascade[i]) {
System.out.print(c + " ");
}
System.out.println();
}
System.out.print("空闲单元: ");
for (Card c : state.freeCell) {
System.out.print((c == null ? "[空]" : c) + " ");
}
System.out.println();
System.out.print("目标堆: ");
String[] suits = {"♠", "♥", "♣", "♦"};
for (int i = 0; i < 4; i++) {
System.out.print(suits[i] + "=" + state.foundation[i] + " ");
}
System.out.println();
}
}
算法优化策略
1. 移动排序（Move Ordering）
优先尝试”好移动”可大幅减少搜索空间：
– 优先移至foundation（推进游戏进度）
– 优先释放被压的A和低牌
– 避免无意义的来回移动
2. 状态压缩哈希
使用Zobrist哈希或完美哈希减少内存占用和比较开销。
3. 迭代加深A (IDA)
对于内存受限场景，可用IDA替代A，以时间换空间。
4. 模式数据库（Pattern Database）
预计算子问题（如单花色的最优解法）作为更精确的启发式下界。
复杂度分析
状态空间规模
空当接龙的状态空间极为庞大。粗略估计上界为 $52!$（所有牌的排列），但由于规则约束，实际可达状态远小于此。据统计，约 $1.75 \times 10^{64}$ 个合法牌局。
搜索复杂度
- 时间复杂度：$O(b^d)$，其中 $b$ 为平均分支因子（约20-50），$d$ 为解深度（通常50-100步）
- 空间复杂度：$O(b^d)$ 存储已访问状态
良好的启发式函数可将实际探索节点数控制在数万至数十万级别，使大多数牌局在秒级求解。
总结
空当接龙的求解展示了A搜索在复杂状态空间问题中的强大能力。关键在于：
1. 精确的状态表示：完整而高效地编码游戏局面
2. 完备的合法移动生成：不遗漏任何可能性
3. 高质量的启发式函数：准确估计剩余代价，引导搜索方向
4. 有效的重复状态剪枝*：避免环路和冗余探索
这些思想同样适用于滑动拼图、魔方求解、路径规划等经典AI问题。
