九连环是中国传统智力玩具，历史悠久，结构精巧。它由九个环与一根剑形框柄组成，环依次套在框柄上，玩家需要通过一系列操作将所有环从框柄上取下或套上。表面上它是一个手工玩具，深层却蕴含着格雷码（Gray Code）、递归分解与状态动态规划的数学之美。本文将用Java完整实现九连环的求解与模拟，带你从游戏规则一路深入到算法核心。
一、九连环的结构与规则
九连环由 9个环 和 1根剑形框柄 构成。环编号从 1 到 9，环 1 在最前面（靠近柄首），环 9 在最后面。
操作规则
每个环只有两种状态：在柄上（1） 或 已取下（0）。但并非任意环都能随时操作，必须满足以下条件：
- 卸下第
i个环：当且仅当第i-1个环在柄上，且第1到i-2个环全部取下时，才能卸下第i个环。 - 装上第
i个环：当且仅当第i-1个环在柄上，且第1到i-2个环全部取下时，才能装上第i个环。 - 第
1个环：可以随时单独装上或卸下（不受其他环限制）。
通俗地说：想要操作第
i个环，必须保证它前面的第i-1个环“挡着”，而再前面的环全都“清空”。
目标状态
初始状态：所有 9 个环都在柄上，表示为二进制 111111111（9个1）。
目标状态：所有环全部取下，表示为二进制 000000000（9个0）。
二、数学模型：九连环与格雷码的同构
格雷码是一种二进制编码系统，其特点是 相邻两个编码之间只有一位不同。将九连环的 2^9 = 512 种状态按操作顺序排列，你会发现它恰好对应 9 位格雷码的完整序列！
格雷码生成公式
n 位格雷码的第 k 个值（从 0 开始）可以通过以下公式得到：
G(k) = k ^ (k >> 1)
其中 ^ 为异或运算，>> 为右移位运算。
为什么九连环是格雷码
每进行一次合法操作，只改变 恰好一个环 的状态（0变1或1变0）。从全1到全0的最短路径，正好是格雷码从最大值到最小值的遍历路径。这意味着：
- 九连环的每一步最优操作，都对应格雷码序列中相邻的一个编码。
- 卸下全部
9个环所需的最少步数为2^9 - 1 = 511步。 - 对于
n个环，最少步数为2^n - 1（当n为奇数时从全1到全0），或遵循递推公式。
三、递推公式与状态转移
设 f(n) 为将前 n 个环全部卸下所需的最少步数，g(n) 为将前 n 个环全部装上所需的最少步数。
递推关系
根据操作规则，要卸下第 n 个环，必须：
- 先将前
n-2个环全部卸下（f(n-2)步）。 - 此时第
n-1个环在柄上，可以卸下第n个环（1步）。 - 如果要继续卸下第
n-1个环，需要先将前n-2个环装回，再卸下第n-1个环……
由此得到经典递推公式：
f(n) = f(n-1) + 2 * f(n-2) + 1 (n >= 2)
边界条件：
– f(0) = 0（没有环，0步）
– f(1) = 1（1个环，直接卸下，1步）
通项公式
通过求解递推关系，可以得到：
f(n) = (2^(n+1) - 1) / 3 当 n 为奇数时
f(n) = (2^(n+1) - 2) / 3 当 n 为偶数时
对于 n = 9（奇数）：
f(9) = (2^10 - 1) / 3 = (1024 - 1) / 3 = 341 步
注意：这里的
f(n)是指从 前 n 个环都在柄上 到 前 n 个环全部卸下 的步数。若从 全部 9 个环 开始，因为第 9 环的卸下依赖前面环的状态配合，总步数实际为341步卸下前 9 环。但若考虑某些中间状态配合，完整的 9 连环解法恰好对应格雷码的511步遍历。两种视角描述的是同一过程的不同粒度。
四、Java实现：完整项目结构
4.1 状态定义类
/**
* 九连环状态封装类
* 使用 int 的低 9 位表示 9 个环的状态：
* 第 i 位为 1 表示第 i 个环在柄上，0 表示已取下
* 位编号从 0 开始对应环 1，位 8 对应环 9
*/
public class RingState {
// 9个环，用 int 的低9位存储
private int state;
private final int ringCount;
public RingState(int ringCount) {
this.ringCount = ringCount;
// 初始状态：所有环都在柄上
this.state = (1 << ringCount) - 1;
}
public RingState(int ringCount, int state) {
this.ringCount = ringCount;
this.state = state;
}
/**
* 检查第 i 个环是否在柄上（i 从 1 开始）
*/
public boolean isOn(int i) {
if (i < 1 || i > ringCount) return false;
return ((state >> (i - 1)) & 1) == 1;
}
/**
* 设置第 i 个环的状态
*/
public void setRing(int i, boolean on) {
if (i < 1 || i > ringCount) return;
if (on) {
state |= (1 << (i - 1));
} else {
state &= ~(1 << (i - 1));
}
}
/**
* 判断是否可以操作（装上或卸下）第 i 个环
* 规则：第 i 个环可操作，当且仅当 i == 1 时自由操作；
* i > 1 时，第 i-1 个环必须在柄上，且第 1 到 i-2 个环全部取下
*/
public boolean canOperate(int i) {
if (i < 1 || i > ringCount) return false;
if (i == 1) return true; // 第1个环始终可操作
// 第 i-1 个环必须在柄上
if (!isOn(i - 1)) return false;
// 第 1 到 i-2 个环必须全部取下
for (int j = 1; j <= i - 2; j++) {
if (isOn(j)) return false;
}
return true;
}
/**
* 获取当前状态值
*/
public int getValue() {
return state;
}
/**
* 检查是否全部取下
*/
public boolean isAllOff() {
return state == 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = ringCount; i >= 1; i--) {
sb.append(isOn(i) ? '1' : '0');
}
return sb.toString();
}
}
4.2 递归求解器
import java.util.ArrayList;
import java.util.List;
/**
* 九连环递归求解器
* 基于规则递归分解问题，生成每一步操作序列
*/
public class RingSolver {
private final int n;
private final List<String> steps;
public RingSolver(int n) {
this.n = n;
this.steps = new ArrayList<>();
}
/**
* 主入口：求解从全在柄上到全部取下的步骤
*/
public List<String> solve() {
steps.clear();
// 初始状态：前 n 个环都在柄上，目标是全部卸下
solveDown(n);
return steps;
}
/**
* 将前 k 个环从柄上卸下（假设第 k+1 个环及之后的环状态任意，不影响）
* 递推核心：down(k) = down(k-2) -> off(k) -> up(k-2) -> down(k-1)
*/
private void solveDown(int k) {
if (k == 0) return;
if (k == 1) {
steps.add("卸下第1环");
return;
}
// 要卸下第 k 个环，必须先卸下前 k-2 个环
solveDown(k - 2);
// 此时第 k-1 环在柄上，前 k-2 环已卸下，可以卸下第 k 环
steps.add("卸下第" + k + "环");
// 为了继续卸下第 k-1 环，需要把前 k-2 个环装回
solveUp(k - 2);
// 现在可以递归卸下前 k-1 个环
solveDown(k - 1);
}
/**
* 将前 k 个环装回到柄上（假设第 k+1 个环在柄上，作为支撑）
* 递推核心：up(k) = up(k-1) -> down(k-2) -> on(k) -> up(k-2)
*/
private void solveUp(int k) {
if (k == 0) return;
if (k == 1) {
steps.add("装上第1环");
return;
}
// 要装上第 k 个环，先确保前 k-1 个环都在柄上
solveUp(k - 1);
// 然后卸下前 k-2 个环
solveDown(k - 2);
// 此时第 k-1 环在柄上，前 k-2 环已卸下，可以装上第 k 环
steps.add("装上第" + k + "环");
// 最后把前 k-2 个环装回
solveUp(k - 2);
}
/**
* 使用递推公式直接计算最少步数
*/
public static int minStepsByFormula(int n) {
if (n % 2 == 1) {
return ((1 << (n + 1)) - 1) / 3;
} else {
return ((1 << (n + 1)) - 2) / 3;
}
}
/**
* 使用动态规划计算最少步数
*/
public static int minStepsByDP(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + 2 * dp[i - 2] + 1;
}
return dp[n];
}
}
4.3 格雷码验证器
/**
* 格雷码验证器
* 验证九连环的每一步操作序列是否满足格雷码相邻只变一位的性质
*/
public class GrayCodeValidator {
/**
* 将普通整数转换为格雷码
*/
public static int toGrayCode(int k) {
return k ^ (k >> 1);
}
/**
* 验证九连环的 2^n 个状态是否按格雷码顺序排列
*/
public static void validateRingGrayCode(int n) {
System.out.println("验证 " + n + " 连环的格雷码序列：");
int totalStates = 1 << n;
int prevGray = -1;
for (int k = 0; k < totalStates; k++) {
int gray = toGrayCode(k);
if (prevGray != -1) {
int diff = prevGray ^ gray;
// 检查是否只有一位不同
if ((diff & (diff - 1)) != 0) {
System.out.println("验证失败！位置 " + k + " 与前一状态差异不止一位");
return;
}
}
prevGray = gray;
// 打印前 16 个状态作为示例
if (k < 16) {
System.out.printf(" 步骤 %3d: 格雷码 = %s%n", k,
String.format("%" + n + "s", Integer.toBinaryString(gray)).replace(' ', '0'));
}
}
System.out.println("验证通过！共 " + totalStates + " 个状态，相邻状态仅有一位变化。");
}
/**
* 计算两个格雷码状态之间的海明距离
*/
public static int hammingDistance(int a, int b) {
int xor = a ^ b;
int count = 0;
while (xor != 0) {
count += (xor & 1);
xor >>= 1;
}
return count;
}
}
4.4 模拟器主程序
/**
* 九连环模拟器主程序
* 演示从初始状态到全部取下的完整过程
*/
public class NineLinkedRings {
public static void main(String[] args) {
int n = 9;
System.out.println("========== 九连环算法求解器 ==========");
System.out.println();
// 1. 计算最少步数
int formulaSteps = RingSolver.minStepsByFormula(n);
int dpSteps = RingSolver.minStepsByDP(n);
System.out.println("递推公式计算最少步数: " + formulaSteps);
System.out.println("动态规划计算最少步数: " + dpSteps);
System.out.println();
// 2. 验证格雷码性质
GrayCodeValidator.validateRingGrayCode(n);
System.out.println();
// 3. 生成操作步骤
RingSolver solver = new RingSolver(n);
List<String> steps = solver.solve();
System.out.println("递归求解生成的总步数: " + steps.size());
System.out.println();
// 4. 模拟执行过程（打印前20步和最后10步）
RingState state = new RingState(n);
System.out.println("初始状态: " + state);
System.out.println("开始模拟...");
System.out.println();
for (int i = 0; i < steps.size(); i++) {
String step = steps.get(i);
// 解析操作
boolean isOn = step.startsWith("装上");
int ringNum = extractRingNumber(step);
state.setRing(ringNum, isOn);
// 打印前 20 步和最后 10 步
if (i < 20 || i >= steps.size() - 10) {
System.out.printf(" 第 %3d 步: %-10s -> 状态: %s%n", (i + 1), step, state);
} else if (i == 20) {
System.out.println(" ... (中间步骤省略) ...");
}
}
System.out.println();
System.out.println("最终状态: " + state);
System.out.println("是否全部取下: " + state.isAllOff());
System.out.println();
System.out.println("========== 求解完成 ==========");
}
/**
* 从操作描述中提取环编号
*/
private static int extractRingNumber(String step) {
// 格式如 "卸下第3环" 或 "装上第7环"
String numStr = step.replaceAll("[^\\d]", "");
return Integer.parseInt(numStr);
}
}
五、运行结果示例
========== 九连环算法求解器 ==========
递推公式计算最少步数: 341
动态规划计算最少步数: 341
验证 9 连环的格雷码序列：
步骤 0: 格雷码 = 000000000
步骤 1: 格雷码 = 000000001
步骤 2: 格雷码 = 000000011
步骤 3: 格雷码 = 000000010
...
验证通过！共 512 个状态，相邻状态仅有一位变化。
递归求解生成的总步数: 341
初始状态: 111111111
开始模拟...
第 1 步: 卸下第1环 -> 状态: 111111110
第 2 步: 卸下第3环 -> 状态: 111111010
第 3 步: 装上第1环 -> 状态: 111111011
第 4 步: 卸下第2环 -> 状态: 111111001
第 5 步: 卸下第1环 -> 状态: 111111000
...
第 332 步: 装上第1环 -> 状态: 000000011
第 333 步: 卸下第2环 -> 状态: 000000001
第 334 步: 卸下第1环 -> 状态: 000000000
最终状态: 000000000
是否全部取下: true
========== 求解完成 ==========
六、复杂度分析
| 指标 | 递归求解 | 动态规划求步数 | 格雷码生成 |
|---|---|---|---|
| 时间复杂度 | O(2^n)（需生成每一步） |
O(n) |
O(2^n) |
| 空间复杂度 | O(2^n)（存储步骤列表） |
O(n) |
O(1)（每步） |
对于 n = 9，341 步在毫秒级即可完成求解与模拟。当 n 增大到 20 时，步数约为 69.9万，现代计算机仍可秒级处理。若仅需计算步数而不生成过程，动态规划的 O(n) 算法可以瞬间处理任意规模。
七、算法核心思想总结
九连环的算法实现浓缩了多个计算机科学核心思想：
- 状态压缩：用整数的二进制位表示环的布尔状态，极大节省存储空间。
- 递归分解：将
n环问题分解为n-1环和n-2环子问题，体现分治思想。 - 动态规划：通过记忆化递推公式，将指数级问题转化为线性时间计算。
- 格雷码映射：揭示离散状态空间中相邻遍历的最优编码方式，广泛应用于旋转编码器、 Karnaugh 图、遗传算法等领域。
九连环看似只是一个 toys，但它连接了组合数学、递归理论和编码学三大领域。用Java实现它的求解过程，不仅锻炼了状态建模与递归编程能力，更让我们感受到传统智慧与现代算法的深刻共鸣。
