# cube_cross_solve **Repository Path**: andnnl/cube_cross_solve ## Basic Information - **Project Name**: cube_cross_solve - **Description**: 一个使用预计算搜索表快速求解魔方底面十字的 Rust 程序。 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-01-21 - **Last Updated**: 2026-01-23 ## Categories & Tags **Categories**: Uncategorized **Tags**: Rust ## README # 魔方底面十字求解器 一个使用预计算搜索表快速求解魔方底面十字的 Rust 程序。 ## 功能特性 - 8步以内最优解求解 - 支持显示多个解法（最多5个） - 搜索时间 < 0.1ms - 预计算搜索表缓存到文件 - 交互式命令行界面 ## 快速开始 ```bash # 编译 cargo build --release # 运行 cargo run --release # 测试 cargo test ``` ## 使用方法 ``` === 魔方底面十字求解器 === > R U R' F2 L' B 打乱: R U R' F2 L' B 1. B' L F2 (3步) 2. B' L F2 U (4步) 3. B' L F2 U' (4步) 耗时: 0.045ms > q 再见！ ``` ![demo](demo/demo.png "demo") --- ## 算法设计 ### 1. 问题定义 **目标**: 给定任意魔方状态，找到最少步数完成底面十字。 **底面十字完成条件**: - 4个白色棱块（DF、DR、DB、DL）在正确位置 - 4个白色棱块方向正确（白色朝下） ### 2. 状态空间分析 ``` ┌─────────────────────────────────────────────────────────────┐ │ 状态空间分析 │ ├─────────────────────────────────────────────────────────────┤ │ 完整魔方棱块状态: 12! × 2^11 ≈ 980 亿 │ │ 底面十字状态: 12^4 × 2^4 = 331,776 │ │ 8步内可达状态: 190,080 │ ├─────────────────────────────────────────────────────────────┤ │ 压缩比: 99.99998% │ └─────────────────────────────────────────────────────────────┘ ``` ### 3. 核心数据结构 #### 3.1 棱块位置 (EdgePos) ``` ┌──────────────┐ │ UB │ │ UL [U] UR │ ← 顶层 (U面) │ UF │ ┌───────┼──────────────┼───────┬───────┐ │ BL │ FL │ FR │ BR │ ← 中层 (E层) └───────┼──────────────┼───────┴───────┘ │ DF │ │ DL [D] DR │ ← 底层 (D面) - 目标 │ DB │ └──────────────┘ 位置编号: UF=0, UR=1, UB=2, UL=3 (顶层) FR=4, FL=5, BR=6, BL=7 (中层) DF=8, DR=9, DB=10, DL=11 (底层) ``` #### 3.2 状态编码 ``` 每个棱块: 5位 = 4位位置 + 1位方向 4个棱块: 20位，使用 u32 存储 32位整数布局: ┌────────────┬────────────┬────────────┬────────────┬────────────┐ │ 未使用 │ 棱块3 │ 棱块2 │ 棱块1 │ 棱块0 │ │ (12位) │ (5位) │ (5位) │ (5位) │ (5位) │ └────────────┴────────────┴────────────┴────────────┴────────────┘ 每个棱块的5位: ┌──────┬───────────┐ │ flip │ position │ │(1位) │ (4位) │ └──────┴───────────┘ ``` #### 3.3 方向翻转规则 ``` 转动类型 │ 是否翻转方向 ────────────────┼───────────── U, U2, U' │ 否 D, D2, D' │ 否 L, L2, L' │ 否 R, R2, R' │ 否 F, F2, F' │ 是 ← 跨越水平/垂直平面 B, B2, B' │ 是 ← 跨越水平/垂直平面 ``` **翻转原因**: F/B 面转动会使棱块在水平和垂直位置间移动，导致白色面朝向改变。 ``` F转动前 (DF位置): F转动后 (FL位置): ┌───┐ ┌───┐ │ G │ ← 绿色朝前 │ W │ ← 白色朝前 (翻转!) ├───┤ ├───┤ │ W │ ← 白色朝下 │ G │ ← 绿色朝左 └───┘ └───┘ ``` --- ## 算法流程 ### 1. 搜索表生成 (BFS) ``` ┌─────────────────────────────────────────────────────────────────┐ │ 搜索表生成流程 │ └─────────────────────────────────────────────────────────────────┘ ┌─────────────┐ │ 已解决状态 │ depth = 0 │ (1个状态) │ └──────┬──────┘ │ ▼ 应用18种转动 ┌─────────────┐ │ 1步可达状态 │ depth = 1 │ (15个) │ └──────┬──────┘ │ ▼ 继续扩展 ┌─────────────┐ │ 2步可达状态 │ depth = 2 │ (158个) │ └──────┬──────┘ │ ▼ ... │ ▼ ┌─────────────┐ │ 8步可达状态 │ depth = 8 │ (102个) │ └─────────────┘ 各深度状态数量: ┌───────┬─────────┬────────────┐ │ 深度 │ 状态数 │ 累计 │ ├───────┼─────────┼────────────┤ │ 0 │ 1 │ 1 │ │ 1 │ 15 │ 16 │ │ 2 │ 158 │ 174 │ │ 3 │ 1,394 │ 1,568 │ │ 4 │ 9,809 │ 11,377 │ │ 5 │ 46,381 │ 57,758 │ │ 6 │ 97,254 │ 155,012 │ │ 7 │ 34,966 │ 189,978 │ │ 8 │ 102 │ 190,080 │ └───────┴─────────┴────────────┘ ``` ### 2. 求解流程 (单解) ``` ┌─────────────────────────────────────────────────────────────────┐ │ 单解求解流程 │ └─────────────────────────────────────────────────────────────────┘ 输入: 打乱公式 "R U R' F" │ ▼ ┌─────────────────┐ │ 解析打乱公式 │ │ 应用到初始状态 │ └────────┬────────┘ │ ▼ ┌─────────────────┐ │ 计算状态编码 │ encode() → u32 └────────┬────────┘ │ ▼ ┌─────────────────┐ │ 查询搜索表 │ table[code] → depth │ 获取第一步 │ moves[code] → Move └────────┬────────┘ │ ▼ ┌─────────────────┐ │ 应用转动 │ │ 重复直到解决 │ └────────┬────────┘ │ ▼ 输出: 解法 "F' R U' R'" ``` ### 3. 多解搜索流程 (DFS + 剪枝) ``` ┌─────────────────────────────────────────────────────────────────┐ │ 多解搜索流程 │ └─────────────────────────────────────────────────────────────────┘ ┌─────────────┐ │ 初始状态 │ │ min_depth=4│ └──────┬──────┘ │ ┌────────────┼────────────┐ ▼ ▼ ▼ ┌────────┐ ┌────────┐ ┌────────┐ │ 深度=4 │ │ 深度=5 │ │ 深度=6 │ ... │ 搜索 │ │ 搜索 │ │ 搜索 │ └────┬───┘ └────┬───┘ └────────┘ │ │ ▼ ▼ 找到2个解 找到3个解 │ │ └─────┬──────┘ ▼ ┌──────────┐ │ 合并排序 │ │ 返回5个 │ └──────────┘ 剪枝策略: ┌─────────────────────────────────────────────────────────────────┐ │ 1. 深度剪枝: remaining_depth == 0 且未解决 → 返回 │ │ 2. 搜索表剪枝: min_steps > remaining_depth → 返回 │ │ 3. 同面剪枝: 上一步是U，这一步不能是U/U2/U' → 跳过 │ │ 4. 数量剪枝: solutions.len() >= max_solutions → 返回 │ └─────────────────────────────────────────────────────────────────┘ ``` --- ## 架构设计 ### 模块结构 ``` src/main.rs ├── EdgePos # 12个棱块位置枚举 ├── Move # 18种转动操作 ├── Edge # 单个棱块状态 (位置+方向) ├── CrossState # 底面十字状态 (4个棱块) │ ├── encode() # 状态编码 │ ├── decode() # 状态解码 │ ├── apply_move() # 应用转动 │ └── is_solved() # 检查是否完成 ├── PruningTable # 预计算搜索表 │ ├── generate() # BFS生成 │ ├── save/load() # 文件IO │ ├── solve() # 单解求解 │ └── solve_multi()# 多解求解 └── main() # 主程序入口 ``` ### 数据流 ``` ┌──────────────────────────────────────────────────────────────────┐ │ 数据流图 │ └──────────────────────────────────────────────────────────────────┘ 启动 │ ▼ ┌─────────────────────────┐ │ 加载/生成搜索表 │ │ cross_table.bin │ │ (2.6MB, 190080状态) │ └────────────┬────────────┘ │ ▼ ┌─────────────────────────┐ │ 随机测试 (10个) │ │ generate_scramble() │ └────────────┬────────────┘ │ ▼ ┌─────────────────────────┐ │ 交互式循环 │◄─────┐ │ 等待用户输入 │ │ └────────────┬────────────┘ │ │ │ ▼ │ ┌─────────────────────────┐ │ │ scramble_state() │ │ │ 解析打乱公式 │ │ └────────────┬────────────┘ │ │ │ ▼ │ ┌─────────────────────────┐ │ │ solve_multi() │ │ │ 搜索多个解法 │ │ └────────────┬────────────┘ │ │ │ ▼ │ ┌─────────────────────────┐ │ │ 打印解法和耗时 │──────┘ └─────────────────────────┘ ``` --- ## 性能分析 ### 时间复杂度 | 操作 | 复杂度 | 说明 | |------|--------|------| | 搜索表生成 | O(N × M) | N=190080, M=18 | | 单解查询 | O(D) | D=解法步数(≤8) | | 多解搜索 | O(M^D) | 但有剪枝优化 | | 状态编码 | O(1) | 位运算 | ### 空间复杂度 | 数据结构 | 大小 | 说明 | |----------|------|------| | 搜索表 | ~2.6MB | 190080 × (4+1+8) bytes | | 运行时内存 | <1MB | 栈上递归 | ### 实测性能 ``` 测试环境: Intel i7, Windows 11 搜索表生成: ~200ms (首次) 搜索表加载: ~50ms (从文件) 单次求解: ~0.05-0.1ms ``` --- ## 文件结构 ``` cube_cross_solve/ ├── Cargo.toml # 项目配置 ├── Cargo.lock # 依赖锁定 ├── src/ │ └── main.rs # 源代码 (含详细注释) ├── cross_table.bin # 预计算搜索表 (运行后生成) ├── README.md # 本文档 └── CLAUDE.md # Claude Code 指南 ``` --- ## 扩展方向 1. **GUI界面**: 添加3D魔方可视化 2. **完整求解**: 扩展到F2L、OLL、PLL 3. **优化搜索**: 实现IDA*算法 4. **并行计算**: 多线程生成搜索表 5. **WASM编译**: 支持网页端运行 --- ## 参考资料 - [Kociemba算法](http://kociemba.org/cube.htm) - [Herbert Kociemba's Two-Phase Algorithm](https://www.speedsolving.com/wiki/index.php/Kociemba%27s_Algorithm) - [魔方状态空间分析](https://www.speedsolving.com/wiki/index.php/Cube_explorer) ## License MIT