rusty_rubik/
pruning.rs

1//! A module for representing and constructing pruning tables.
2//!
3//! At a high level, a pruning tables gives a lower bound on how many
4//! moves are needed to solve a given position of the Rubik's Cube. The intention
5//! is for these tables to be pre-generated before any solving work begins.
6//!
7//! Each table is generated by executing an iterative deepening DFS (IDDFS) starting
8//! from the solved state. For each state, the depth is recorded in a vector
9//! of the appropriate size.
10
11use crate::cube::*;
12use std::io::Write;
13
14/**
15 * A struct holding pruning information for certain subgroups of the
16 * Rubik's Cube.
17 *
18 * Each pruning table provides a lower bound on how many moves are
19 * needed to transform a given state into the solved state within each subgroup.
20 * These tables are obtained from `pruning.rs`.
21 */
22pub struct PruningTables {
23    /// A pruning table representing the subgroup of corner permutation and orientation.
24    pub corners: Vec<u8>,
25    /// A pruning table representing the subgroup of edge orientation.
26    pub eo: Vec<u8>,
27    /// A pruning table representing the subgroup of edge permutation.
28    pub ep: Vec<u8>,
29}
30
31impl PruningTables {
32    /// Reads the default pruning tables from the default
33    /// file names.
34    pub fn default_tables() -> Self {
35        let corners = std::fs::read("corners.pt").unwrap();
36        let edges_o = std::fs::read("edges_o.pt").unwrap();
37        let edges_p = std::fs::read("edges_p.pt").unwrap();
38        PruningTables {
39            corners,
40            eo: edges_o,
41            ep: edges_p,
42        }
43    }
44
45    /// Computes a lower bound on the number of moves needed to
46    /// solve the given state, based on the pruning table values.
47    pub fn compute_h_value(&self, state: &CubeState) -> u8 {
48        let (corners, eo, ep) = get_index_of_state(&state);
49        std::cmp::max(
50            self.corners[corners as usize],
51            std::cmp::max(self.eo[eo as usize], self.ep[ep as usize]),
52        )
53    }
54}
55
56/// A wrapper function around the main logic of IDDFS.
57fn iddfs(
58    starting_state: &CubeState,
59    depth: u8,
60    mut bv: &mut [u8],
61    prop_func: &dyn Fn(&CubeState) -> usize,
62    tag: String,
63) {
64    if depth < 1 {
65        panic!("Depth must be positive");
66    }
67    for d in 1..depth {
68        println!("Building {} pruning table for depth {}...", tag, d);
69        iddfs_search(&starting_state, d, d, &mut bv, 0, &prop_func);
70    }
71}
72
73/// Starts a depth-bounded DFS from the given state.
74fn iddfs_search(
75    state: &CubeState,
76    original_depth: u8,
77    d: u8,
78    mut bv: &mut [u8],
79    allowed_moves: u8,
80    prop_func: &dyn Fn(&CubeState) -> usize,
81) {
82    if d == 0 {
83        // cool, we've hit the desired depth now
84        let index = prop_func(state);
85        if index > 0 && bv[index] == 0 {
86            bv[index] = original_depth;
87        }
88    } else {
89        for m in ALL_MOVES
90            .iter()
91            .filter(|mo| (1 << get_basemove_pos(mo.basemove)) & allowed_moves == 0)
92        {
93            let new_state = state.apply_move_instance(m);
94            let new_allowed_moves = get_allowed_post_moves(allowed_moves, Some(m.basemove));
95            iddfs_search(
96                &new_state,
97                original_depth,
98                d - 1,
99                &mut bv,
100                new_allowed_moves,
101                &prop_func,
102            );
103        }
104    }
105}
106
107fn write_table(table: &[u8], filename: String) {
108    let mut file = std::fs::File::create(filename).expect("Unable to create file.");
109    file.write(table).expect("Unable to write to file.");
110}
111
112/// Generates a pruning table for the corners of a Rubik's Cube.
113pub fn generate_pruning_table_corners(filename: String) -> bool {
114    let solved = CubeState::default();
115    let mut table = vec![0 as u8; 88179840];
116    iddfs(
117        &solved,
118        9,
119        &mut table,
120        &|state: &CubeState| {
121            let (corner, _, _) = get_index_of_state(state);
122            corner as usize
123        },
124        String::from("corners"),
125    );
126    write_table(&*table, filename);
127    true
128}
129
130/// Generates a pruning table for the edge orientation of a Rubik's Cube.
131pub fn generate_pruning_table_eo(filename: String) -> bool {
132    let solved = CubeState::default();
133    let mut table = vec![0 as u8; 2048];
134    iddfs(
135        &solved,
136        8,
137        &mut table,
138        &|state| {
139            let (_, index, _) = get_index_of_state(&state);
140            index as usize
141        },
142        String::from("EO"),
143    );
144    write_table(&*table, filename);
145    true
146}
147
148/// Generates a pruning table for the edge permutation of a Rubik's Cube.
149pub fn generate_pruning_table_ep(filename: String) -> bool {
150    let solved = CubeState::default();
151    let mut table = vec![0 as u8; 479001600];
152    iddfs(
153        &solved,
154        9,
155        &mut table,
156        &|state| {
157            let (_, _, index) = get_index_of_state(&state);
158            index as usize
159        },
160        String::from("EP"),
161    );
162    write_table(&*table, filename);
163    true
164}
rusty_rubik/pruning.rs

rusty_rubik/
pruning.rs
