commit 5bdf6e73179cf944ce82606545beb0b0d63a59a3
parent e2004826a56b1e2cac8b3d5a94535e480ca2855d
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 8 Nov 2023 18:53:00 +0100
Improved comments
Diffstat:
| M | TODO.txt | | | 25 | +++++++------------------ |
| M | cube.c | | | 59 | +++++++++++++++++++++++++++++++++++++++++++++++++---------- |
| M | cube.h | | | 43 | +++++++++++++++++++++++++++++++++++++++---- |
3 files changed, 95 insertions(+), 32 deletions(-)
diff --git a/TODO.txt b/TODO.txt
@@ -1,11 +1,12 @@
-## Generic solver
+## Solving
+
+### Generic solver
-* finish implementation
* tests: solve full cube (max 7-8 moves?)
* more tests: eo and other stuff
* benchmarks
-## Coordinates
+### Coordinates
* [done] eo
* co
@@ -17,22 +18,10 @@
What about symcoord?
-## More I/O
-
-
-## Solving
+### More solvers
-All solving functions take a cube and some parameters as input.
-
-* Depth [uint, <= 20]: all solvers work at fixed depth. The caller
- implementation can implement an A* search.
-* max [int]: the maximum number of solutions to find. Set to a negative
- value for all solutions.
-* sol [move_t *]: the array for returning the solutions. The caller
- should make sure that it can hold at least max * depth values.
-* Table [uint8_t *]: table with all the necessare pre-computed info.
- The table can be generated with a companion function, but reading
- from and writing to file is delegated to the caller implementation.
+* solve_light: first based on solve_generic, then optimize; benchmark
+ to see up to what length it works best (7 moves? 10 moves?)
### Implement the following solvers:
diff --git a/cube.c b/cube.c
@@ -3688,19 +3688,51 @@ implementation of all the solving algorithms.
typedef struct {
cube_t cube;
- int (*estimate)(cube_t);
uint8_t depth;
int maxsols;
move_t *sols;
int nsols;
int nmoves;
move_t moves[20];
+ int (*estimate)(cube_t);
} dfs_arg_t;
-int
+static bool
+allowednextmove(dfs_arg_t arg, move_t m)
+{
+ int n;
+ move_t mbase, l1base, l2base, maxis, l1axis, l2axis;
+
+ n = arg.nmoves;
+
+ if (n == 0)
+ return true;
+
+ mbase = m / 3;
+ maxis = mbase / 2;
+ l1base = arg.moves[n-1] / 3;
+ l1axis = l1base / 2;
+
+ if (mbase == l1base || (maxis == l1axis && mbase < l1base))
+ return false;
+
+ if (n == 1)
+ return true;
+
+ l2base = arg.moves[n-2] / 3;
+ l2axis = l1base / 2;
+
+ return l1axis != l2axis || mbase != l2base;
+}
+
+static int
solve_generic_dfs(dfs_arg_t arg)
{
- int bound = arg.estimate(arg.cube);
+ dfs_arg_t nextarg;
+ int bound, ret;
+ move_t m;
+
+ bound = arg.estimate(arg.cube);
if (arg.nsols == arg.maxsols || bound + arg.nmoves > arg.depth)
return 0;
@@ -3714,36 +3746,43 @@ solve_generic_dfs(dfs_arg_t arg)
return 1;
}
- /* TODO: loop over moves and recur */
- return 0;
+ memcpy(&nextarg, &arg, sizeof(dfs_arg_t));
+ nextarg.nmoves = arg.nmoves + 1;
+ for (m = 0, ret = 0; m < 18; m++) {
+ if (allowednextmove(arg, m)) {
+ nextarg.cube = move(arg.cube, m);
+ nextarg.moves[arg.nmoves] = m;
+ ret += solve_generic_dfs(nextarg);
+ }
+ }
+
+ return ret;
}
int
solve_generic(
cube_t cube,
- int (*estimate)(cube_t),
uint8_t depth,
int maxsols,
move_t *sols
+ int (*estimate)(cube_t),
)
{
dfs_arg_t arg;
- if (!issolvable(cube) || depth > 20)
+ if (!issolvable(cube) || depth > 20 || estimate == NULL)
return -1;
arg = (dfs_arg_t) {
.cube = cube,
- .estimate = estimate,
.depth = depth,
.maxsols = maxsols,
.sols = sols,
.nsols = 0,
.nmoves = 0,
.moves = {0}
+ .estimate = estimate,
};
return solve_generic_dfs(arg);
-
- return 0;
}
diff --git a/cube.h b/cube.h
@@ -169,9 +169,44 @@ int16_t coord_eo(cube_t); /* Edge orientation */
/******************************************************************************
Solvers
-Solvers return -1 in case of error, the number of solutions otherwise
-
-TODO
+All solvers work at fixed depth, i.e. they will only find solutions of the
+specified length. Iterating over the possible lengths, if desired, is left as
+an implementation detail for the user of this library.
+
+The solutions are returned as a list of moves, which can then be converted to
+a string using writemoves().
+
+Unless specified otherwise, all the solutions are not trivially simplifiable.
+This means that sequences like U U2 or R L R will not appear in any solution.
+Moreover, two consecutive parallel moves are always going to be sorted in
+increasing order. For example, L R2 may never appear in a solution, but R2 L
+could.
+
+Solvers return -1 in case of error, the number of solutions found otherwise.
+
+TODO NISS / INVERSE / LINEAR as a mask?
+
+All solvers take at least the following parameters, satisfying the conditions
+in square brackets:
+ - cube_t cube [issolvable(cube)]: The cube to solve.
+ - uint8_t depth [depth <= 20]: The lenght of the solution.
+ - int maxsols: The maximum number of solutions to find. The solver
+ stops when the limit is reached. If set to a negative number, all
+ the solutions are found.
+ - move_t *ret: The array where the moves of the solutions are stored.
+ There is no separator between different solutions; to read the
+ solutions, use the fact that all solutions has the same length: the
+ i-th move of the j-th solution is ret[j*depth + i].
+
+Some solvers take other parameters. See below for details.
******************************************************************************/
-int solve_generic(cube_t, int (*)(cube_t), uint8_t, int, move_t *);
+int solve_generic(
+ cube_t cube,
+ uint8_t depth,
+ int maxsols,
+ move_t *ret
+ int (*estimate)(cube_t),
+);
+
+int solve_light(cube_t, int
