cubesim 0.0.7

Rubik's Cube simulation and solving library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

use lazy_static::lazy_static;

use crate::generic_cube::{Cube, Face, Move, MoveVariant, CubeSize, all_moves};
use crate::generic_cube::{sticker_index as S};
use crate::facelet_cube::FaceletCube;
use crate::generic_solver::{Solver, PruningTable, ida_star};

/// Solves a 3x3x3 Cube using the Thistlethwaite Algorithm.
/// 
/// This is the basic 4 phase solver as described on [Jaap's Puzzle Page].
/// The solutions generated are NOT optimal and will take on average 60 moves.
/// While this function will work on a ``GeoCube``, it is highly recommended to
/// use a ``FaceletCube`` for optimal performance.
/// 
/// [Jaap's Puzzle Page]: https://www.jaapsch.net/puzzles/thistle.htm
/// 
/// # Examples
/// 
/// Solve the superflip position:
/// 
/// ```rust
/// use cubesim::prelude::{Cube};
/// use cubesim::FaceletCube;
/// use cubesim::parse_scramble;
/// use cubesim::solve;
/// 
/// let cube = FaceletCube::new(3).apply_moves(
///     &parse_scramble(String::from("U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2"))
///  );
//// assert!(cube.apply_moves(&solve(&cube).unwrap()).is_solved());
/// ```
pub fn solve(cube: &impl Cube) -> Option<Vec<Move>> {
    let mut solution = vec![];
    let mut cube = cube.clone();

    for phase in [phase1, phase2, phase3, phase4] {
        let mut phase_solution = phase(&cube)?;
        cube = cube.apply_moves(&phase_solution);
        solution.append(&mut phase_solution);
    }

    Some(solution)
}

pub fn phase1(cube: &impl Cube) -> Option<Vec<Move>> {
    use Face::*;

    lazy_static! {
        static ref MASK: Box<dyn Fn(CubeSize, Face) -> Face + Sync> = {
            let g1_mask = [
                S(3, U, 2), S(3, U, 4), S(3, U, 6), S(3, U, 8),
                S(3, D, 2), S(3, D, 4), S(3, D, 6), S(3, D, 8),
                S(3, F, 4), S(3, F, 6), S(3, B, 4), S(3, B, 6)
            ];

            Box::new(move |i: CubeSize, _| if g1_mask.contains(&i) { U } else { X })
        };

        static ref MOVES: Vec<Move> = all_moves(3);

        static ref PRUNING_TABLE: PruningTable = {
            let pruning_depth = 7;
            PruningTable::new(&[FaceletCube::new(3).mask(&*MASK)], pruning_depth, &MOVES)
        };

        static ref SOLVER: Solver = Solver::new(all_moves(3), (*PRUNING_TABLE).clone());
    }

    ida_star(&cube.mask(&*MASK), &*SOLVER, 10)
}

pub fn phase2(cube: &impl Cube) -> Option<Vec<Move>> {
    use Face::*;
    use MoveVariant::*;

    lazy_static! {
        static ref MASK: Box<dyn Fn(CubeSize, Face) -> Face + Sync> = {
            let co_pieces = [
                S(3, U, 1), S(3, U, 3), S(3, U, 7), S(3, U, 9),
                S(3, D, 1), S(3, D, 3), S(3, D, 7), S(3, D, 9)
            ];
        
            let eo_ud_pieces = [
                S(3, U, 2), S(3, U, 4), S(3, U, 6), S(3, U, 8),
                S(3, D, 2), S(3, D, 4), S(3, D, 6), S(3, D, 8)
            ];
        
            let eo_e_pieces = [
                S(3, F, 4), S(3, F, 6), S(3, B, 4), S(3, B, 6)
            ];
        
            Box::new(move |i: CubeSize, _| 
                if eo_ud_pieces.contains(&i) || co_pieces.contains(&i) { X } 
                else if eo_e_pieces.contains(&i) { U } 
                else { R }
            )
        };

        static ref MOVES: Vec<Move> = vec![
            Move::U(Standard), Move::U(Inverse), Move::U(Double), 
            Move::D(Standard), Move::D(Inverse), Move::D(Double),  
            Move::L(Standard), Move::L(Inverse), Move::L(Double), 
            Move::R(Standard), Move::R(Inverse), Move::R(Double),  
            Move::F(Double), Move::B(Double) 
        ];

        static ref PRUNING_TABLE: PruningTable = {
            let pruning_depth = 5;
            PruningTable::new(&[FaceletCube::new(3).mask(&*MASK)], pruning_depth, &*MOVES)
        };

        static ref SOLVER: Solver = Solver::new((*MOVES).clone(), (*PRUNING_TABLE).clone());
    }

    ida_star(&cube.mask(&*MASK), &*SOLVER, 10)
}

pub fn phase3(cube: &impl Cube) -> Option<Vec<Move>>  {
    use Face::*;
    use MoveVariant::*;

    lazy_static! {
        static ref MASK: Box<dyn Fn(CubeSize, Face) -> Face + Sync> = {
            let cp_pieces = [U, D, F, B, L, R].iter()
                .map(|f| [1, 3, 7, 9].map(|x| S(3, *f, x)))
                .collect::<Vec<_>>()
                .concat();

            let ep_pieces = [F, B, L, R].iter()
                .map(|f| [2, 4, 6, 8].map(|x| S(3, *f, x)))
                .collect::<Vec<_>>()
                .concat();

            let face = |f| if f == B { F }
                           else if f == L { R }
                           else { f };

            Box::new(move |i: CubeSize, _| 
                if cp_pieces.contains(&i) { [U, R, F, D, L, B][(i / 9) as usize] }
                else if ep_pieces.contains(&i) { face([U, R, F, D, L, B][(i / 9) as usize]) }
                else { X }
            )
        };

        static ref G2_SOLVED_STATES: PruningTable = PruningTable::new(
            &[FaceletCube::new(3).mask(&*MASK)], 
            10,
            &vec![Move::U(Double), Move::D(Double), Move::F(Double), Move::B(Double), Move::L(Double), Move::R(Double)]
        );

        static ref MOVES: Vec<Move> = vec![
            Move::U(Standard), Move::U(Inverse), Move::U(Double),
            Move::D(Standard), Move::D(Inverse), Move::D(Double),
            Move::F(Double), Move::B(Double), Move::L(Double), Move::R(Double)
        ];

        static ref PRUNING_TABLE: PruningTable = {
            let pruning_depth = 5;
            PruningTable::from_existing_table(&G2_SOLVED_STATES, pruning_depth, &*MOVES)
        };

        static ref SOLVER: Solver = Solver::new((*MOVES).clone(), (*PRUNING_TABLE).clone());
    }

    ida_star(&cube.mask(&*MASK), &*SOLVER, 13)
}

pub fn phase4(cube: &impl Cube) -> Option<Vec<Move>> {
    use MoveVariant::*;

    let moves = vec![
        Move::U(Double), Move::D(Double), Move::F(Double),
        Move::B(Double), Move::L(Double), Move::R(Double)
    ];
    let search_limit = 14;
    let pruning_depth = 6;
    let pruning_table = PruningTable::new(&[FaceletCube::new(3)], pruning_depth, &moves);

    let solver = Solver::new(moves, pruning_table);

    ida_star(cube, &solver, search_limit)
}