每日算法 — 使用java实现纸牌接龙：DFS回溯搜索与状态空间启发式策略

纸牌接龙（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();
    }
}

三、合法移动枚举

自动求解的第一步是枚举当前状态下的所有合法操作。操作分为四类：

1. tableau ↔ tableau：将一列顶部的一段连续正面牌（或单张）移到另一列。
2. tableau → foundation：将tableau顶牌移入foundation。
3. waste → tableau：将waste顶牌移到tableau。
4. waste → foundation：将waste顶牌移入foundation。
5. 翻stock：从stock翻牌到waste（或循环重置）。
6. 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实现省略，与上文一致
}

八、算法复杂度分析

九、进阶优化方向

1. 迭代加深（IDDFS）：逐步放宽深度限制，保证在有限时间内找到最优解（步数最少）。
2. 双向BFS：从胜利状态反向搜索，但逆向移动生成较复杂。
3. A*搜索：设计更精细的启发函数（如foundation已放置牌数、暴露正面牌数、列空位数），用优先队列引导搜索。
4. 模式数据库：预计算小型子问题（如单花色的最优移动）作为查找表加速评估。

十、总结

纸牌接龙是一个绝佳的算法学习载体。本文从状态表示、合法移动生成、DFS回溯搜索到启发式剪枝，完整构建了一个自动求解引擎。核心收获包括：

• 紧凑编码：状态字符串化是判重和哈希的基础。
• 回溯策略：DFS配合visited集合有效避免循环状态。
• 启发式排序：优先尝试移牌入foundation和翻牌操作，大幅提升搜索效率。
• 不变量保持：每次状态转移后正确翻转背面牌，维护牌局规则不变性。

读者可以在此基础上扩展图形界面、尝试更复杂的启发函数，或将迭代加深和A*算法引入，进一步提升求解能力和效率。