1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
# TODO-list for version 2.1 (or is it 3.0 at this point?)
## Alg and moveset changes (prerequisite for solve.h)
### moveset.h
* split off from alg.h
### alg.h
* There is a (future) bug in the way the solver checks if a move can
be appended (allowed_next and similar): the last two moves are not enough.
* Example: using QTM we have last 3 moves U U D. Considering only last 2,
U could be appended, but it cannot (cancel to U').
* Solution: the per-moveset bool allowed_next() should take an alg as
parameter. There are going to be basically two versions, one for QTM and
one for HTM (but more may be added).
* Alg should be extended to remember the list of moves on inverse / normal
separately (without looping over moves).
* Maybe another parameter to know if it can assume there has not been
any double switching, i.e. if the last moves are the only ones to
be checked and there is no need to go back further (e.g. if alg is
U (... stuff on inverse ...) D I don't want to have to check back
to the U, but in practice we can often assume this does not happen).
* Then we can remove last and lastinv from dfsdata.
* move also can_niss to alg.h
* the check for the order of the moves (to avoid counting L R and R L as
different) can be made separately. Maybe add a "compare" function for moves,
such that non-commuting moves are not comparable (return -1 0 1).
## Rework solver
* The architecture is the following: solve.h contains a solve() public
function that takes as parameters a set of solver methods (see below)
and a thread manager (basically, multithreaded or single threaded).
It also has a dfs() public function with the same parameters.
* The solve() function, looping over the allowed depths, calls
the dispatcher provided by the thread manager, which takes care of
instantiating the threads. Each thread calls back to dfs(). The
thread manager then takes case of re-assembling the solutions, and
finally returns a list of solutions for the given depth.
* The specifics of how dfs() works are implemented in a specific solver
module.
### solve.h
* Interface: define solve(), dfs() and the types dfsdata, solvermethods and
threadmanager. solve.h is included by specific thread managers and solvers.
* DfsData: remove Cube *, Movable, Step and extra. Add Void * (containing
either cube, indexes or whatnot) and a moveset (extracted from step,
necessary). Maybe cleanup solveoptions too (e.g. threads not necessary).
* solve.h depends only on moves (dependency on step and trans is removed).
* preparation step should be reworked, maybe removed or delegated to the
specific implementations.
* All dfs stuff in the same function. Maybe remove also solvestop.
* Move two-step solve to a different module
### Specific thread managers
* Single thread. Useful in low-resources environments or when solving multiple
scrambles at the same time, or simply when asked to solve with one thread.
* Lazy multithread: threads are as independent as possible and only
merged at the end. Ideal when all solutions of a certain length are requested.
* Eager multithread: current implementation, branches communicate the number
and list of solutions to stop as soon as possible. Good when only one solution
of a certain depth is required.
### Solver methods
* bool move_check_stop(DfsArg *, Move): applies the given move (possibly
recovered from DfsData, but we avoid checking for niss by passing it
directly) and at the same time checks if the branch should be pruned. Not
elegant, but it is much more efficient to do the two things at the same time
(e.g. when moving a fst_cube we can move one "orientation" at the time, check
the pruning table and stop if possible).
* void add_solution(DfsArg *, ThreadManager): add the solution to the list.
Also checks if the solution is valid / acceptable (e.g. EO does not finish
with F' instead of F and such) and cleans it up (rotation, cleanup, unniss).
* void copy(void * src, void * dst): copy the cube-part of dfs_data. To be
called by copy_dfsdata, which remains in solve.h (but merged into dfs).
* void * invert_cube(void *): in preparation for niss.
* bool niss_makes_sense(DfsArg *): maybe can be done generically in solve.h?
## New optimal solver (use fst)
* Implement nxopt31 with fst_cube. Remember that the function
move_check_solved() should do one axis at the time, so that we don't move
everything before checking.
## Simplify steps
* Remove one type of rotation.
* Change steps to choicestep and stepalt to step (or was this already done?).
## Add missing coordinates and steps
* Check the old file for a list. Many are missing.
* Checkers in steps.c should use coordinates.
## Missing and new commands
* gen
* freemem
* twophase
## Easy improvements
* Solve should re-orient the cube if centers are off
* Solve: add options for -I (inverse only) and -L (linear = normal + inverse).
|
