commit 6cf7cd87a90a1314332aace1d25b9c0f230dc227
parent ea0387796a349c91032fbcb10f50c6ad8607b0f6
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 29 Jul 2025 16:57:21 +0200
added drslice coordinate
Diffstat:
15 files changed, 260 insertions(+), 53 deletions(-)
diff --git a/src/core/constants.h b/src/core/constants.h
@@ -360,7 +360,8 @@
MM18_FACE(MOVE_U) | MM18_FACE(MOVE_D) |\
MM_SINGLE(MOVE_R2) | MM_SINGLE(MOVE_L2) |\
MM_SINGLE(MOVE_F2) | MM_SINGLE(MOVE_B2))
-#define MM18_HTR (MM18_ALLMOVES & ~MM18_NOHALFTURNS)
+#define MM18_DR_NOD (MM18_DR & ~MM18_FACE(MOVE_D))
+#define MM18_HTR (MM18_ALLMOVES & ~MM18_NOHALFTURNS)
#define TM_SINGLE(t) (UINT64_C(1) << (uint64_t)(t))
#define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF)
diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
@@ -10,6 +10,8 @@ STATIC void append_coord_name(const coord_t [static 1], char *);
STATIC bool solution_lastqt_cw(const solution_moves_t [static 1]);
STATIC bool coord_can_switch(const coord_t [static 1], const unsigned char *,
size_t, const uint8_t *);
+STATIC bool coord_is_solved(
+ const coord_t [static 1], uint64_t, const unsigned char *);
STATIC uint64_t
coord_coord_generic(
@@ -182,8 +184,11 @@ coord_can_switch(
uint64_t i;
- if (n == 0)
- return true;
+ DBG_ASSERT(n > 0, "Error: cannot check if coordinate solver "
+ "can use NISS after 0 moves");
+
+ if (!coord->allow_niss)
+ return false;
i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data);
if (i == 0)
@@ -195,3 +200,13 @@ coord_can_switch(
i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data);
return i != 0;
}
+
+STATIC bool
+coord_is_solved(
+ const coord_t coord[static 1],
+ uint64_t i,
+ const unsigned char *data
+)
+{
+ return coord->is_solved == NULL ? i == 0 : coord->is_solved(i, data);
+}
diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
@@ -4,6 +4,7 @@
#include "dr.h"
#include "dreo.h"
#include "drfinnoe.h"
+#include "drslice.h"
#include "list.h"
#include "utils.h"
#include "gendata.h"
diff --git a/src/solvers/coord/dr.h b/src/solvers/coord/dr.h
@@ -20,7 +20,8 @@ STATIC coord_t coordinate_dr = {
.gendata = coordinate_dr_gendata,
.max = DREOESEP_CLASSES * POW_3_7,
.trans_mask = TM_UDFIX,
- .moves_mask = MM18_ALLMOVES,
+ .moves_mask_gendata = MM18_ALLMOVES,
+ .moves_mask_solve = MM18_ALLMOVES,
.axistrans = {
[AXIS_UD] = TRANS_UFr,
[AXIS_RL] = TRANS_RFr,
@@ -28,6 +29,8 @@ STATIC coord_t coordinate_dr = {
},
.is_admissible = &solution_lastqt_cw,
.is_solvable = &is_eoco_solvable,
+ .is_solved = NULL,
+ .allow_niss = true,
.pruning_distribution = {
[0] = 1,
[1] = 1,
diff --git a/src/solvers/coord/dreo.h b/src/solvers/coord/dreo.h
@@ -19,7 +19,8 @@ STATIC coord_t coordinate_dreo = {
.gendata = coordinate_dreo_gendata,
.max = DRESEP_CLASSES * POW_3_7,
.trans_mask = TM_UDRLFIX,
- .moves_mask = MM18_EO,
+ .moves_mask_gendata = MM18_EO,
+ .moves_mask_solve = MM18_EO,
.axistrans = {
[AXIS_UD] = TRANS_UFr,
[AXIS_RL] = TRANS_RFr,
@@ -27,6 +28,8 @@ STATIC coord_t coordinate_dreo = {
},
.is_admissible = &solution_lastqt_cw,
.is_solvable = &is_dreo_solvable,
+ .is_solved = NULL,
+ .allow_niss = true,
.pruning_distribution = {
[0] = 1,
[1] = 1,
diff --git a/src/solvers/coord/drfinnoe.h b/src/solvers/coord/drfinnoe.h
@@ -13,12 +13,7 @@ In the worst case, it is a bug to be fixed, but I find it unlikely.
#define CLASSES_CP_16 2768
-STATIC uint64_t coordinate_cp_coord(cube_t);
-STATIC cube_t coordinate_cp_cube(uint64_t);
-STATIC uint64_t coordinate_epud_coord(cube_t);
-STATIC cube_t coordinate_epud_cube(uint64_t);
STATIC cube_t coordinate_drfinnoe_merge(cube_t, cube_t);
-
STATIC uint64_t coordinate_drfinnoe_coord(cube_t, const unsigned char *);
STATIC cube_t coordinate_drfinnoe_cube(uint64_t, const unsigned char *);
STATIC bool coordinate_drfinnoe_isnasty(uint64_t, const unsigned char *);
@@ -34,7 +29,8 @@ STATIC coord_t coordinate_drfinnoe = {
.gendata = coordinate_drfinnoe_gendata,
.max = CLASSES_CP_16 * FACT_8,
.trans_mask = TM_UDFIX,
- .moves_mask = MM18_DR,
+ .moves_mask_gendata = MM18_DR,
+ .moves_mask_solve = MM18_DR,
.axistrans = {
[AXIS_UD] = TRANS_UFr,
[AXIS_RL] = TRANS_RFr,
@@ -42,6 +38,8 @@ STATIC coord_t coordinate_drfinnoe = {
},
.is_admissible = &solution_always_valid,
.is_solvable = &is_drfinnoe_solvable,
+ .is_solved = NULL,
+ .allow_niss = false,
.pruning_distribution = {
[0] = 1,
[1] = 3,
@@ -64,39 +62,15 @@ STATIC coord_t coordinate_drfinnoe = {
.sym = {
.classes = CLASSES_CP_16,
.max = FACT_8,
- .coord = &coordinate_cp_coord,
- .cube = &coordinate_cp_cube,
+ .coord = &coord_cp,
+ .cube = &invcoord_cp,
.max2 = FACT_8,
- .coord2 = &coordinate_epud_coord,
- .cube2 = &coordinate_epud_cube,
+ .coord2 = &coord_epud,
+ .cube2 = &invcoord_epud,
.merge = &coordinate_drfinnoe_merge,
},
};
-STATIC uint64_t
-coordinate_cp_coord(cube_t c)
-{
- return coord_cp(c);
-}
-
-STATIC cube_t
-coordinate_cp_cube(uint64_t i)
-{
- return invcoord_cp(i);
-}
-
-STATIC uint64_t
-coordinate_epud_coord(cube_t c)
-{
- return coord_epud(c);
-}
-
-STATIC cube_t
-coordinate_epud_cube(uint64_t i)
-{
- return invcoord_epud(i);
-}
-
STATIC cube_t
coordinate_drfinnoe_merge(cube_t c1, cube_t c2)
{
diff --git a/src/solvers/coord/drslice.h b/src/solvers/coord/drslice.h
@@ -0,0 +1,113 @@
+/*
+The DRSLICE coordinate is almost identical to DRFINNOE, but it allows for
+the centers of the E layer to be off by a rotation. For this reason we reuse
+much of the code of DRFINNOE. We could make the pruning table 4x smaller
+if we reduced the coordinate by rotations. TODO.
+*/
+
+STATIC cube_t coordinate_drslice_merge(cube_t, cube_t);
+STATIC uint64_t coordinate_drslice_coord(cube_t, const unsigned char *);
+STATIC cube_t coordinate_drslice_cube(uint64_t, const unsigned char *);
+STATIC bool coordinate_drslice_isnasty(uint64_t, const unsigned char *);
+STATIC size_t coordinate_drslice_gendata(unsigned char *);
+STATIC bool is_drslice_solvable(cube_t);
+STATIC bool is_drslice_solved(uint64_t, const unsigned char *);
+
+STATIC coord_t coordinate_drslice = {
+ .name = "DRSLICE",
+ .coord = &coordinate_drslice_coord,
+ .cube = &coordinate_drslice_cube,
+ .isnasty = &coordinate_drslice_isnasty,
+ .gendata = coordinate_drslice_gendata,
+ .max = CLASSES_CP_16 * FACT_8,
+ .trans_mask = TM_UDFIX,
+ .moves_mask_gendata = MM18_DR,
+ .moves_mask_solve = MM18_DR_NOD,
+ .axistrans = {
+ [AXIS_UD] = TRANS_UFr,
+ [AXIS_RL] = TRANS_RFr,
+ [AXIS_FB] = TRANS_FDr,
+ },
+ .is_admissible = &solution_always_valid,
+ .is_solvable = &is_drslice_solvable,
+ .is_solved = &is_drslice_solved,
+ .allow_niss = false,
+ .pruning_distribution = {
+ [0] = 3,
+ [1] = 7,
+ [2] = 18,
+ [3] = 111,
+ [4] = 433,
+ [5] = 1618,
+ [6] = 6718,
+ [7] = 29182,
+ [8] = 119873,
+ [9] = 476999,
+ [10] = 1858350,
+ [11] = 6531166,
+ [12] = 18338522,
+ [13] = 32839235,
+ [14] = 34118824,
+ [15] = 17284701
+ },
+ .pruning_max = 15,
+ .sym = {
+ .classes = CLASSES_CP_16,
+ .max = FACT_8,
+ .coord = &coord_cp,
+ .cube = &invcoord_cp,
+ .max2 = FACT_8,
+ .coord2 = &coord_epud,
+ .cube2 = &invcoord_epud,
+ .merge = &coordinate_drslice_merge,
+ },
+};
+
+STATIC cube_t
+coordinate_drslice_merge(cube_t c1, cube_t c2)
+{
+ cube_t merged;
+
+ merged = c1;
+ copy_edges(&merged, c2);
+
+ return merged;
+}
+
+STATIC uint64_t
+coordinate_drslice_coord(cube_t cube, const unsigned char *data)
+{
+ return coord_coord_generic(&coordinate_drslice, cube, data);
+}
+
+STATIC cube_t
+coordinate_drslice_cube(uint64_t i, const unsigned char *data)
+{
+ return coord_cube_generic(&coordinate_drslice, i, data);
+}
+
+STATIC size_t
+coordinate_drslice_gendata(unsigned char *data)
+{
+ return coord_gendata_generic(&coordinate_drslice, data);
+}
+
+STATIC bool
+coordinate_drslice_isnasty(uint64_t i, const unsigned char *data)
+{
+ return coord_isnasty_generic(&coordinate_drslice, i, data);
+}
+
+STATIC bool
+is_drslice_solvable(cube_t cube) {
+ return coord_eo(cube) == 0 &&
+ coord_eo(transform_edges(cube, TRANS_URr)) == 0 &&
+ coord_co(cube) == 0;
+}
+
+STATIC bool
+is_drslice_solved(uint64_t i, const unsigned char *data)
+{
+ /* Pre-computed coordinates of U D' (= U' D up to trans) and U2 D2 */
+ return i == 0 || i == 109779816 || i == 68468527;
+}
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
@@ -12,7 +12,8 @@ STATIC coord_t coordinate_eo = {
.gendata = coordinate_eo_gendata,
.max = POW_2_11,
.trans_mask = TM_SINGLE(TRANS_UFr),
- .moves_mask = MM18_ALLMOVES,
+ .moves_mask_gendata = MM18_ALLMOVES,
+ .moves_mask_solve = MM18_ALLMOVES,
.axistrans = {
[AXIS_UD] = TRANS_FDr,
[AXIS_RL] = TRANS_URr,
@@ -20,6 +21,8 @@ STATIC coord_t coordinate_eo = {
},
.is_admissible = &solution_lastqt_cw,
.is_solvable = &is_eo_even,
+ .is_solved = NULL,
+ .allow_niss = true,
.pruning_distribution = {
[0] = 1,
[1] = 2,
@@ -37,7 +40,7 @@ STATIC coord_t coordinate_eo = {
STATIC uint64_t
coordinate_eo_coord(cube_t c, const unsigned char *data)
{
- return (uint64_t)coord_eo(c);
+ return coord_eo(c);
}
STATIC cube_t
diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h
@@ -3,6 +3,8 @@ STATIC long long gendata_coord_dispatch(const char *, unsigned long long,
unsigned char *);
STATIC tableinfo_t genptable_coord(
const coord_t [static 1], const unsigned char *, unsigned char *);
+STATIC uint64_t genptable_coord_init_solved(
+ const coord_t [static 1], const unsigned char *, unsigned char *);
STATIC bool switch_to_fromnew(uint64_t, uint64_t, uint64_t);
STATIC uint64_t genptable_coord_fillneighbors(const coord_t [static 1],
const unsigned char *, uint64_t, uint8_t, unsigned char *);
@@ -118,11 +120,10 @@ genptable_coord(
memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
append_coord_name(coord, info.solver);
- nm = popcount_u32(coord->moves_mask);
- i = coord->coord(SOLVED_CUBE, data);
- set_coord_pval(coord, table, i, 0);
- info.distribution[0] = 1;
- for (d = 1, tot = 1; tot < coord->max && d < 15; d++) {
+ tot = info.distribution[0] =
+ genptable_coord_init_solved(coord, data, table);
+ nm = popcount_u32(coord->moves_mask_gendata);
+ for (d = 1; tot < coord->max && d < 15; d++) {
t = 0;
if (switch_to_fromnew(tot, coord->max, nm)) {
for (i = 0; i < coord->max; i++)
@@ -153,6 +154,27 @@ genptable_coord(
return info;
}
+STATIC uint64_t
+genptable_coord_init_solved(
+ const coord_t coord[static 1],
+ const unsigned char *coord_data,
+ unsigned char *table
+)
+{
+ uint64_t i, max_solved, ret;
+
+ max_solved = coord->is_solved == NULL ? 1 : coord->max;
+
+ for (i = 0, ret = 0; i < max_solved; i++) {
+ if (coord_is_solved(coord, i, coord_data)) {
+ set_coord_pval(coord, table, i, 0);
+ ret++;
+ }
+ }
+
+ return ret;
+}
+
STATIC bool
switch_to_fromnew(uint64_t done, uint64_t max, uint64_t nm)
{
@@ -183,7 +205,8 @@ genptable_coord_fillneighbors(
c = coord->cube(i, data);
tot = 0;
for (m = 0; m < NMOVES; m++) {
- if (!((UINT32_C(1) << (uint32_t)m) & coord->moves_mask))
+ if (!((UINT32_C(1) << (uint32_t)m) &
+ coord->moves_mask_gendata))
continue;
moved = move(c, m);
ii = coord->coord(moved, data);
@@ -234,7 +257,8 @@ genptable_coord_fillfromnew(
for (j = 0, found = false; j < nsim && !found; j++) {
c = coord->cube(sim[j], data);
for (m = 0; m < NMOVES; m++) {
- if (!((UINT32_C(1) << (uint32_t)m) & coord->moves_mask))
+ if (!((UINT32_C(1) << (uint32_t)m) &
+ coord->moves_mask_gendata))
continue;
ii = coord->coord(move(c, m), data);
if (get_coord_pval(coord, table, ii) < d) {
diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h
@@ -3,5 +3,6 @@ coord_t *all_coordinates[] = {
&coordinate_dr,
&coordinate_dreo,
&coordinate_drfinnoe,
+ &coordinate_drslice,
NULL
};
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h
@@ -76,6 +76,7 @@ coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1])
if (nn + ni == 0)
return f & (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_MIXED);
+ /* TODO logic here can probably be simplified */
if (arg->lastisnormal)
return (f & NISSY_NISSFLAG_NORMAL) ||
((f & NISSY_NISSFLAG_MIXED) && (ni > 0 || nn <= th));
@@ -98,6 +99,7 @@ coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1])
if (nn + ni == 0)
return f & (NISSY_NISSFLAG_INVERSE | NISSY_NISSFLAG_MIXED);
+ /* TODO logic here can probably be simplified */
if (!arg->lastisnormal)
return (f & NISSY_NISSFLAG_INVERSE) ||
((f & NISSY_NISSFLAG_MIXED) && (nn > 0 || ni < th));
@@ -118,7 +120,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
cube_t backup_cube, backup_inverse;
coord = arg->coord->coord(arg->cube, arg->coord_data);
- if (coord == 0) {
+ if (coord_is_solved(arg->coord, coord, arg->coord_data)) {
if (!coord_solution_admissible(arg))
return 0;
return appendsolution(arg->solution_moves,
@@ -137,7 +139,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
ret = 0;
if (coord_continue_onnormal(arg)) {
l = arg->solution_moves->nmoves;
- mm = arg->coord->moves_mask;
+ mm = arg->coord->moves_mask_solve;
if (l != 0) {
m = arg->solution_moves->moves[l-1];
mm &= allowedmask[movebase(m)];
@@ -166,7 +168,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
if (coord_continue_oninverse(arg)) {
l = arg->solution_moves->npremoves;
- mm = arg->coord->moves_mask;
+ mm = arg->coord->moves_mask_solve;
if (l != 0) {
m = arg->solution_moves->premoves[l-1];
mm &= allowedmask[movebase(m)];
@@ -260,6 +262,7 @@ solve_coord(
int8_t d;
uint8_t t;
int64_t ndepth;
+ uint64_t i;
cube_t c;
const unsigned char *coord_data;
const unsigned char *ptable;
@@ -314,7 +317,8 @@ solve_coord(
.nissflag = nissflag,
};
- if (coord->coord(c, coord_data) == 0) {
+ i = coord->coord(c, coord_data);
+ if (coord_is_solved(coord, i, coord_data)) {
if (minmoves == 0 && !appendsolution(&solution_moves,
&solution_settings, &solution_list))
goto solve_coord_error_buffer;
diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h
@@ -21,13 +21,17 @@ typedef struct {
bool (*isnasty)(uint64_t, const unsigned char *);
size_t (*gendata)(unsigned char *);
uint64_t max;
- uint64_t moves_mask;
+ /* moves_mask_gendata must be invariant under trans_mask */
+ uint64_t moves_mask_gendata;
+ uint64_t moves_mask_solve;
uint64_t trans_mask;
uint8_t axistrans[3];
bool (*is_admissible)(const solution_moves_t[static 1]);
bool (*is_solvable)(cube_t);
+ bool (*is_solved)(uint64_t, const unsigned char *);
uint64_t pruning_distribution[INFO_DISTRIBUTION_LEN];
uint8_t pruning_max;
+ bool allow_niss;
struct {
size_t classes;
uint64_t max;
diff --git a/test/133_coordata_drfinnoe/00_all.in b/test/133_coordata_drfinnoe/00_all.in
diff --git a/test/133_coordata_drfinnoe/00_all.out b/test/133_coordata_drfinnoe/00_all.out
@@ -0,0 +1 @@
+All good
diff --git a/test/133_coordata_drfinnoe/coorddata_drfinnoe.c b/test/133_coordata_drfinnoe/coorddata_drfinnoe.c
@@ -0,0 +1,60 @@
+#include "../test.h"
+
+#define BOUND 100000
+#define TGROUP UINT64_C(4278190335)
+
+cube_t transform(cube_t, uint8_t);
+uint64_t coordinate_drfinnoe_coord(cube_t, const unsigned char *);
+cube_t coordinate_drfinnoe_cube(uint64_t, const unsigned char *);
+size_t coordinate_drfinnoe_gendata(unsigned char *);
+
+void run(void) {
+ bool found;
+ uint64_t t;
+ char str[STRLENMAX];
+ unsigned char *data;
+ size_t size;
+ cube_t cube;
+ oriented_cube_t oc;
+ uint64_t coord, coord2;
+
+ size = coordinate_drfinnoe_gendata(NULL);
+ data = malloc(size);
+ coordinate_drfinnoe_gendata(data);
+
+ for (coord = 0; coord < BOUND; coord++) {
+ cube = coordinate_drfinnoe_cube(coord, data);
+
+ oc = (oriented_cube_t) { .cube = cube, .orientation = 0 };
+ if (!isconsistent(oc)) {
+ printf("Error: invcoord of %" PRId64
+ " is not consistent\n", coord);
+ goto cleanup;
+ }
+
+ for (t = 0, found = false; t < 48; t++) {
+ if (!((UINT64_C(1) << t) & TGROUP))
+ continue;
+
+ coord2 = coordinate_drfinnoe_coord(transform(cube, t), data);
+ if (coord == coord2) {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found) {
+ oc = (oriented_cube_t){.cube = cube, .orientation = 0};
+ printf("Error: invcoord of %" PRId64 " returns %"
+ PRId64 " with cube:\n", coord, coord2);
+ writecube(oc, STRLENMAX, str);
+ printf("%s\n", str);
+ goto cleanup;
+ }
+ }
+
+ printf("All good\n");
+
+cleanup:
+ free(data);
+}
