引言
Slitherlink（数回/Loop the Loop）是日本 Nikoli 出版社发明的经典逻辑谜题：在由点构成的网格中，部分格子标有数字 0~3，表示围绕该格子的封闭回路经过的边数。玩家需要画出一条连续的闭合回路，满足所有数字约束。
本文将用 Java 实现 Slitherlink 求解器，核心算法基于约束传播（Constraint Propagation）与回溯搜索（Backtracking Search），展示如何从局部约束逐步推导出全局解。
问题建模
棋盘表示
对于 m×n 的数字网格：
– 水平边：m+1 行，每行 n 条
– 垂直边：m 行，每行 n+1 条
– 总边数：(m+1)×n + m×(n+1)
用三个二维数组表示：
hEdges[m+1][n] // 水平边：0=无, 1=有, -1=未知
vEdges[m][n+1] // 垂直边：0=无, 1=有, -1=未知
numbers[m][n] // 格子数字：-1=空, 0~3=约束
约束条件
每个数字格子周围的4条边之和必须等于该数字：
– 上 hEdges[i][j]
– 下 hEdges[i+1][j]
– 左 vEdges[i][j]
– 右 vEdges[i][j+1]
此外，回路必须是单一的闭合环，不能有分叉或孤立线段。
核心算法：约束传播 + 回溯搜索
约束传播规则
从数字约束可以直接推断边的状态：
| 数字 | 已确定边 | 剩余未知边 | 推断 |
|---|---|---|---|
| 0 | 0 | 4 | 所有边 = 0 |
| 3 | 0 | 4 | 所有边 = 1 |
| 3 | 1 | 3 | 剩余3条边 = 1 |
| 0 | 1 | 3 | 矛盾（回溯） |
| 2 | 1 | 3 | 剩余中选2条 = 1 |
| 1 | 0 | 4 | 无法直接推断 |
进阶规则（顶点约束）：
– 每个顶点的度只能是 0 或 2（回路无分叉）
– 若某顶点已有2条边确定，其余边必须为0
– 若某顶点已有3条边确定为0，第4条必须为… 不，回路不要求经过每个顶点
等等，修正：顶点的度可以是 0（回路不经过）或 2（回路经过）。
回溯搜索
当约束传播无法继续时，选择一个未知边进行假设（设为0或1），然后递归求解。若导致矛盾则回溯。
完整 Java 实现
import java.util.*;
/**
* Slitherlink（数回）求解器
* 基于约束传播与回溯搜索的逻辑谜题求解
*/
public class SlitherlinkSolver {
// 边状态
static final int UNKNOWN = -1;
static final int EMPTY = 0;
static final int LINE = 1;
int rows, cols;
int[][] numbers; // 数字约束
int[][] hEdges; // 水平边 [rows+1][cols]
int[][] vEdges; // 垂直边 [rows][cols+1]
public SlitherlinkSolver(int[][] numbers) {
this.rows = numbers.length;
this.cols = numbers[0].length;
this.numbers = new int[rows][cols];
for (int i = 0; i < rows; i++) {
this.numbers[i] = numbers[i].clone();
}
this.hEdges = new int[rows + 1][cols];
this.vEdges = new int[rows][cols + 1];
// 初始化为未知
for (int[] row : hEdges) Arrays.fill(row, UNKNOWN);
for (int[] row : vEdges) Arrays.fill(row, UNKNOWN);
}
/**
* 主求解方法：约束传播 + 回溯
*/
public boolean solve() {
// 先进行约束传播
boolean changed;
do {
changed = propagateConstraints();
} while (changed);
// 检查是否已解决
if (isComplete() && isValidLoop()) {
return true;
}
// 检查是否有矛盾
if (hasContradiction()) {
return false;
}
// 选择一个未知边进行分支
Edge branchEdge = selectBranchEdge();
if (branchEdge == null) {
return isComplete() && isValidLoop();
}
// 保存状态
int[][] savedHEdges = copyArray(hEdges);
int[][] savedVEdges = copyArray(vEdges);
// 尝试设为 LINE
setEdge(branchEdge, LINE);
if (solve()) return true;
// 恢复状态
hEdges = savedHEdges;
vEdges = savedVEdges;
savedHEdges = copyArray(hEdges);
savedVEdges = copyArray(vEdges);
// 尝试设为 EMPTY
setEdge(branchEdge, EMPTY);
if (solve()) return true;
// 恢复状态
hEdges = savedHEdges;
vEdges = savedVEdges;
return false;
}
/**
* 约束传播：利用数字和顶点约束推断边的状态
*/
boolean propagateConstraints() {
boolean changed = false;
// 规则1：数字约束传播
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (numbers[r][c] < 0) continue;
int target = numbers[r][c];
int[] edges = getCellEdges(r, c);
int lineCount = 0, emptyCount = 0, unknownCount = 0;
List<Edge> unknownEdges = new ArrayList<>();
for (Edge e : edges) {
int val = getEdgeValue(e);
if (val == LINE) lineCount++;
else if (val == EMPTY) emptyCount++;
else {
unknownCount++;
unknownEdges.add(e);
}
}
// 如果已有太多LINE，矛盾
if (lineCount > target) return false; // 触发回溯
// 如果已有太多EMPTY，无法满足target
if (emptyCount > 4 - target) return false;
// 如果剩余未知边必须全为LINE
if (lineCount + unknownCount == target) {
for (Edge e : unknownEdges) {
if (getEdgeValue(e) == UNKNOWN) {
setEdge(e, LINE);
changed = true;
}
}
}
// 如果剩余未知边必须全为EMPTY
if (lineCount == target) {
for (Edge e : unknownEdges) {
if (getEdgeValue(e) == UNKNOWN) {
setEdge(e, EMPTY);
changed = true;
}
}
}
}
}
// 规则2：顶点度数约束
// 每个顶点度数只能是0或2
for (int r = 0; r <= rows; r++) {
for (int c = 0; c <= cols; c++) {
List<Edge> incident = getIncidentEdges(r, c);
int lineCount = 0, emptyCount = 0;
List<Edge> unknownEdges = new ArrayList<>();
for (Edge e : incident) {
int val = getEdgeValue(e);
if (val == LINE) lineCount++;
else if (val == EMPTY) emptyCount++;
else unknownEdges.add(e);
}
// 若已有2条LINE，其余必须为EMPTY
if (lineCount == 2) {
for (Edge e : unknownEdges) {
if (getEdgeValue(e) == UNKNOWN) {
setEdge(e, EMPTY);
changed = true;
}
}
}
// 若已有3条EMPTY，且还有未知边
// 如果只剩1条未知边：若lineCount==0则设为LINE（度=2）
// 若lineCount==1则矛盾（度不能为1）
if (emptyCount == incident.size() - 1 && unknownEdges.size() == 1) {
if (lineCount == 0) {
setEdge(unknownEdges.get(0), LINE);
changed = true;
} else if (lineCount == 1) {
return false; // 度=1，矛盾
}
}
// 若lineCount > 2，矛盾
if (lineCount > 2) return false;
}
}
// 规则3：避免小环（除非已完整）
if (!isComplete()) {
// 检查是否有不完整的小环
// 简化版：暂不实现复杂环检测，留到最终验证
}
return changed;
}
/**
* 获取格子周围的4条边
*/
Edge[] getCellEdges(int r, int c) {
return new Edge[] {
new Edge(true, r, c), // 上
new Edge(true, r + 1, c), // 下
new Edge(false, r, c), // 左
new Edge(false, r, c + 1) // 右
};
}
/**
* 获取顶点关联的边（最多4条）
*/
List<Edge> getIncidentEdges(int r, int c) {
List<Edge> edges = new ArrayList<>();
// 上水平边
if (r > 0 && c < cols) edges.add(new Edge(true, r, c));
// 下水平边
if (r < rows && c < cols) edges.add(new Edge(true, r + 1, c)); // 修正索引
// 实际上水平边是 hEdges[r][c] 表示第r行第c列上方的水平边
// 重新设计：hEdges[i][j] 连接 (i,j) 和 (i,j+1)
edges.clear();
// 上方水平边（如果存在）
if (r > 0 && c < cols) edges.add(new Edge(true, r - 1, c)); // hEdges[r-1][c] 在顶点(r,c)上方？
// 不对，重新梳理索引
// hEdges[i][j]: 连接点(i,j)和(i,j+1)的水平边，i=0..rows, j=0..cols-1
// vEdges[i][j]: 连接点(i,j)和(i+1,j)的垂直边，i=0..rows-1, j=0..cols
// 顶点(r,c)的关联边：
// 左水平边: hEdges[r][c-1] (如果 c > 0)
// 右水平边: hEdges[r][c] (如果 c < cols)
// 上垂直边: vEdges[r-1][c] (如果 r > 0)
// 下垂直边: vEdges[r][c] (如果 r < rows)
if (c > 0) edges.add(new Edge(true, r, c - 1));
if (c < cols) edges.add(new Edge(true, r, c));
if (r > 0) edges.add(new Edge(false, r - 1, c));
if (r < rows) edges.add(new Edge(false, r, c));
return edges;
}
int getEdgeValue(Edge e) {
return e.isHorizontal ? hEdges[e.r][e.c] : vEdges[e.r][e.c];
}
void setEdge(Edge e, int value) {
if (e.isHorizontal) hEdges[e.r][e.c] = value;
else vEdges[e.r][e.c] = value;
}
/**
* 选择分支边：优先选择约束最强的未知边
*/
Edge selectBranchEdge() {
// 策略：选择涉及最多数字约束的未知边
for (int r = 0; r <= rows; r++) {
for (int c = 0; c < cols; c++) {
if (hEdges[r][c] == UNKNOWN) {
return new Edge(true, r, c);
}
}
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c <= cols; c++) {
if (vEdges[r][c] == UNKNOWN) {
return new Edge(false, r, c);
}
}
}
return null;
}
/**
* 检查是否所有边都已确定
*/
boolean isComplete() {
for (int[] row : hEdges) {
for (int v : row) if (v == UNKNOWN) return false;
}
for (int[] row : vEdges) {
for (int v : row) if (v == UNKNOWN) return false;
}
return true;
}
/**
* 检查是否有矛盾
*/
boolean hasContradiction() {
// 数字约束矛盾
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (numbers[r][c] < 0) continue;
int target = numbers[r][c];
Edge[] edges = getCellEdges(r, c);
int lineCount = 0, unknownCount = 0;
for (Edge e : edges) {
int v = getEdgeValue(e);
if (v == LINE) lineCount++;
else if (v == UNKNOWN) unknownCount++;
}
if (lineCount > target) return true;
if (lineCount + unknownCount < target) return true;
}
}
// 顶点度数矛盾
for (int r = 0; r <= rows; r++) {
for (int c = 0; c <= cols; c++) {
List<Edge> incident = getIncidentEdges(r, c);
int lineCount = 0;
for (Edge e : incident) {
if (getEdgeValue(e) == LINE) lineCount++;
}
if (lineCount > 2) return true;
}
}
return false;
}
/**
* 验证回路是否合法：单一的闭合环
*/
boolean isValidLoop() {
// 1. 所有数字约束满足
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (numbers[r][c] < 0) continue;
Edge[] edges = getCellEdges(r, c);
int lineCount = 0;
for (Edge e : edges) {
if (getEdgeValue(e) == LINE) lineCount++;
}
if (lineCount != numbers[r][c]) return false;
}
}
// 2. 所有顶点度数为0或2
for (int r = 0; r <= rows; r++) {
for (int c = 0; c <= cols; c++) {
List<Edge> incident = getIncidentEdges(r, c);
int lineCount = 0;
for (Edge e : incident) {
if (getEdgeValue(e) == LINE) lineCount++;
}
if (lineCount != 0 && lineCount != 2) return false;
}
}
// 3. 检查是单一回路（不是多个小环）
// 找到一条LINE边，沿回路遍历，统计经过的边数
int totalLineEdges = 0;
Edge startEdge = null;
for (int r = 0; r <= rows; r++) {
for (int c = 0; c < cols; c++) {
if (hEdges[r][c] == LINE) {
totalLineEdges++;
if (startEdge == null) startEdge = new Edge(true, r, c);
}
}
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c <= cols; c++) {
if (vEdges[r][c] == LINE) {
totalLineEdges++;
if (startEdge == null) startEdge = new Edge(false, r, c);
}
}
}
if (totalLineEdges == 0) return false; // 空回路
// BFS/DFS沿回路遍历
Set<String> visited = new HashSet<>();
int traversed = traverseLoop(startEdge, visited);
return traversed == totalLineEdges;
}
/**
* 沿回路遍历，返回经过的边数
*/
int traverseLoop(Edge start, Set<String> visited) {
int count = 0;
Edge current = start;
Edge prev = null;
while (current != null) {
String key = current.toString();
if (visited.contains(key)) break;
visited.add(key);
count++;
// 找到当前边的两个端点
int[][] endpoints = getEndpoints(current);
Edge next = null;
for (int[] ep : endpoints) {
List<Edge> incident = getIncidentEdges(ep[0], ep[1]);
for (Edge e : incident) {
if (getEdgeValue(e) == LINE && !e.equals(current) && !e.equals(prev)) {
next = e;
break;
}
}
if (next != null) break;
}
prev = current;
current = next;
}
return count;
}
int[][] getEndpoints(Edge e) {
if (e.isHorizontal) {
return new int[][]{{e.r, e.c}, {e.r, e.c + 1}};
} else {
return new int[][]{{e.r, e.c}, {e.r + 1, e.c}};
}
}
int[][] copyArray(int[][] arr) {
int[][] copy = new int[arr.length][];
for (int i = 0; i < arr.length; i++) {
copy[i] = arr[i].clone();
}
return copy;
}
/**
* 打印解答
*/
void printSolution() {
System.out.println("=== Slitherlink 解答 ===");
for (int r = 0; r <= rows; r++) {
// 打印水平边和点
for (int c = 0; c <= cols; c++) {
System.out.print("·");
if (c < cols) {
System.out.print(hEdges[r][c] == LINE ? "───" : " ");
}
}
System.out.println();
// 打印垂直边和数字
if (r < rows) {
for (int c = 0; c <= cols; c++) {
System.out.print(vEdges[r][c] == LINE ? "│" : " ");
if (c < cols) {
if (numbers[r][c] >= 0) {
System.out.print(" " + numbers[r][c] + " ");
} else {
System.out.print(" ");
}
}
}
System.out.println();
}
}
}
/**
* 边类
*/
static class Edge {
final boolean isHorizontal;
final int r, c;
Edge(boolean isHorizontal, int r, int c) {
this.isHorizontal = isHorizontal;
this.r = r;
this.c = c;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Edge)) return false;
Edge edge = (Edge) o;
return isHorizontal == edge.isHorizontal && r == edge.r && c == edge.c;
}
@Override
public int hashCode() {
return Objects.hash(isHorizontal, r, c);
}
@Override
public String toString() {
return (isHorizontal ? "H" : "V") + "(" + r + "," + c + ")";
}
}
public static void main(String[] args) {
// 5x5 示例谜题 (-1表示无数字)
int[][] puzzle = {
{ 2, 3,-1, 2, 1},
{ 2,-1, 2,-1, 3},
{-1, 2, 1, 3,-1},
{ 1,-1, 3,-1, 2},
{ 3, 2,-1, 2, 1}
};
SlitherlinkSolver solver = new SlitherlinkSolver(puzzle);
System.out.println("求解中...");
long start = System.currentTimeMillis();
boolean solved = solver.solve();
long end = System.currentTimeMillis();
if (solved) {
System.out.println("求解成功！耗时 " + (end - start) + "ms");
solver.printSolution();
} else {
System.out.println("无解！");
}
// 更小的测试
int[][] smallPuzzle = {
{3, 2},
{2, 3}
};
System.out.println("\n=== 2x2 小谜题 ===");
SlitherlinkSolver solver2 = new SlitherlinkSolver(smallPuzzle);
if (solver2.solve()) {
solver2.printSolution();
} else {
System.out.println("无解");
}
}
}
算法解析
约束传播的核心思想
Slitherlink 的约束具有局部传播性：一个数字格子的约束会影响其四条边，边的确定又会通过顶点约束影响相邻格子的边。这种连锁反应可以大幅缩小搜索空间。
为何约束传播 + 回溯如此高效
对于 5×5 的 Slitherlink：
– 无约束传播：2^60 种可能（约 10^18）
– 约束传播后：通常只剩下极少数未知边需要分支
– 回溯深度：通常 < 10
顶点度数约束的重要性
顶点度数只能是 0 或 2 的规则是排除非法解的关键：
– 防止分叉（度 > 2）
– 防止死路（度 = 1）
– 结合数字约束，可以快速确定大量边的状态
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 约束传播 | O(R×C) | 每轮扫描所有格子和顶点 |
| 最坏情况回溯 | O(2^E) | E=边数，实际远小于此 |
| 5×5 谜题 | 毫秒级 | 约束传播后搜索空间极小 |
| 10×10 谜题 | 秒级 | 需要更多分支 |
扩展思考
- 高级约束规则：角点规则、边规则等可以进一步减少分支。
- 对称性剪枝：利用棋盘对称性避免重复搜索。
- 人机交互求解：将求解器改造为提示系统，逐步揭示推理过程。
总结
Slitherlink 求解器完美演绎了约束满足问题（CSP）的经典解法：约束传播快速缩小搜索空间，回溯搜索处理剩余不确定性。这一组合策略是数独、扫雷、填字游戏等逻辑谜题求解的通用框架。
