rcuber/solver/min2phase/
solver.rs

1use std::cmp::{max, min};
2
3use super::constants::{
4    MAX_DEPTH2, MAX_PRE_MOVES, MIN_P1LENGTH_PRE, N_COMB, N_MPERM, OPTIMAL_SOLUTION, TRY_INVERSE,
5    TRY_THREE_AXES, USE_CONJ_PRUN,
6};
7use super::cubie::CubieCube;
8use super::tables::{CT, IT, MT, PT, ST};
9use super::utils::UT;
10use super::{arraycube::ArrayCube, coord::CoordCube, utils::Solution};
11use crate::error::Error;
12use crate::facelet::FaceCube;
13use crate::moves::Formula;
14
15/// min2phase Solver.
16/// # Example
17/// ```rust
18/// use rcuber::{facelet::FaceCube, generator::Generator};
19/// use rcuber::solver::min2phase::solver::Solver;
20///
21/// fn main() {
22///     let mut solver = Solver::default();
23///     let s = solver
24///         .solve(
25///             "DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL",
26///             21,
27///             100000,
28///             0,
29///             0x0,
30///         )
31///         .unwrap();
32///     println!("{}", s);
33///     let n = solver.next(500, 0, 0x4).unwrap();
34///     println!("{}", n);
35///     let n = solver.next(500, 0, 0x4).unwrap();
36///     println!("{}", n);
37///     let n = solver.next(1000, 0, 0x4).unwrap();
38///     println!("{}", n);
39/// }
40/// ```
41#[derive(Debug)]
42pub struct Solver {
43    moves: [i32; 31],
44    node_ud: [CoordCube; 21],
45    node_rl: [CoordCube; 21],
46    node_fb: [CoordCube; 21],
47    selfsym: u64,
48    conj_mask: u32,
49    urf_idx: usize,
50    length1: usize,
51    depth1: usize,
52    max_dep2: usize,
53    sol_len: usize,
54    pub solution: Solution,
55    probe: u64,
56    probe_max: u64,
57    probe_min: u64,
58    verbose: usize,
59    valid1: u32,
60    allow_shorter: bool,
61    cc: ArrayCube,
62    urf_cubiecube: [ArrayCube; 6],
63    urf_coordcube: [CoordCube; 6],
64    phase1_cubie: [ArrayCube; 21],
65    pre_move_cubes: [ArrayCube; MAX_PRE_MOVES + 1],
66    pre_moves: [i32; MAX_PRE_MOVES],
67    pre_move_len: usize,
68    max_pre_moves: usize,
69    is_rec: bool,
70}
71
72impl Default for Solver {
73    fn default() -> Self {
74        let node_ud = [CoordCube::default(); 21];
75        let node_rl = [CoordCube::default(); 21];
76        let node_fb = [CoordCube::default(); 21];
77        let phase1_cubie = [ArrayCube::default(); 21];
78
79        let urf_cubiecube = [ArrayCube::default(); 6];
80        let urf_coordcube = [CoordCube::default(); 6];
81
82        let pre_move_cubes = [ArrayCube::default(); MAX_PRE_MOVES + 1];
83        Self {
84            moves: [0; 31],
85            node_ud,
86            node_rl,
87            node_fb,
88            selfsym: 0,
89            conj_mask: 0,
90            urf_idx: 0,
91            length1: 0,
92            depth1: 0,
93            max_dep2: 0,
94            sol_len: 0,
95            solution: Solution::new(),
96            probe: 0,
97            probe_max: 0,
98            probe_min: 0,
99            verbose: 0,
100            valid1: 0,
101            allow_shorter: false,
102            cc: ArrayCube::default(),
103            urf_cubiecube,
104            urf_coordcube,
105            phase1_cubie,
106            pre_move_cubes: pre_move_cubes,
107            pre_moves: [0; MAX_PRE_MOVES],
108            pre_move_len: 0,
109            max_pre_moves: 0,
110            is_rec: false,
111        }
112    }
113}
114
115impl Solver {
116    /// Solve cube to an expected state(goal falcelet).
117    pub fn solve_to(
118        &mut self,
119        facelet: &str,
120        goal: &str,
121        max_depth: usize,
122        probe_max: u64,
123        probe_min: u64,
124        verbose: usize,
125    ) -> Result<Formula, Error> {
126        let fc0 = FaceCube::try_from(facelet)?;
127        let fcg = FaceCube::try_from(goal)?;
128        let cc0 = CubieCube::try_from(&fc0)?;
129        let s = cc0.verify()?;
130        if s != true {
131            return Err(Error::InvalidFaceletString); // no valid facelet cube, gives invalid cubie cube
132        }
133        let ccg = CubieCube::try_from(&fcg)?;
134        let s = ccg.verify()?;
135        if s != true {
136            return Err(Error::InvalidFaceletString); // no valid facelet cube, gives invalid cubie cube
137        }
138        // cc0 * S = ccg  <=> (ccg^-1 * cc0) * S = Id
139        let mut cc = ccg.inverse_cubie_cube();
140        cc.multiply(cc0);
141        self.solve(
142            FaceCube::try_from(&cc).unwrap().to_string().as_str(),
143            max_depth,
144            probe_max,
145            probe_min,
146            verbose,
147        )
148    }
149
150    /// Solve cube to solved state.
151    pub fn solve(
152        &mut self,
153        facelet: &str,
154        max_depth: usize,
155        probe_max: u64,
156        probe_min: u64,
157        verbose: usize,
158    ) -> Result<Formula, Error> {
159        let cubestate = self.feed_with_verify(facelet);
160        if cubestate.is_err() {
161            return Err(Error::InvalidFaceletString);
162        }
163        self.sol_len = max_depth + 1;
164        self.probe = 0;
165        self.probe_max = probe_max;
166        self.probe_min = min(probe_min, probe_max);
167        self.verbose = verbose;
168        self.solution = Solution::new();
169        self.is_rec = false;
170        self.init_search();
171        match (verbose & OPTIMAL_SOLUTION) == 0 {
172            true => self.search(),
173            false => self.search_opt(),
174        }
175    }
176
177    /// feed facelet to self.cc and verify if its a solvable cube.
178    pub fn feed_with_verify(&mut self, facelet: &str) -> Result<bool, Error> {
179        self.cc = ArrayCube::from(facelet);
180        self.cc.verify()
181    }
182
183    fn init_search(&mut self) {
184        self.conj_mask = match TRY_INVERSE {
185            true => 0,
186            false => 0x38,
187        };
188        self.conj_mask |= match TRY_THREE_AXES {
189            true => 0,
190            false => 0x36,
191        };
192        self.selfsym = self.cc.symmetry();
193        self.conj_mask |= match (self.selfsym >> 16 & 0xffff) != 0 {
194            true => 0x12,
195            false => 0,
196        };
197        self.conj_mask |= match (self.selfsym >> 32 & 0xffff) != 0 {
198            true => 0x24,
199            false => 0,
200        };
201        self.conj_mask |= match (self.selfsym >> 48 & 0xffff) != 0 {
202            true => 0x38,
203            false => 0,
204        };
205        self.selfsym &= 0xffffffffffffu64;
206        self.max_pre_moves = match self.conj_mask > 7 {
207            true => 0,
208            false => MAX_PRE_MOVES,
209        };
210        for i in 0..6 {
211            self.urf_cubiecube[i] = self.cc.clone();
212            self.urf_coordcube[i].set_with_prun(self.urf_cubiecube[i], 20);
213            self.cc = self.cc.urf_conjugate();
214            if i % 3 == 2 {
215                self.cc = self.cc.inverse_cube();
216            }
217        }
218    }
219
220    /// Continue search to find more optimal solution.
221    pub fn next(
222        &mut self,
223        probe_max: u64,
224        probe_min: u64,
225        verbose: usize,
226    ) -> Result<Formula, Error> {
227        self.probe = 0;
228        self.probe_max = probe_max;
229        self.probe_min = min(probe_min, probe_max);
230        self.solution = Solution::new();
231        self.is_rec = (self.verbose & OPTIMAL_SOLUTION) == (verbose & OPTIMAL_SOLUTION);
232        self.verbose = verbose;
233        match (verbose & OPTIMAL_SOLUTION) == 0 {
234            true => self.search(),
235            false => self.search_opt(),
236        }
237    }
238
239    fn phase1_pre_moves(&mut self, max1: usize, lm: i32, ac: ArrayCube, ssym: u64) -> u32 {
240        self.pre_move_len = self.max_pre_moves - max1;
241        if (self.is_rec && (self.depth1 == self.length1 - self.pre_move_len))
242            || (!self.is_rec && (self.pre_move_len == 0 || (0x36FB7 >> lm & 1) == 0))
243        {
244            self.depth1 = self.length1 - self.pre_move_len;
245            self.phase1_cubie[0] = ac;
246            self.allow_shorter = self.depth1 == MIN_P1LENGTH_PRE && self.pre_move_len != 0;
247            if self.node_ud[self.depth1 + 1].set_with_prun(ac, self.depth1 as i32)
248                && self.phase1(self.node_ud[self.depth1 + 1], ssym, self.depth1, -1) == 0
249            {
250                return 0;
251            }
252        }
253        if max1 == 0 || self.pre_move_len + MIN_P1LENGTH_PRE >= self.length1 {
254            return 1;
255        }
256        let mut skip_moves = ArrayCube::get_skip_moves(ssym);
257        if max1 == 1 || self.pre_move_len + 1 + MIN_P1LENGTH_PRE >= self.length1 {
258            // last pre move
259            skip_moves |= 0x36FB7; // 11 0110 1111 1011 0111
260        }
261        let lm = lm / 3 * 3;
262        let mut m = 0;
263        while m < 18 {
264            if m == lm || m == lm - 9 || m == lm + 9 {
265                m += 2;
266                m += 1;
267                continue;
268            }
269            if self.is_rec && m != self.pre_moves[self.max_pre_moves - max1]
270                || (skip_moves & 1 << m) != 0
271            {
272                m += 1;
273                continue;
274            }
275            self.pre_move_cubes[max1] = MT.move_cube[m as usize].multiply(&ac);
276            self.pre_moves[self.max_pre_moves - max1] = m;
277            if self.phase1_pre_moves(
278                max1 - 1,
279                m,
280                self.pre_move_cubes[max1],
281                ssym & ST.move_cube_sym[m as usize],
282            ) == 0
283            {
284                return 0;
285            }
286            m += 1;
287        }
288        1
289    }
290
291    fn search(&mut self) -> Result<Formula, Error> {
292        self.length1 = match self.is_rec {
293            true => self.length1,
294            false => 0,
295        };
296        while self.length1 < self.sol_len {
297            self.max_dep2 = min(MAX_DEPTH2, self.sol_len - self.length1 - 1);
298            self.urf_idx = match self.is_rec {
299                true => self.urf_idx,
300                false => 0,
301            };
302            while self.urf_idx < 6 {
303                if (self.conj_mask & 1 << self.urf_idx) != 0 {
304                    self.urf_idx += 1;
305                    continue;
306                }
307                if self.phase1_pre_moves(
308                    self.max_pre_moves,
309                    -30,
310                    self.urf_cubiecube[self.urf_idx],
311                    self.selfsym & 0xffff,
312                ) == 0
313                {
314                    match self.solution.length {
315                        0 => return Err(Error::ProbeLimitExceeded),
316                        _ => {
317                            return Ok(Formula {
318                                moves: self.solution.to_vec(),
319                            })
320                        }
321                    }
322                }
323                self.urf_idx += 1;
324            }
325            self.length1 += 1;
326        }
327        match self.solution.length {
328            0 => return Err(Error::NoSolutionForMaxDepth),
329            _ => {
330                return Ok(Formula {
331                    moves: self.solution.to_vec(),
332                })
333            }
334        }
335    }
336
337    fn search_opt(&mut self) -> Result<Formula, Error> {
338        let mut maxprun1 = 0;
339        let mut maxprun2 = 0;
340        for i in 0..6 {
341            self.urf_coordcube[i].calc_pruning(false);
342            if i < 3 {
343                maxprun1 = max(maxprun1, self.urf_coordcube[i].prun);
344            } else {
345                maxprun2 = max(maxprun2, self.urf_coordcube[i].prun);
346            }
347        }
348        self.urf_idx = match maxprun2 > maxprun1 {
349            true => 3,
350            false => 0,
351        };
352        self.phase1_cubie[0] = self.urf_cubiecube[self.urf_idx];
353        self.length1 = match self.is_rec {
354            true => self.length1,
355            false => 0,
356        };
357        while self.length1 < self.sol_len {
358            let ud = self.urf_coordcube[0 + self.urf_idx];
359            let rl = self.urf_coordcube[1 + self.urf_idx];
360            let fb = self.urf_coordcube[2 + self.urf_idx];
361            if ud.prun <= self.length1 as i32
362                && rl.prun <= self.length1 as i32
363                && fb.prun < self.length1 as i32
364                && self.phase1_opt(ud, rl, fb, self.selfsym, self.length1, -1) == 0
365            {
366                return match self.solution.length == 0 {
367                    true => Err(Error::ProbeLimitExceeded),
368                    false => Ok(Formula {
369                        moves: self.solution.to_vec(),
370                    }),
371                };
372            }
373            self.length1 += 1;
374        }
375        match self.solution.length == 0 {
376            true => Err(Error::NoSolutionForMaxDepth),
377            false => Ok(Formula {
378                moves: self.solution.to_vec(),
379            }),
380        }
381    }
382
383    ///     0: Found or Probe limit exceeded
384    ///     1: at least 1 + maxDep2 moves away, Try next power
385    ///     2: at least 2 + maxDep2 moves away, Try next axis
386    fn init_phase2_pre(&mut self) -> u32 {
387        self.is_rec = false;
388        let _probe = match self.solution.length {
389            0 => self.probe_max,
390            _ => self.probe_min,
391        };
392        if self.probe >= _probe {
393            return 0;
394        }
395        self.probe += 1;
396
397        for i in (self.valid1 as usize)..self.depth1 {
398            self.phase1_cubie[i + 1] =
399                self.phase1_cubie[i].multiply(&MT.move_cube[self.moves[i] as usize]);
400        }
401        self.valid1 = self.depth1 as u32;
402        let mut p2corn = self.phase1_cubie[self.depth1].get_perm_corner_sym();
403        let mut p2csym = p2corn & 0xf;
404        p2corn >>= 4;
405        let mut p2edge = self.phase1_cubie[self.depth1].get_perm_edge_sym();
406        let mut p2esym = p2edge & 0xf;
407        p2edge >>= 4;
408        let mut p2mid = self.phase1_cubie[self.depth1].get_perm_m();
409        let mut edgei = ArrayCube::get_perm_sym_inv(p2edge as usize, p2esym as usize, false);
410        let mut corni = ArrayCube::get_perm_sym_inv(p2corn, p2csym, true);
411        let last_move = match self.depth1 == 0 {
412            true => -1,
413            false => self.moves[self.depth1 - 1],
414        };
415        let last_pre = match self.pre_move_len == 0 {
416            true => -1,
417            false => self.pre_moves[self.pre_move_len - 1],
418        };
419        let mut ret = 0;
420        let p2switch_max = match self.pre_move_len == 0 {
421            true => 1,
422            false => 2,
423        } * match self.depth1 == 0 {
424            true => 1,
425            false => 2,
426        };
427
428        let mut p2switch = 0;
429        let mut p2switch_mask = (1 << p2switch_max) - 1;
430        while p2switch < p2switch_max {
431            if (p2switch_mask >> p2switch & 1) != 0 {
432                p2switch_mask &= !(1 << p2switch);
433                ret = self.init_phase2(p2corn, p2csym, p2edge, p2esym, p2mid, edgei, corni);
434                if ret == 0 || ret > 2 {
435                    break;
436                } else if ret == 2 {
437                    p2switch_mask &= 0x4 << p2switch; // 0->2; 1=>3; 2=>N/A
438                }
439            }
440            if p2switch_mask == 0 {
441                break;
442            }
443            if (p2switch & 1) == 0 && self.depth1 > 0 {
444                let m = UT.std2ud[(last_move / 3 * 3 + 1) as usize];
445                self.moves[self.depth1 - 1] =
446                    (UT.ud2std[m as usize] as usize * 2) as i32 - self.moves[self.depth1 - 1];
447                p2mid = CT.mperm_move[p2mid][m] as usize;
448                p2corn =
449                    CT.cperm_move[p2corn][ST.sym_move_ud[p2csym][m as usize] as usize] as usize;
450                p2csym = MT.sym_mult[(p2corn & 0xf) as usize][p2csym] as usize;
451                p2corn >>= 4;
452                p2edge = CT.eperm_move[p2edge as usize]
453                    [ST.sym_move_ud[p2esym as usize][m as usize] as usize];
454                p2esym = MT.sym_mult[p2edge as usize & 0xf][p2esym as usize] as u16;
455                p2edge >>= 4;
456                corni = ArrayCube::get_perm_sym_inv(p2corn, p2csym, true);
457                edgei = ArrayCube::get_perm_sym_inv(p2edge as usize, p2esym as usize, false);
458            } else if self.pre_move_len > 0 {
459                let m = UT.std2ud[(last_pre / 3 * 3 + 1) as usize];
460                self.pre_moves[self.pre_move_len - 1] =
461                    UT.ud2std[m] as i32 * 2 - self.pre_moves[self.pre_move_len - 1];
462                p2mid =
463                    IT.mperm_inv[CT.mperm_move[IT.mperm_inv[p2mid] as usize][m] as usize] as usize;
464                p2corn = CT.cperm_move[corni as usize >> 4]
465                    [ST.sym_move_ud[corni as usize & 0xf][m] as usize]
466                    as usize;
467                corni =
468                    p2corn as u16 & !0xf | MT.sym_mult[p2corn & 0xf][corni as usize & 0xf] as u16;
469                p2corn =
470                    ArrayCube::get_perm_sym_inv(corni as usize >> 4, corni as usize & 0xf, true)
471                        as usize;
472                p2csym = p2corn & 0xf;
473                p2corn >>= 4;
474                p2edge = CT.eperm_move[edgei as usize >> 4]
475                    [ST.sym_move_ud[edgei as usize & 0xf][m] as usize];
476                edgei =
477                    p2edge & !0xf | MT.sym_mult[p2edge as usize & 0xf][edgei as usize & 0xf] as u16;
478                p2edge =
479                    ArrayCube::get_perm_sym_inv(edgei as usize >> 4, edgei as usize & 0xf, false);
480                p2esym = p2edge & 0xf;
481                p2edge >>= 4;
482            }
483            p2switch += 1;
484        }
485        if self.depth1 > 0 {
486            self.moves[self.depth1 - 1] = last_move;
487        }
488        if self.pre_move_len > 0 {
489            self.pre_moves[self.pre_move_len - 1] = last_pre;
490        }
491        match ret == 0 {
492            true => 0,
493            false => 2,
494        }
495    }
496
497    fn init_phase2(
498        &mut self,
499        p2corn: usize,
500        p2csym: usize,
501        p2edge: u16,
502        p2esym: u16,
503        p2mid: usize,
504        edgei: u16,
505        corni: u16,
506    ) -> u32 {
507        let prun = max(
508            CoordCube::get_pruning(
509                &PT.eperm_ccombp_prun,
510                (edgei as usize >> 4) * N_COMB
511                    + CT.ccombp_conj[IT.perm2_comb_p[corni as usize >> 4] as usize & 0xff]
512                        [MT.sym_mult_inv[edgei as usize & 0xf][corni as usize & 0xf] as usize]
513                        as usize,
514            ),
515            max(
516                CoordCube::get_pruning(
517                    &PT.eperm_ccombp_prun,
518                    p2edge as usize * N_COMB
519                        + CT.ccombp_conj[IT.perm2_comb_p[p2corn as usize] as usize & 0xff]
520                            [MT.sym_mult_inv[p2esym as usize][p2csym as usize] as usize]
521                            as usize,
522                ),
523                CoordCube::get_pruning(
524                    &PT.mcperm_prun,
525                    p2corn * N_MPERM + CT.mperm_conj[p2mid][p2csym] as usize,
526                ),
527            ),
528        );
529        if prun > self.max_dep2 as i32 {
530            return prun as u32 - self.max_dep2 as u32;
531        }
532
533        let mut depth2 = self.max_dep2;
534        while depth2 >= prun as usize {
535            let ret = self.phase2(
536                p2edge,
537                p2esym,
538                p2corn,
539                p2csym,
540                p2mid,
541                depth2,
542                self.depth1,
543                10,
544            );
545            if ret < 0 {
546                break;
547            }
548            depth2 -= ret as usize;
549            self.sol_len = 0;
550            self.solution = Solution::new();
551            self.solution
552                .set_args(self.verbose, self.urf_idx, self.depth1);
553            for i in 0..self.depth1 + depth2 {
554                self.solution.append_sol_move(self.moves[i]);
555            }
556            for i in (0..self.pre_move_len).rev() {
557                self.solution.append_sol_move(self.pre_moves[i]);
558            }
559            self.sol_len = self.solution.length;
560            depth2 -= 1;
561        }
562        if depth2 != self.max_dep2 {
563            //At least one solution has been found.
564            self.max_dep2 = min(MAX_DEPTH2, self.sol_len - self.length1 - 1);
565            return match self.probe >= self.probe_min {
566                true => 0,
567                false => 1,
568            };
569        }
570        1
571    }
572
573    /// 0: Found or Probe limit exceeded
574    /// 1: Try Next Power
575    /// 2: Try Next Axis
576    fn phase1(&mut self, node: CoordCube, ssym: u64, maxl: usize, lm: i32) -> u32 {
577        if node.prun == 0 && maxl < 5 {
578            if self.allow_shorter || maxl == 0 {
579                self.depth1 -= maxl;
580                let ret = self.init_phase2_pre();
581                self.depth1 += maxl;
582                return ret;
583            } else {
584                return 1;
585            }
586        }
587        let skip_moves = ArrayCube::get_skip_moves(ssym);
588        for axis in 0..6 {
589            let axis = axis * 3;
590            if axis == lm || axis == lm - 9 {
591                continue;
592            }
593            for power in 0..3 {
594                let m = axis + power;
595                if self.is_rec && m != self.moves[self.depth1 - maxl]
596                    || skip_moves != 0 && (skip_moves & 1 << m) != 0
597                {
598                    continue;
599                }
600
601                let mut prun = self.node_ud[maxl].do_move_prun(node, m as usize, true);
602                if prun > maxl as i32 {
603                    break;
604                } else if prun == maxl as i32 {
605                    continue;
606                }
607
608                if USE_CONJ_PRUN {
609                    prun = self.node_ud[maxl].do_move_prun_conj(node, m as usize);
610                    if prun > maxl as i32 {
611                        break;
612                    } else if prun == maxl as i32 {
613                        continue;
614                    }
615                }
616                self.moves[self.depth1 - maxl] = m;
617                self.valid1 = min(self.valid1, (self.depth1 - maxl) as u32);
618                let ret = self.phase1(
619                    self.node_ud[maxl],
620                    ssym & ST.move_cube_sym[m as usize],
621                    maxl - 1,
622                    axis,
623                );
624                if ret == 0 {
625                    return 0;
626                } else if ret >= 2 {
627                    break;
628                }
629            }
630        }
631        1
632    }
633
634    fn phase1_opt(
635        &mut self,
636        ud: CoordCube,
637        rl: CoordCube,
638        fb: CoordCube,
639        ssym: u64,
640        maxl: usize,
641        lm: i32,
642    ) -> u32 {
643        if ud.prun == 0 && rl.prun == 0 && fb.prun == 0 && maxl < 5 {
644            self.max_dep2 = maxl;
645            self.depth1 = self.length1 - maxl;
646            return match self.init_phase2_pre() == 0 {
647                true => 0,
648                false => 1,
649            };
650        }
651
652        let skip_moves = ArrayCube::get_skip_moves(ssym);
653        for axis in 0..6 {
654            let axis: usize = axis * 3;
655            if axis == lm as usize || (axis as i32) == lm - 9 {
656                continue;
657            }
658            for power in 0..3 {
659                let mut m = axis + power;
660                if self.is_rec && m != self.moves[self.length1 - maxl] as usize
661                    || skip_moves != 0 && (skip_moves & 1 << m) != 0
662                {
663                    continue;
664                }
665                // UD Axis
666                let prun_ud = max(
667                    self.node_ud[maxl].do_move_prun(ud, m, false),
668                    self.node_ud[maxl].do_move_prun_conj(ud, m),
669                ) as usize;
670                if prun_ud > maxl {
671                    break;
672                } else if prun_ud == maxl {
673                    continue;
674                }
675
676                //RL Axis
677                m = MT.urf_move[2][m] as usize;
678                let prun_rl = max(
679                    self.node_rl[maxl].do_move_prun(rl, m, false),
680                    self.node_rl[maxl].do_move_prun_conj(rl, m),
681                ) as usize;
682                if prun_rl > maxl {
683                    break;
684                } else if prun_rl == maxl {
685                    continue;
686                }
687                //FB Axis
688                m = MT.urf_move[2][m] as usize;
689                let mut prun_fb = max(
690                    self.node_fb[maxl].do_move_prun(fb, m, false),
691                    self.node_fb[maxl].do_move_prun_conj(fb, m),
692                ) as usize;
693                if prun_ud == prun_rl && prun_rl == prun_fb && prun_fb != 0 {
694                    prun_fb += 1;
695                }
696                if prun_fb > maxl {
697                    break;
698                } else if prun_fb == maxl {
699                    continue;
700                }
701                m = MT.urf_move[2][m] as usize;
702
703                self.moves[self.length1 - maxl] = m as i32;
704                self.valid1 = min(self.valid1, (self.length1 - maxl) as u32);
705                if self.phase1_opt(
706                    self.node_ud[maxl],
707                    self.node_rl[maxl],
708                    self.node_fb[maxl],
709                    ssym & ST.move_cube_sym[m],
710                    maxl - 1,
711                    axis as i32,
712                ) == 0
713                {
714                    return 0;
715                }
716            }
717        }
718        1
719    }
720
721    //-1: no solution found
722    // X: solution with X moves shorter than expectation. Hence, the length of the solution is  depth - X
723    fn phase2(
724        &mut self,
725        edge: u16,
726        esym: u16,
727        corn: usize,
728        csym: usize,
729        mid: usize,
730        maxl: usize,
731        depth: usize,
732        lm: usize,
733    ) -> i32 {
734        if edge == 0 && corn == 0 && mid == 0 {
735            return maxl as i32;
736        }
737        let move_mask = UT.ckmv2bit[lm];
738        let mut m: i32 = 0;
739        while m < 10 {
740            if (move_mask >> m & 1) != 0 {
741                m += 0x42 >> m & 3;
742                m += 1;
743                continue;
744            }
745            let midx = CT.mperm_move[mid][m as usize];
746            let mut cornx = CT.cperm_move[corn][ST.sym_move_ud[csym][m as usize] as usize];
747            let csymx = MT.sym_mult[cornx as usize & 0xf][csym];
748            cornx >>= 4;
749            let mut edgex =
750                CT.eperm_move[edge as usize][ST.sym_move_ud[esym as usize][m as usize] as usize];
751            let esymx = MT.sym_mult[edgex as usize & 0xf][esym as usize];
752            edgex >>= 4;
753            let edgei = ArrayCube::get_perm_sym_inv(edgex as usize, esymx as usize, false);
754            let corni = ArrayCube::get_perm_sym_inv(cornx as usize, csymx as usize, true);
755            let mut prun = CoordCube::get_pruning(
756                &PT.eperm_ccombp_prun,
757                (edgei as usize >> 4) * N_COMB
758                    + CT.ccombp_conj[IT.perm2_comb_p[corni as usize >> 4] as usize & 0xff]
759                        [MT.sym_mult_inv[edgei as usize & 0xf][corni as usize & 0xf] as usize]
760                        as usize,
761            );
762            if prun > maxl as i32 + 1 {
763                return maxl as i32 - prun + 1;
764            } else if prun >= maxl as i32 {
765                m += 0x42 >> m & 3 & (maxl as i32 - prun);
766                m += 1;
767                continue;
768            }
769            prun = max(
770                CoordCube::get_pruning(
771                    &PT.mcperm_prun,
772                    cornx as usize * N_MPERM
773                        + CT.mperm_conj[midx as usize][csymx as usize] as usize,
774                ),
775                CoordCube::get_pruning(
776                    &PT.eperm_ccombp_prun,
777                    edgex as usize * N_COMB
778                        + CT.ccombp_conj[IT.perm2_comb_p[cornx as usize] as usize & 0xff]
779                            [MT.sym_mult_inv[esymx as usize][csymx as usize] as usize]
780                            as usize,
781                ),
782            );
783            if prun >= maxl as i32 {
784                m += 0x42 >> m & 3 & (maxl as i32 - prun);
785                m += 1;
786                continue;
787            }
788            let depthx = depth + 1;
789            let maxlx = maxl - 1;
790            let ret = self.phase2(
791                edgex,
792                esymx as u16,
793                cornx as usize,
794                csymx as usize,
795                midx as usize,
796                maxlx,
797                depthx,
798                m as usize,
799            );
800            if ret >= 0 {
801                self.moves[depth] = UT.ud2std[m as usize] as i32;
802                return ret;
803            }
804            if ret < -2 {
805                break;
806            }
807            if ret < -1 {
808                m += 0x42 >> m & 3;
809            }
810            m += 1;
811        }
812        -1
813    }
814}
815
816#[cfg(test)]
817mod tests {
818    use super::Solver;
819    use crate::{facelet::FaceCube, generator::Generator};
820
821    #[test]
822    fn test_solver() {
823        let mut solver = Solver::default();
824        let s = solver
825            .solve(
826                "DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL",
827                21,
828                100000,
829                0,
830                0x4,
831            )
832            .unwrap();
833        println!("{}", s);
834        let n = solver.next(500, 0, 0x4).unwrap();
835        println!("{}", n);
836        let n = solver.next(500, 0, 0x4).unwrap();
837        println!("{}", n);
838        let n = solver.next(1000, 0, 0x4).unwrap();
839        println!("{}", n);
840    }
841
842    #[test]
843    fn test_solve_to() {
844        let gc = Generator::superflip();
845        let mut solver = Solver::default();
846        let s = solver
847            .solve_to(
848                "UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB",
849                FaceCube::try_from(&gc).unwrap().to_string().as_str(),
850                21,
851                100000,
852                10000,
853                0,
854            )
855            .unwrap();
856        println!("{}", s);
857    }
858}
rcuber/solver/min2phase/solver.rs

rcuber/solver/min2phase/
solver.rs
