# 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-09-09
## Categories & Tags
**Categories**: Uncategorized
**Tags**: Rust
## README
# 魔方底面十字求解器
一个使用预计算搜索表快速求解魔方底面十字的 Rust 程序，同时支持 **XCross**（十字 + 一组 F2L）最优求解，可编译为 CLI 与 WebAssembly 两种形态。
## 功能特性
- **十字求解**：8 步以内最优解，搜索时间 < 0.1ms，支持多解展示
- **XCross 求解**：完成底面十字的同时完成一组 F2L（角块 + 棱块贴纸颜色全部正确）
- IDA* 最优搜索，保证解最短（实测 20 步打乱平均 7 步左右，上限 11 步）
- 支持 FR / FL / BR / BL 任一槽位，或 4 槽位自动取最优
- 单次求解 0.7~2.2ms（CLI），浏览器内 < 1ms
- **F2L 全解**：十字 + 4 组 F2L 全部完成
- 预计算搜索表缓存到文件 / IndexedDB
- 交互式命令行 + 网页可视化界面
## 快速开始
```bash
# 编译 CLI
cargo build --release
# 运行测试
cargo test
# 运行
./target/release/cross-solver
```
## CLI 使用方法
### 1. 命令行参数模式（一次性求解）
```bash
# 普通十字求解
./target/release/cross-solver "R U R' F2 L' B"
# XCross 求解（4 个槽位自动取最优）
./target/release/cross-solver "x:R U R' F"
# XCross 指定槽位（FR / FL / BR / BL 任选）
./target/release/cross-solver "x:FR R U R' F"
# F2L 全解模式（十字 + 4 组 F2L 全部完成）
./target/release/cross-solver "f2l:R U R' F"
```
### 2. 交互模式（不带参数）
```bash
./target/release/cross-solver
```
```
> R U R' F2 L' B ← 普通十字求解
1. B' L F2 (3步)
> x FR R U R' U' ← XCross 指定 FR 槽位
1. F' R U' R' (4步, +3) [前右]
> x R U R' U' ← XCross 4 槽位取最优
> f2l R U R' U' ← F2L 全解模式
> q ← 退出
```
### XCross 输出解读
```
XCross 解法（十字+一组F2L，最优）:
1. F' R U' R' (4步, +3) [前右]
```
- `4步` — 解法总步数（最优）
- `+3` — 比纯十字解多的步数（`±0` 表示完成十字的同时"白送"一组 F2L）
- `[前右]` — 完成的槽位（FR），解法应用后十字与该槽位 F2L 均完全还原
### 输入格式
- 打乱公式：标准记号 `R U R' F2 D' B2`（U/D/F/B/L/R + `'/2` 后缀）
- 完整魔方状态：54 字符串 `UUUUUUUUURRRRRRRRR...`
## WASM 构建（浏览器端）
### 构建步骤
```bash
# 安装 wasm-pack（一次性）
cargo install wasm-pack
# 构建产物输出到 pkg/（Windows 可用 build_wasm.bat）
wasm-pack build --target web --out-dir pkg --release
```
构建产物（`pkg/` 目录，wasm 二进制仅约 150KB）：
| 文件 | 说明 |
|------|------|
| `cube_cross_solve_bg.wasm` | WASM 二进制 |
| `cube_cross_solve.js` | JS 绑定（ESM 命名导出） |
| `cube_cross_solve_bg.js` | WASM 加载器 |
| `cube_cross_solve.d.ts` | TypeScript 类型定义 |
| `package.json` | npm 包描述 |
### 运行网页界面
WASM 必须通过 HTTP 服务器运行（不能直接双击 index.html）：
```bash
python3 -m http.server 8000
# 浏览器打开 http://localhost:8000
```
首次打开会自动生成搜索表（约 5-10 秒）并缓存到 IndexedDB，之后秒开。
> **注意**：`index.html` 可视化界面目前提供**十字求解**功能；**XCross 求解**（`solve_xcross`）目前仅通过 JS API 提供，可在控制台或自己的代码中按下方 API 说明调用。
### JavaScript API 使用说明
**重要**：所有函数必须通过**命名导出**调用；`init default()` 的返回值是 raw wasm exports，直接调用会得到 `[ptr,len]` 原始值。
```javascript
// 1. 初始化（推荐先 fetch 字节再传入，可彻底绕开 HTTP 缓存问题）
const wasm = await import('./pkg/cube_cross_solve.js');
const resp = await fetch('./pkg/cube_cross_solve_bg.wasm', {cache: 'no-store'});
await wasm.default(await resp.arrayBuffer());
// 2. 生成搜索表（或用 load_table_from_bytes 加载缓存的二进制）
await wasm.generate_table(8);
// wasm.load_table_from_bytes(cachedBytes); // 从 IndexedDB 缓存加载
// 3. 十字求解
const solutions = wasm.solve_multi("R U R' F", 3);
// => [["B'","L","F2"], ["B'","L","F2","U"], ...]
// 4. XCross 求解（slot: "FR"/"FL"/"BR"/"BL"/"ALL"）
const xcross = wasm.solve_xcross("R U R' F", 'FR', 3);
// => [{moves:["F'","R","U'","R'"], slot:"FR", length:4}, ...]
// 5. 其他
wasm.is_table_loaded(); // => true
wasm.get_table_stats(); // => JS Map（各深度状态数）
wasm.get_table_bytes(); // => Uint8Array（用于 IndexedDB 缓存）
```
### IndexedDB 缓存辅助函数（真实现）
```javascript
function openDB() {
return new Promise((res, rej) => {
const req = indexedDB.open('cube_solver', 1);
req.onupgradeneeded = () => req.result.createObjectStore('kv');
req.onsuccess = () => res(req.result);
req.onerror = () => rej(req.error);
});
}
async function idbGet(key) {
const db = await openDB();
return new Promise((res, rej) => {
const req = db.transaction('kv').objectStore('kv').get(key);
req.onsuccess = () => res(req.result);
req.onerror = () => rej(req.error);
});
}
async function idbSet(key, val) {
const db = await openDB();
return new Promise((res, rej) => {
const tx = db.transaction('kv', 'readwrite');
tx.objectStore('kv').put(val, key);
tx.oncomplete = () => res();
tx.onerror = () => rej(tx.error);
});
}
```
### 典型 IndexedDB 缓存流程
```javascript
let bytes = await idbGet('cross_table'); // 1. 读缓存
if (!bytes) {
wasm.generate_table(8); // 2. 生成
bytes = wasm.get_table_bytes(); // 3. 导出
await idbSet('cross_table', bytes); // 4. 存缓存
} else {
wasm.load_table_from_bytes(bytes); // 5. 秒加载
}
```
### 完整示例 1：单文件 HTML（浏览器端）
保存为 `example.html` 放到项目根目录，然后 `python3 -m http.server 8000` 并访问 `http://localhost:8000/example.html`。功能：加载 WASM → 搜索表优先走 IndexedDB 缓存 → 输入打乱 → 同时求解十字与 XCross。
```html
WASM 求解示例
十字 / XCross 求解
加载中...
```
返回值结构：
- `solve_multi` → `string[][]`，如 `[["F'"], ["U","F'"]]`
- `solve_xcross` → `[{moves, slot, length}, ...]`，`slot` 为 `"FR"/"FL"/"BR"/"BL"`
### 完整示例 2：Node.js（命令行端）
保存为 `example.mjs` 放到项目根目录，运行 `node example.mjs`（Node 18+）：
```javascript
import fs from 'node:fs';
import * as wasm from './pkg/cube_cross_solve.js';
// 1. 初始化：Node 中直接读取 wasm 字节传入（default 即 __wbg_init）
await wasm.default(fs.readFileSync('./pkg/cube_cross_solve_bg.wasm'));
// 2. 生成搜索表（生产环境建议落盘缓存，再用 load_table_from_bytes 秒加载）
wasm.generate_table(8);
// 3. 十字求解 → string[][]
console.log('十字:', wasm.solve_multi("R U R' F2 L' B", 3));
// 4. XCross 求解（ALL = 4 槽位自动取最优）→ [{moves, slot, length}, ...]
for (const x of wasm.solve_xcross("R U R' F2 L' B", 'ALL', 3))
console.log(`XCross (${x.length}步, ${x.slot}):`, x.moves.join(' '));
```
> **必须用命名空间导入**（`import * as wasm`）：`init default()` 的返回值是 raw wasm exports，直接在上面调用字符串参数会得到 `[ptr, len]` 原始值；命名导出才是 JS 包装版。
## Python 批量验证脚本
`py/batch_xcross_test.py` 用独立的 3D 贴纸物理模拟（与 Rust 代码零共享逻辑）验证求解结果：
```bash
python3 py/batch_xcross_test.py # 批量验证 20 个随机 20 步打乱
python3 py/batch_xcross_test.py 50 # 验证 50 个
python3 py/batch_xcross_test.py "FR R U R' F" # 手动验证单条（指定槽位）
python3 py/batch_xcross_test.py "R U R' F" # 手动验证单条（自动选槽）
```
验证内容：应用"打乱+解法"后，十字 4 棱白贴纸朝下且侧贴对色，目标槽位角块 3 贴纸 + 棱块 2 贴纸全部对色。失败时打印 6 面贴纸展开图供人工核对。
## XCross 算法设计
### 启发函数（可采纳，保证最优）
```
h(state) = max(十字最短距离, F2L对最短距离)
```
- **十字距离**：复用现有十字搜索表（190,080 状态的最短距离直查）
- **F2L对距离**：预计算 576 状态（角 8×3 × 棱 12×2）的 BFS 距离表，每个槽位一张
- `max` 保证下界性 → IDA* 返回的一定是最短解
### 搜索流程
```
输入打乱 → 提取 SearchState（4棱 + 目标槽位角/棱）
→ 计算 h0 = max(十字距离, F2L距离)
→ for bound in h0..=11:
DFS(bound) + 转置表 + 同面剪枝
找到解即返回（该 bound 内全部解按长度排序）
输出解法（≤11 步，最优）
```
### 剪枝策略
| 剪枝 | 说明 |
|------|------|
| 深度剪枝 | 剩余深度 0 且未解决 → 回溯 |
| 启发剪枝 | `h(state) > 剩余深度` → 回溯（IDA* 核心） |
| 同面剪枝 | 连续同面转动（如 U U2）→ 跳过 |
| 转置表 | 记录 (状态, 剩余深度)，避免重复展开 |
---
## 十字算法设计（原有）
### 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 # 项目配置（wasm-bindgen 0.2.92 钉版说明）
├── Cargo.lock # 依赖锁定
├── build_wasm.bat # WASM 构建脚本（Windows）
├── index.html # Web 可视化界面
├── src/
│ ├── main.rs # CLI 程序入口
│ ├── lib.rs # 库入口 + WASM 导出（含 solve_xcross）
│ ├── pruning_table.rs # 十字/F2L 搜索表
│ ├── xcross_solver.rs # XCross IDA* 求解器（F2L 对距离表 + 搜索）
│ ├── xcross_state.rs # XCross 状态表示
│ ├── f2l_slot.rs # F2L 槽位定义（FR/FL/BR/BL）
│ ├── cross_state.rs # 十字状态
│ ├── cube_state.rs # 完整魔方状态
│ ├── move_def.rs # 转动定义
│ ├── move_effect.rs # 转动对棱角块的影响数据
│ ├── solver.rs # 打乱生成 / 状态解析辅助
│ ├── oll.rs / pll.rs # OLL/PLL 识别与解法
│ └── f2l_pruning_table.rs # F2L 剪枝表
├── pkg/ # WASM 构建产物（wasm-pack 生成）
├── py/
│ └── batch_xcross_test.py # XCross 独立物理验证脚本
├── cross_table.bin # 预计算搜索表（运行后生成）
├── README.md # 本文档
└── CLAUDE.md # Claude Code 指南
```
---
## 扩展方向
1. **完整求解**: 扩展到 OLL、PLL（已有基础模块）
2. **3D 可视化**: 添加魔方 3D 渲染
3. **多线程**: 并行化搜索表生成
4. **移动端**: 优化移动端性能和界面
5. **算法优化**: XCross 扩展到双组 F2L
---
## 参考资料
- [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