引言
羊了个羊是一款现象级的三消类益智游戏，核心玩法是将三层堆叠的图案牌逐张移入槽位，当槽位中累积三张相同图案时即可消除。游戏看似简单，实则蕴含深厚的组合数学与搜索算法思想。本文将用Java实现该游戏的核心引擎，重点讲解基于栈结构的消除匹配与DFS回溯求解算法，分析如何判定一局游戏是否可解，以及如何用搜索算法寻找最优消除序列。
问题建模
游戏规则抽象
- 牌堆结构：N张牌分为M种图案，每种图案有3张，堆叠成多层结构
- 可见性：只有不被其他牌覆盖的牌才可点击
- 槽位机制：底部有7个槽位，点击的牌进入槽位
- 消除规则：槽位中某图案累积达到3张时自动消除
- 胜负判定：槽位满7张且无法消除时失败；所有牌消除时胜利
数据结构定义
- 每张牌具有：唯一ID、图案类型、所在层数、覆盖关系
- 覆盖关系：如果牌A的矩形区域与牌B重叠且A在B上层，则A覆盖B
- 可见牌：不被任何上层牌覆盖的牌
核心算法一：可见牌检测与覆盖关系
通过二维网格或矩形相交检测来确定牌的覆盖关系。
核心算法二：DFS回溯求解
判定当前局面是否有解，核心思路是：
1. 枚举所有当前可见牌的选择
2. 模拟选择后的状态变化（槽位变化、新牌露出）
3. 递归搜索，直到找到解或穷尽所有可能
4. 使用记忆化或剪枝避免重复搜索
完整Java实现
package sheep.game;
import java.util.*;
/**
* 羊了个羊 - 栈结构匹配与DFS回溯求解引擎
*
* 核心功能：
* 1. 多层牌堆的覆盖关系建模与可见牌检测
* 2. 槽位栈结构的匹配消除逻辑
* 3. DFS回溯搜索判定局面可解性
* 4. 寻找最优消除序列
*/
public class SheepGameSolver {
/**
* 牌的图案类型
*/
public enum Pattern {
CARROT, CORN, GLOVE, BRUSH, SCISSORS,
BELL, FIRE, GRASS, MILK, WOOL
}
/**
* 单张牌
*/
public static class Card {
public final int id;
public final Pattern pattern;
public final int layer; // 所在层数，越大越靠上
public final int x, y; // 坐标位置
public final int width, height; // 尺寸
public Card(int id, Pattern pattern, int layer, int x, int y, int w, int h) {
this.id = id;
this.pattern = pattern;
this.layer = layer;
this.x = x;
this.y = y;
this.width = w;
this.height = h;
}
/**
* 判断两个牌是否发生矩形重叠
*/
public boolean overlaps(Card other) {
return this.x < other.x + other.width
&& this.x + this.width > other.x
&& this.y < other.y + other.height
&& this.y + this.height > other.y;
}
}
/**
* 游戏状态
*/
public static class GameState {
public final List<Card> remainingCards; // 剩余未消除的牌
public final List<Card> slot; // 当前槽位中的牌（最多7张）
public final List<Move> moves; // 已执行的移动序列
public GameState(List<Card> remaining, List<Card> slot, List<Move> moves) {
this.remainingCards = new ArrayList<>(remaining);
this.slot = new ArrayList<>(slot);
this.moves = new ArrayList<>(moves);
}
public GameState copy() {
return new GameState(remainingCards, slot, moves);
}
}
/**
* 一次移动操作
*/
public static class Move {
public final Card card;
public final int slotIndex;
public Move(Card card, int slotIndex) {
this.card = card;
this.slotIndex = slotIndex;
}
}
/**
* 构建覆盖关系图
*
* @param cards 所有牌的列表
* @return 覆盖映射：对于每张牌，哪些牌覆盖在它上面
*/
public static Map<Card, Set<Card>> buildCoverGraph(List<Card> cards) {
Map<Card, Set<Card>> coverMap = new HashMap<>();
for (Card card : cards) {
coverMap.put(card, new HashSet<>());
}
// 对于每对牌，如果发生重叠且层数更高，则上层覆盖下层
for (int i = 0; i < cards.size(); i++) {
for (int j = i + 1; j < cards.size(); j++) {
Card a = cards.get(i);
Card b = cards.get(j);
if (a.overlaps(b)) {
if (a.layer > b.layer) {
coverMap.get(b).add(a); // a覆盖b
} else if (b.layer > a.layer) {
coverMap.get(a).add(b); // b覆盖a
}
}
}
}
return coverMap;
}
/**
* 获取当前可见的牌（不被任何剩余牌覆盖）
*/
public static Set<Card> getVisibleCards(List<Card> remaining,
Map<Card, Set<Card>> coverGraph) {
Set<Card> visible = new HashSet<>();
for (Card card : remaining) {
boolean covered = false;
for (Card cover : coverGraph.get(card)) {
if (remaining.contains(cover)) {
covered = true;
break;
}
}
if (!covered) {
visible.add(card);
}
}
return visible;
}
/**
* 将牌放入槽位，处理消除逻辑
*
* @param slot 当前槽位
* @param card 要放入的牌
* @return 消除后的槽位状态，若槽位溢出（超过7张且无法消除）返回null
*/
public static List<Card> placeIntoSlot(List<Card> slot, Card card) {
List<Card> newSlot = new ArrayList<>(slot);
newSlot.add(card);
// 检查是否有3张相同的图案可以消除
Map<Pattern, List<Card>> patternGroups = new HashMap<>();
for (Card c : newSlot) {
patternGroups.computeIfAbsent(c.pattern, k -> new ArrayList<>()).add(c);
}
// 消除所有达到3张的图案
List<Card> afterElimination = new ArrayList<>();
for (Card c : newSlot) {
if (patternGroups.get(c.pattern).size() < 3) {
afterElimination.add(c);
}
}
// 槽位最多容纳7张未消除的牌
if (afterElimination.size() > 7) {
return null; // 槽位溢出，游戏失败
}
return afterElimination;
}
/**
* 计算状态哈希，用于记忆化
*/
private static String stateHash(List<Card> remaining, List<Card> slot) {
StringBuilder sb = new StringBuilder();
List<Integer> remIds = new ArrayList<>();
for (Card c : remaining) remIds.add(c.id);
Collections.sort(remIds);
for (int id : remIds) sb.append(id).append(',');
sb.append('|');
for (Card c : slot) sb.append(c.pattern.ordinal());
return sb.toString();
}
/**
* DFS回溯搜索求解
*
* @param state 当前游戏状态
* @param coverGraph 覆盖关系图
* @param memo 记忆化集合，记录已访问的状态
* @return 若可解返回true，并将解路径存入state.moves
*/
public static boolean dfsSolve(GameState state,
Map<Card, Set<Card>> coverGraph,
Set<String> memo) {
// 所有牌已消除，胜利
if (state.remainingCards.isEmpty()) {
return true;
}
String hash = stateHash(state.remainingCards, state.slot);
if (memo.contains(hash)) {
return false; // 该状态已搜索过且不可解
}
memo.add(hash);
// 获取当前可见牌
Set<Card> visible = getVisibleCards(state.remainingCards, coverGraph);
// 如果没有可见牌但还有剩余牌，死锁
if (visible.isEmpty() && !state.remainingCards.isEmpty()) {
return false;
}
// 按启发式策略排序可见牌：优先消除槽位中已有的图案
List<Card> sortedVisible = new ArrayList<>(visible);
Map<Pattern, Integer> slotPatternCount = new HashMap<>();
for (Card c : state.slot) {
slotPatternCount.merge(c.pattern, 1, Integer::sum);
}
sortedVisible.sort((a, b) -> {
int ca = slotPatternCount.getOrDefault(a.pattern, 0);
int cb = slotPatternCount.getOrDefault(b.pattern, 0);
return cb - ca; // 槽位中已有更多的优先
});
for (Card card : sortedVisible) {
// 模拟将牌放入槽位
List<Card> newSlot = placeIntoSlot(state.slot, card);
if (newSlot == null) continue; // 槽位溢出，跳过
// 构建新状态
List<Card> newRemaining = new ArrayList<>(state.remainingCards);
newRemaining.remove(card);
List<Move> newMoves = new ArrayList<>(state.moves);
newMoves.add(new Move(card, state.slot.size()));
GameState nextState = new GameState(newRemaining, newSlot, newMoves);
if (dfsSolve(nextState, coverGraph, memo)) {
// 将子状态的解复制回当前状态
state.moves.clear();
state.moves.addAll(nextState.moves);
return true;
}
}
return false;
}
/**
* 生成一局可解的游戏
*/
public static List<Card> generateSolvableGame(int patternCount, int layers) {
List<Card> cards = new ArrayList<>();
Random rand = new Random();
int id = 0;
Pattern[] patterns = Pattern.values();
// 每种图案3张
for (int p = 0; p < patternCount && p < patterns.length; p++) {
for (int copy = 0; copy < 3; copy++) {
int layer = rand.nextInt(layers);
int x = rand.nextInt(400);
int y = rand.nextInt(400);
cards.add(new Card(id++, patterns[p], layer, x, y, 60, 60));
}
}
return cards;
}
/**
* 打印当前游戏状态
*/
public static void printState(GameState state, Map<Card, Set<Card>> coverGraph) {
Set<Card> visible = getVisibleCards(state.remainingCards, coverGraph);
System.out.printf("剩余牌: %d | 可见牌: %d | 槽位: %d%n",
state.remainingCards.size(), visible.size(), state.slot.size());
System.out.print("槽位: ");
for (Card c : state.slot) {
System.out.print(c.pattern + " ");
}
System.out.println();
System.out.print("可见: ");
for (Card c : visible) {
System.out.printf("[%d]%s ", c.id, c.pattern);
}
System.out.println("\n");
}
// ==================== 测试入口 ====================
public static void main(String[] args) {
System.out.println("===== 羊了个羊 DFS回溯求解 =====\n");
// 生成一局小型游戏：5种图案 × 3张 = 15张牌，3层
List<Card> cards = generateSolvableGame(5, 3);
System.out.printf("生成牌堆: %d 张牌，%d 种图案%n\n", cards.size(), 5);
// 构建覆盖关系
Map<Card, Set<Card>> coverGraph = buildCoverGraph(cards);
// 初始状态
GameState initial = new GameState(cards, new ArrayList<>(), new ArrayList<>());
printState(initial, coverGraph);
// DFS求解
Set<String> memo = new HashSet<>();
long start = System.currentTimeMillis();
boolean solvable = dfsSolve(initial, coverGraph, memo);
long elapsed = System.currentTimeMillis() - start;
System.out.printf("求解结果: %s (耗时 %dms, 搜索状态数: %d)%n\n",
solvable ? "可解" : "不可解", elapsed, memo.size());
if (solvable && !initial.moves.isEmpty()) {
System.out.println("===== 最优消除序列 =====");
GameState simState = new GameState(cards, new ArrayList<>(), new ArrayList<>());
for (int i = 0; i < initial.moves.size(); i++) {
Move move = initial.moves.get(i);
System.out.printf("Step %d: 选择 [%d]%s -> ", i + 1, move.card.id, move.card.pattern);
List<Card> newSlot = placeIntoSlot(simState.slot, move.card);
List<Card> newRem = new ArrayList<>(simState.remainingCards);
newRem.remove(move.card);
boolean eliminated = newSlot.size() < simState.slot.size() + 1;
System.out.print(eliminated ? "消除! " : "入槽 ");
System.out.printf("(槽位: %d张)%n", newSlot.size());
simState = new GameState(newRem, newSlot, simState.moves);
}
System.out.println("\n全部消除完成!");
}
}
}
算法原理深入
覆盖关系图的构建
覆盖关系图是有向无环图（DAG），边从上层牌指向下层牌。关键性质：
– 如果牌A覆盖牌B，则B在A被移除前不可点击
– 入度为0的节点（不被任何剩余牌覆盖）即为当前可见牌
DFS搜索的剪枝策略
- 槽位溢出剪枝：如果某选择导致槽位超过7张且无法消除，立即回溯
- 图案计数剪枝：如果某图案剩余张数不是3的倍数，且无法与槽位中已有牌组合消除，提前判定不可解
- 记忆化：记录已访问的
(remainingCards, slot)状态，避免重复搜索
复杂度分析
| 指标 | 最坏情况 | 实际游戏 | 说明 |
|---|---|---|---|
| 状态空间 | O(2^N × N!) | 极大剪枝 | N为牌数 |
| 可见牌枚举 | O(V) | V很小 | V为当前可见牌数 |
| 覆盖图构建 | O(N²) | 一次性 | N为总牌数 |
| 实际求解 | 毫秒级 | 剪枝有效 | 小型实例可秒解 |
游戏设计视角
可解性控制
羊了个羊第二关 notoriously 难的原因：
1. 层数设计：关键牌被深层牌完全覆盖，形成”死锁”
2. 图案分布：某些图案的大量牌集中在同一层，导致前期无法有效消除
3. 随机性：完全随机的发牌可能导致本质不可解的局面
改进算法：带随机重启的迭代求解
public static List<Card> generateGuaranteedSolvable(int patterns, int layers) {
for (int attempt = 0; attempt < 1000; attempt++) {
List<Card> cards = generateSolvableGame(patterns, layers);
GameState state = new GameState(cards, new ArrayList<>(), new ArrayList<>());
Map<Card, Set<Card>> graph = buildCoverGraph(cards);
Set<String> memo = new HashSet<>();
if (dfsSolve(state, graph, memo)) {
return cards; // 找到可解布局
}
}
throw new RuntimeException("无法生成可解布局");
}
总结
本文用Java实现了羊了个羊游戏的核心求解引擎，涵盖：
– 多层牌堆的覆盖关系建模与可见牌检测
– 基于栈的槽位消除机制
– DFS回溯搜索与多种剪枝策略
– 可解性分析与保证可解的游戏生成
该实现展示了如何将看似休闲的游戏转化为严谨的组合搜索问题。DFS回溯与状态空间剪枝的思想在自动推理、约束满足问题（CSP）、游戏AI等领域具有普适性。
