# cube-solve

**Repository Path**: andnnl/cube-solve

## Basic Information

- **Project Name**: cube-solve
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-12-10
- **Last Updated**: 2026-01-22

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 基于Kociemba两阶段算法的Rust魔方求解器, Rust

## README

# cube-solve

基于 Kociemba 两阶段算法的 Rust 魔方求解器，从 Java 版本移植而来。

## 功能特性

- ✅ 完整的魔方状态表示（面级别、块级别、坐标级别）
- ✅ 两阶段搜索算法
- ✅ 随机打乱生成
- ✅ 魔方状态验证
- ✅ 交互式求解模式
- ✅ 详细的代码注释和文档

## 安装

```bash
git clone https://gitee.com/andnnl/cube-solve.git
cd cube-solve
cargo build --release
```

## 使用方法

### 运行程序

```bash
cargo run --release
```

程序会自动：
1. 初始化移动表和剪枝表
2. 随机生成并求解 10 个 20 步打乱的魔方
3. 进入交互模式，等待用户输入打乱公式

### 交互模式

支持的移动格式：
- 基础移动：`U`, `R`, `F`, `D`, `L`, `B`
- 逆时针：`U'`, `R'`, `F'`, `D'`, `L'`, `B'`
- 双层转动：`U2`, `R2`, `F2`, `D2`, `L2`, `B2`

示例：
```
请输入打乱公式: R U R' U' R' F R2 U' R' U' R U R' F'
```

输入 `q`、`exit` 或 `quit` 退出程序。

## 作为库使用

```rust
use cube_solve::solve::{init_tables, Search, Tools};

fn main() {
    // 初始化表
    let _ = init_tables();

    // 创建魔方状态
    let cube_str = "UBRLUFFUBLRUFRLLLRDBDRFDBBUDDBUDDLRFBFLDLBFFRFLRUBRDUU";

    // 验证魔方状态
    let verify = Tools::verify(cube_str);
    if verify != 0 {
        println!("魔方状态无效: Error {}", verify);
        return;
    }

    // 求解
    let search = Search::new();
    let solution = search.solution(cube_str, 21, 10, false);
    println!("解法: {}", solution);
}
```

## 设计逻辑

### 核心算法：两阶段搜索算法

本项目实现了基于 Kociemba 的两阶段搜索算法，这是目前最高效的魔方求解算法之一。

#### 算法概述

两阶段算法将魔方求解问题分解为两个子问题：

**Phase 1：恢复子群**
- 目标：将魔方恢复到 G1 = <U, D, R2, L2, F2, B2> 子群
- 条件：
  - 所有角块朝向正确（twist = 0）
  - 所有棱块朝向正确（flip = 0）
  - 中层棱块（FR, FL, BL, BR）在中间层
- 允许的移动：U, D, R, L, F, B（18种基本移动）

**Phase 2：完成还原**
- 目标：在 G1 子群中完成剩余的还原
- 允许的移动：U, D, R2, L2, F2, B2（只有10种移动）
- 剩余问题：排列和奇偶性

#### 搜索策略

使用 IDA*（Iterative Deepening A*）算法：
- 逐步增加搜索深度
- 使用剪枝表进行启发式评估
- 一旦找到解法立即返回

### 三种魔方表示方式

#### 1. FaceCube（面级别表示）

**用途**：输入/输出，人类可读

**数据结构**：
- 54个面块的颜色数组
- 顺序：U1-U9, R1-R9, F1-F9, D1-D9, L1-L9, B1-B9

**示例**：
```
UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB
```

#### 2. CubieCube（块级别表示）

**用途**：魔方状态的数学运算和验证

**数据结构**：
- 角块排列（cp）：8个角块的位置
- 角块朝向（co）：8个角块的扭转状态（0, 1, 2）
- 棱块排列（ep）：12个棱块的位置
- 棱块朝向（eo）：12个棱块的翻转状态（0, 1）

**物理约束**：
1. 每个角块和棱块必须恰好出现一次
2. 角块扭转状态之和必须能被3整除
3. 棱块翻转状态之和必须为偶数
4. 角块和棱块的排列奇偶性必须一致

#### 3. CoordCube（坐标级别表示）

**用途**：高效搜索，快速查找和剪枝

**数据结构**：
- Phase 1 坐标：
  - twist：角块扭转（3^7 = 2187 种状态）
  - flip：棱块翻转（2^11 = 2048 种状态）
  - fr_to_br：中层棱块排列（C(12,4) = 495 种状态）

- Phase 2 坐标：
  - parity：奇偶性（2 种状态）
  - urf_to_dlf：上层角块排列（20160 种状态）
  - ur_to_df：上层棱块排列（20160 种状态）
  - fr_to_br：中层棱块排列（24 种状态）

### 预计算表

#### 移动表（Move Tables）

记录每个坐标在每种移动后的新坐标值：

- `TWIST_MOVE`：角块扭转移动表
- `FLIP_MOVE`：棱块翻转移动表
- `FR_TO_BR_MOVE`：中层棱块排列移动表
- `URF_TO_DLF_MOVE`：上层角块排列移动表
- `UR_TO_DF_MOVE`：上层棱块排列移动表
- `UR_TO_UL_MOVE`：上层棱块排列移动表（UR, UF, UL）
- `UB_TO_DF_MOVE`：上层棱块排列移动表（UB, DR, DF）

#### 剪枝表（Pruning Tables）

记录从每个坐标到目标状态的最小距离：

- `SLICE_TWIST_PRUN`：Phase 1 角块扭转和切片的剪枝表
- `SLICE_FLIP_PRUN`：Phase 1 棱块翻转和切片的剪枝表
- `SLICE_URF_TO_DLF_PARITY_PRUN`：Phase 2 角块和切片的剪枝表
- `SLICE_UR_TO_DF_PARITY_PRUN`：Phase 2 棱块的剪枝表

## 流程图

### 主程序流程

```
开始
  ↓
初始化移动表和剪枝表
  ↓
随机生成10个20步打乱魔方
  ↓
┌─────────────────────┐
│  对每个魔方：        │
│  1. 生成打乱公式     │
│  2. 验证魔方状态     │
│  3. 求解魔方         │
│  4. 输出解法和耗时    │
└─────────────────────┘
  ↓
进入交互模式
  ↓
┌─────────────────────┐
│  等待用户输入：       │
│  - 打乱公式 → 求解   │
│  - q/exit/quit → 退出 │
└─────────────────────┘
  ↓
结束
```

### 两阶段搜索流程

```
输入魔方状态
  ↓
转换为 CoordCube
  ↓
┌─────────────────────┐
│     Phase 1         │
│  恢复子群 G1        │
│  - twist = 0        │
│  - flip = 0         │
│  - 中层棱块在中间层  │
└─────────────────────┘
  ↓
┌─────────────────────┐
│     Phase 2         │
│  完成还原           │
│  - 只允许 G1 移动    │
└─────────────────────┘
  ↓
输出解法
```

### 求解算法流程

```
开始求解
  ↓
验证魔方状态
  ↓
转换为 CubieCube
  ↓
转换为 CoordCube
  ↓
┌─────────────────────┐
│  Phase 1 搜索：      │
│  1. 初始化深度 d=1   │
│  2. IDA* 搜索       │
│  3. 使用剪枝表       │
│  4. 找到 G1 状态     │
└─────────────────────┘
  ↓
┌─────────────────────┐
│  Phase 2 搜索：      │
│  1. 从 G1 状态开始   │
│  2. IDA* 搜索       │
│  3. 只允许 G1 移动   │
│  4. 找到还原状态     │
└─────────────────────┘
  ↓
合并 Phase 1 和 Phase 2
  ↓
输出完整解法
```

## 设计图

### 魔方面块编号

```
         U1 U2 U3
         U4 U5 U6
         U7 U8 U9
L1 L2 L3 F1 F2 F3 R1 R2 R3 B1 B2 B3
L4 L5 L6 F4 F5 F6 R4 R5 R6 B4 B5 B6
L7 L8 L9 F7 F8 F9 R7 R8 R9 B7 B8 B9
         D1 D2 D3
         D4 D5 D6
         D7 D8 D9
```

### 角块位置

```
        URF-------UBR
       /|         /|
      / |        / |
     UFL-URF-----UBR-UBR
     |  |       |  |
     |  DFL-----|  DRB
     | /        | /
     |/         |/
     DLF-------DRB
```

角块列表：
- URF (Up-Right-Front)
- UFL (Up-Front-Left)
- ULB (Up-Left-Back)
- UBR (Up-Back-Right)
- DFR (Down-Front-Right)
- DLF (Down-Left-Front)
- DBL (Down-Back-Left)
- DRB (Down-Right-Back)

### 棱块位置

```
        UB
       /  \
      UR  UL
     /      \
    UF       UB
    |        |
    FR       FL
    |        |
    DF       DB
     \      /
      DR  DL
       \  /
        DB
```

棱块列表：
- UR (Up-Right)
- UF (Up-Front)
- UL (Up-Left)
- UB (Up-Back)
- DR (Down-Right)
- DF (Down-Front)
- DL (Down-Left)
- DB (Down-Back)
- FR (Front-Right)
- FL (Front-Left)
- BL (Back-Left)
- BR (Back-Right)

### 模块依赖关系

```
main.rs
  ↓
lib.rs
  ↓
solve/mod.rs
  ↓
┌─────────┬─────────┬─────────┬─────────┐
│color.rs │edge.rs  │corner.rs│facelet.rs│
└─────────┴─────────┴─────────┴─────────┘
  ↓           ↓           ↓           ↓
┌───────────────────────────────────────┐
│          face_cube.rs                 │
└───────────────────────────────────────┘
  ↓
┌───────────────────────────────────────┐
│          cubie_cube.rs                │
└───────────────────────────────────────┘
  ↓
┌───────────────────────────────────────┐
│          coord_cube.rs                │
└───────────────────────────────────────┘
  ↓
┌───────────────────────────────────────┐
│          search.rs                    │
└───────────────────────────────────────┘
  ↓
┌───────────────────────────────────────┐
│          tools.rs                     │
└───────────────────────────────────────┘
```

## 项目结构

```
src/
├── main.rs          # 主程序入口
├── lib.rs           # 库入口
└── solve/           # 求解算法模块
    ├── mod.rs       # 模块导出
    ├── color.rs     # 颜色枚举
    ├── edge.rs      # 边块枚举
    ├── corner.rs    # 角块枚举
    ├── facelet.rs   # 面块枚举
    ├── cubie_cube.rs    # 块级别表示
    ├── coord_cube.rs    # 坐标级别表示
    ├── search.rs        # 搜索算法
    ├── tools.rs         # 工具函数
    └── face_cube.rs     # 面级别表示
```

## 构建和测试

```bash
# 构建
cargo build

# 发布版本（优化）
cargo build --release

# 运行测试
cargo test

# 格式化代码
cargo fmt

# 代码检查
cargo clippy
```

## 技术细节

### 算法

- **两阶段算法**：基于 Kociemba 算法的改进版本
- **IDA* 搜索**：迭代加深 A* 算法
- **剪枝表**：预计算的距离表，用于快速剪枝

### 性能

- 初始化时间：几十毫秒（优化后）
- 平均求解时间：< 100ms（取决于打乱复杂度）
- 平均步数：~20 步（接近最优）
- 最坏情况：21 步

## 依赖

- `rand` - 随机数生成
- `once_cell` - 懒初始化

## 开发状态

✅ Java 到 Rust 移植已完成
- 所有 Java `solve` 包中的类都已移植到 Rust
- 基础数据结构完整实现
- 算法框架搭建完成
- 测试用例通过
- 代码注释完善

## 参考实现

本项目参考了 [magicube-solve-algorithm](./magicube-solve-algorithm/) 中的 Java 实现。

## 许可证

MIT License

## 贡献

欢迎提交 Issue 和 Pull Request！