From d1a5218935ed0007832c85150d5697e1e1d8513e Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Sun, 24 Apr 2022 21:53:07 +0200 Subject: Added solver class, pruning table generating works --- src/solver.cpp | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 src/solver.cpp (limited to 'src/solver.cpp') diff --git a/src/solver.cpp b/src/solver.cpp new file mode 100644 index 0000000..98e8a13 --- /dev/null +++ b/src/solver.cpp @@ -0,0 +1,57 @@ +#include +#include +#include "solver.hpp" + +Solver::Solver(uint32_t pruning_tab_depth) { + pruning_table = kh_init_cube(); + visited_states = kh_init_cube(); + + generate_pruning_table(pruning_tab_depth); +} + +void Solver::generate_pruning_table(uint32_t depth) { + std::cerr << "Generating pruning table...\n"; + cube_t initial, cube, rotated; + rot_cnt_t rot_cnt; + uint16_t rot, cnt; + int ret; + khint_t k; + std::queue q; + + init_cube(&initial); + k = kh_put_cube(pruning_table, initial, &ret); + kh_val(pruning_table, k) = build_rot_cnt(NULL_ROT, 0); + + q.push(initial); + + while(!q.empty()) { + cube = q.front(); + q.pop(); + + // std::cerr << "processing cube:\n"; + // dump_cube_grid(&cube); + + k = kh_get_cube(pruning_table, cube); + rot_cnt = kh_val(pruning_table, k); + cnt = get_cnt(rot_cnt); + // std::cerr << cnt << "\n"; + if (cnt >= depth) + continue; + + for (rot = ROT_R; rot != NULL_ROT; rot++) { + rotated = cube; + perform_rotation(&rotated, (rotations)rot); + + k = kh_get_cube(pruning_table, rotated); + if (k == kh_end(pruning_table)) { + k = kh_put_cube(pruning_table, rotated, &ret); + kh_val(pruning_table, k) = build_rot_cnt(rot, cnt+1); + q.push(rotated); + + // printf("Cube cnt: %d\n", cnt+1); + // dump_cube_grid(&rotated); + } + } + } + std::cerr << "Generated\n"; +} -- cgit v1.2.3