纸牌接龙（Klondike Solitaire）是Windows系统自带的最经典纸牌游戏之一，陪伴了无数人的童年。它看似简单，实则蕴含丰富的算法设计空间：从牌局状态的紧凑表示，到合法移动的枚举，再到基于DFS的回溯搜索与启发式策略的自动求解，每一步都值得深入探讨。本文将用Java完整实现一个带自动求解功能的纸牌接龙引擎，核心聚焦算法而非界面绘制。
一、游戏规则与算法建模
标准纸牌接龙使用一副去掉大小王的52张扑克牌。牌局由以下区域构成：
- ** tableau（七列牌阵）**：共7列，第i列有i张牌，仅最底牌正面朝上。
- ** stock（牌库）**：剩余24张牌叠放，每次可翻1张或3张到waste（废牌堆）。
- ** foundation（基础堆）**：4个空位，按同花色的A→K顺序逐张放置。
玩家的目标是将所有52张牌按花色分别移入4个foundation。每次只能移动正面朝上的牌，且tableau中的牌必须按降序、红黑交替的规则叠放。
从算法角度，这是一个典型的有限状态空间搜索问题。每个牌局状态可以用各区域牌的排列完全描述，玩家的每一步操作则是状态转移。由于状态空间有限（约10^67，但可达状态远少），我们可以用深度优先搜索（DFS）结合回溯来探索解空间，同时引入启发式函数剪枝，实现高效的自动求解。
二、状态表示设计
为了高效地存储和比较牌局状态（用于判重），我们采用紧凑的字符串编码。每张牌用两个字符表示：花色（S/H/D/C）+ 点数（A/2-9/T/J/Q/K）。
/**
* 纸牌类：表示单张扑克牌
*/
public class Card {
public enum Suit { SPADE('S'), HEART('H'), DIAMOND('D'), CLUB('C');
public final char code;
Suit(char c) { this.code = c; }
}
public final Suit suit;
public final int rank; // 1=A, 11=J, 12=Q, 13=K
public boolean faceUp;
public Card(Suit suit, int rank) {
this.suit = suit;
this.rank = rank;
this.faceUp = false;
}
public boolean isRed() {
return suit == Suit.HEART || suit == Suit.DIAMOND;
}
/** 能否叠放在另一张牌上（tableau规则：降序且颜色交替） */
public boolean canPlaceOn(Card other) {
if (other == null) return this.rank == 13; // K可放空列
return this.rank == other.rank - 1 && this.isRed() != other.isRed();
}
/** 能否放入foundation（同花色升序） */
public boolean canPlaceOnFoundation(Card top) {
if (top == null) return this.rank == 1; // A可放空foundation
return this.suit == top.suit && this.rank == top.rank + 1;
}
public String toCode() {
char r = " A23456789TJQK".charAt(rank);
return "" + suit.code + r;
}
@Override
public String toString() {
return toCode() + (faceUp ? "" : "?");
}
}
牌局状态编码的核心思想是按区域顺序拼接所有牌的编码，中间用分隔符区分不同区域：
/**
* 牌局状态：包含tableau、stock、waste、foundation的完整状态
* 并提供紧凑的字符串编码用于状态判重
*/
public class GameState {
// 7列tableau，每列是一个栈（底→顶）
public final List<Deque<Card>> tableau;
// stock牌库（顶牌在末尾）
public final List<Card> stock;
// waste废牌堆（顶牌在末尾）
public final List<Card> waste;
// 4个foundation，按S/H/D/C顺序
public final Card[] foundation;
public GameState() {
this.tableau = new ArrayList<>();
for (int i = 0; i < 7; i++) tableau.add(new ArrayDeque<>());
this.stock = new ArrayList<>();
this.waste = new ArrayList<>();
this.foundation = new Card[4];
}
/**
* 生成唯一状态编码，用于HashSet判重。
* 格式：T0|T1|...|T6#W|F0|F1|F2|F3#S
* 其中T表示tableau各列（从底到顶），W表示waste顶牌，F表示foundation顶牌，S表示stock剩余数
*/
public String encode() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 7; i++) {
if (i > 0) sb.append('|');
for (Card c : tableau.get(i)) {
sb.append(c.faceUp ? c.toCode() : "XX");
}
}
sb.append('#');
if (!waste.isEmpty()) sb.append(waste.get(waste.size() - 1).toCode());
sb.append('#');
for (int i = 0; i < 4; i++) {
if (foundation[i] != null) sb.append(foundation[i].toCode());
else sb.append("--");
}
sb.append('#').append(stock.size());
return sb.toString();
}
}
三、合法移动枚举
自动求解的第一步是枚举当前状态下的所有合法操作。操作分为四类：
- tableau ↔ tableau：将一列顶部的一段连续正面牌（或单张）移到另一列。
- tableau → foundation：将tableau顶牌移入foundation。
- waste → tableau：将waste顶牌移到tableau。
- waste → foundation：将waste顶牌移入foundation。
- 翻stock：从stock翻牌到waste（或循环重置）。
- foundation → tableau（可选高级操作，部分规则允许）。
/**
* 移动操作描述
*/
public class Move {
public enum Type {
TABLEAU_TO_TABLEAU, // 列间移动
TABLEAU_TO_FOUNDATION, // 移入基础堆
WASTE_TO_TABLEAU, // 废牌移到列
WASTE_TO_FOUNDATION, // 废牌移入基础堆
FLIP_STOCK, // 翻牌库
FOUNDATION_TO_TABLEAU // 基础堆回列（部分变体规则）
}
public final Type type;
public final int from; // 来源列/堆索引
public final int to; // 目标列/堆索引
public final int count; // 移动的牌数量
public 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, cnt=%d]", type, from, to, count);
}
}
/**
* 合法移动生成器
*/
public class MoveGenerator {
public List<Move> generateMoves(GameState state) {
List<Move> moves = new ArrayList<>();
// 1. tableau顶牌 → foundation
for (int col = 0; col < 7; col++) {
Card top = peekTop(state.tableau.get(col));
if (top != null && top.faceUp) {
int fIdx = top.suit.ordinal();
if (top.canPlaceOnFoundation(state.foundation[fIdx])) {
moves.add(new Move(Move.Type.TABLEAU_TO_FOUNDATION, col, fIdx, 1));
}
}
}
// 2. waste顶牌 → foundation
if (!state.waste.isEmpty()) {
Card top = state.waste.get(state.waste.size() - 1);
int fIdx = top.suit.ordinal();
if (top.canPlaceOnFoundation(state.foundation[fIdx])) {
moves.add(new Move(Move.Type.WASTE_TO_FOUNDATION, -1, fIdx, 1));
}
}
// 3. tableau → tableau（移动顶部连续序列）
for (int from = 0; from < 7; from++) {
Deque<Card> src = state.tableau.get(from);
List<Card> faceUpSeq = getFaceUpSequence(src);
if (faceUpSeq.isEmpty()) continue;
for (int to = 0; to < 7; to++) {
if (from == to) continue;
Card destTop = peekTop(state.tableau.get(to));
// 尝试移动整个连续序列或子序列
for (int cnt = 1; cnt <= faceUpSeq.size(); cnt++) {
Card moving = faceUpSeq.get(faceUpSeq.size() - cnt);
if (moving.canPlaceOn(destTop)) {
moves.add(new Move(Move.Type.TABLEAU_TO_TABLEAU, from, to, cnt));
}
}
}
}
// 4. waste → tableau
if (!state.waste.isEmpty()) {
Card top = state.waste.get(state.waste.size() - 1);
for (int to = 0; to < 7; to++) {
Card destTop = peekTop(state.tableau.get(to));
if (top.canPlaceOn(destTop)) {
moves.add(new Move(Move.Type.WASTE_TO_TABLEAU, -1, to, 1));
}
}
}
// 5. 翻stock（每次翻1张）
if (!state.stock.isEmpty()) {
moves.add(new Move(Move.Type.FLIP_STOCK, -1, -1, 1));
} else if (!state.waste.isEmpty()) {
// stock为空且waste有牌，可以重置（循环）
moves.add(new Move(Move.Type.FLIP_STOCK, -1, -1, -1));
}
return moves;
}
private Card peekTop(Deque<Card> stack) {
return stack.isEmpty() ? null : stack.peekLast();
}
/** 获取一列中从某张牌开始到底部所有正面朝上的连续序列 */
private List<Card> getFaceUpSequence(Deque<Card> col) {
List<Card> list = new ArrayList<>(col);
List<Card> seq = new ArrayList<>();
for (int i = list.size() - 1; i >= 0; i--) {
Card c = list.get(i);
if (!c.faceUp) break;
seq.add(0, c); // 保持从顶到底顺序
}
return seq;
}
}
四、DFS回溯搜索与状态判重
纸牌接龙的求解可以建模为路径搜索问题：从初始牌局出发，通过合法移动不断转移状态，直到所有牌都进入foundation（胜利）或状态空间穷尽（无解/未找到）。
由于牌局可能循环（例如反复移动同一张牌），必须使用状态判重（visited集合）。DFS配合剪枝是合适的选择：搜索深度有限（最多约200步），状态编码紧凑，判重开销可控。
/**
* DFS求解器：带状态判重和深度限制的深度优先搜索
*/
public class SolitaireSolver {
private final MoveGenerator generator = new MoveGenerator();
private final Set<String> visited = new HashSet<>();
private List<Move> solution;
private static final int MAX_DEPTH = 250; // 最大搜索深度防止无限递归
/**
* 尝试求解给定牌局，返回移动序列；若未找到则返回null。
*/
public List<Move> solve(GameState initial) {
visited.clear();
solution = null;
List<Move> path = new ArrayList<>();
dfs(initial, path, 0);
return solution;
}
private boolean dfs(GameState state, List<Move> path, int depth) {
if (depth > MAX_DEPTH) return false;
// 胜利检测：52张牌全部进入foundation
if (isWin(state)) {
solution = new ArrayList<>(path);
return true;
}
String enc = state.encode();
if (visited.contains(enc)) return false;
visited.add(enc);
// 生成并按启发式分数排序所有合法移动（优先尝试更优的移动）
List<Move> moves = generator.generateMoves(state);
moves.sort((a, b) -> heuristicScore(b, state) - heuristicScore(a, state));
for (Move move : moves) {
GameState next = applyMove(state, move);
if (next == null) continue;
path.add(move);
if (dfs(next, path, depth + 1)) return true;
path.remove(path.size() - 1);
}
return false;
}
private boolean isWin(GameState state) {
for (Card c : state.foundation) {
if (c == null || c.rank != 13) return false;
}
return true;
}
/** 启发式评分：分数越高越优先尝试 */
private int heuristicScore(Move move, GameState state) {
return switch (move.type) {
case TABLEAU_TO_FOUNDATION -> 100; // 优先把牌移入foundation
case WASTE_TO_FOUNDATION -> 90;
case TABLEAU_TO_TABLEAU -> {
// 优先翻牌操作（移动后暴露新牌）
Deque<Card> src = state.tableau.get(move.from);
boolean exposesNew = src.size() > move.count;
yield exposesNew ? 50 : 10;
}
case WASTE_TO_TABLEAU -> 20;
case FLIP_STOCK -> 0; // 最后尝试翻牌
default -> 5;
};
}
}
五、状态转移实现
状态转移是求解器的核心，需要准确执行移动并生成新状态：
/**
* 执行移动，返回新状态（不修改原状态）
*/
public GameState applyMove(GameState state, Move move) {
GameState next = cloneState(state);
switch (move.type) {
case TABLEAU_TO_FOUNDATION -> {
Deque<Card> col = next.tableau.get(move.from);
Card card = col.pollLast();
next.foundation[move.to] = card;
flipIfNeeded(next, move.from);
}
case WASTE_TO_FOUNDATION -> {
Card card = next.waste.remove(next.waste.size() - 1);
next.foundation[move.to] = card;
}
case TABLEAU_TO_TABLEAU -> {
Deque<Card> src = next.tableau.get(move.from);
Deque<Card> dst = next.tableau.get(move.to);
List<Card> temp = new ArrayList<>();
for (int i = 0; i < move.count; i++) temp.add(0, src.pollLast());
for (Card c : temp) dst.addLast(c);
flipIfNeeded(next, move.from);
}
case WASTE_TO_TABLEAU -> {
Card card = next.waste.remove(next.waste.size() - 1);
next.tableau.get(move.to).addLast(card);
}
case FLIP_STOCK -> {
if (move.count == -1) {
// 重置：waste全部移回stock
for (int i = next.waste.size() - 1; i >= 0; i--) {
Card c = next.waste.get(i);
c.faceUp = false;
next.stock.add(0, c);
}
next.waste.clear();
} else {
// 翻1张
Card c = next.stock.remove(0);
c.faceUp = true;
next.waste.add(c);
}
}
}
return next;
}
/** 如果一列顶牌被移走后露出背面牌，将其翻转 */
private void flipIfNeeded(GameState state, int colIdx) {
Deque<Card> col = state.tableau.get(colIdx);
if (!col.isEmpty()) {
Card top = col.peekLast();
if (!top.faceUp) top.faceUp = true;
}
}
/** 深拷贝牌局状态 */
private GameState cloneState(GameState s) {
GameState c = new GameState();
for (int i = 0; i < 7; i++) {
for (Card card : s.tableau.get(i)) {
Card copy = new Card(card.suit, card.rank);
copy.faceUp = card.faceUp;
c.tableau.get(i).addLast(copy);
}
}
for (Card card : s.stock) {
Card copy = new Card(card.suit, card.rank);
copy.faceUp = card.faceUp;
c.stock.add(copy);
}
for (Card card : s.waste) {
Card copy = new Card(card.suit, card.rank);
copy.faceUp = card.faceUp;
c.waste.add(copy);
}
for (int i = 0; i < 4; i++) {
if (s.foundation[i] != null) {
c.foundation[i] = new Card(s.foundation[i].suit, s.foundation[i].rank);
c.foundation[i].faceUp = true;
}
}
return c;
}
六、发牌与随机牌局生成
/**
* 牌局生成器：随机洗牌并按规则发牌
*/
public class GameFactory {
public GameState createRandomGame(long seed) {
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(seed));
GameState state = new GameState();
int idx = 0;
for (int col = 0; col < 7; col++) {
for (int row = 0; row <= col; row++) {
Card c = deck.get(idx++);
c.faceUp = (row == col); // 仅最底牌正面朝上
state.tableau.get(col).addLast(c);
}
}
while (idx < 52) {
Card c = deck.get(idx++);
c.faceUp = false;
state.stock.add(c);
}
return state;
}
}
七、主程序与求解演示
public class SolitaireApp {
public static void main(String[] args) {
// 使用固定种子生成可复现的牌局
long seed = 42L;
GameState game = new GameFactory().createRandomGame(seed);
System.out.println("=== 初始牌局 ===");
printState(game);
SolitaireSolver solver = new SolitaireSolver();
List<Move> solution = solver.solve(game);
if (solution != null) {
System.out.println("\n=== 找到解法，共 " + solution.size() + " 步 ===");
GameState current = new GameFactory().createRandomGame(seed);
for (int i = 0; i < solution.size(); i++) {
Move m = solution.get(i);
System.out.println("Step " + (i + 1) + ": " + m);
current = applyMove(current, m);
}
System.out.println("\n=== 胜利 ===");
} else {
System.out.println("\n未找到解法（当前深度限制或确实无解）。");
}
}
// applyMove和printState实现省略，与上文一致
}
八、算法复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 状态空间 | O((52)! / 约束) | 实际可达状态远小于理论值 |
| 单次移动枚举 | O(1) ~ O(n) | 最多约50种合法移动 |
| 状态编码 | O(52) | 线性扫描所有牌 |
| DFS最坏时间 | 指数级 | 依赖剪枝效果，实际通常在毫秒到秒级 |
| 判重空间 | O(访问状态数) | HashSet存储，每个状态约60字节 |
九、进阶优化方向
- 迭代加深（IDDFS）：逐步放宽深度限制，保证在有限时间内找到最优解（步数最少）。
- 双向BFS：从胜利状态反向搜索，但逆向移动生成较复杂。
- A*搜索：设计更精细的启发函数（如foundation已放置牌数、暴露正面牌数、列空位数），用优先队列引导搜索。
- 模式数据库：预计算小型子问题（如单花色的最优移动）作为查找表加速评估。
十、总结
纸牌接龙是一个绝佳的算法学习载体。本文从状态表示、合法移动生成、DFS回溯搜索到启发式剪枝，完整构建了一个自动求解引擎。核心收获包括：
- 紧凑编码：状态字符串化是判重和哈希的基础。
- 回溯策略：DFS配合visited集合有效避免循环状态。
- 启发式排序：优先尝试移牌入foundation和翻牌操作，大幅提升搜索效率。
- 不变量保持：每次状态转移后正确翻转背面牌，维护牌局规则不变性。
读者可以在此基础上扩展图形界面、尝试更复杂的启发函数，或将迭代加深和A*算法引入，进一步提升求解能力和效率。
