nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

commit 374c33d1412f8f3a35dd3eb874dcaef82d60fff4
parent 455c7d9c8185acdd8c8fe74ad4a59a3e0756d75d
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Wed,  8 Feb 2023 23:20:11 +0100

Added notes for solver theory

Diffstat:
MTODO/2.1.md | 65++++++++++++++++++++++++++++++++++++++++++++++++-----------------
MTODO/testing.md | 8++------
2 files changed, 50 insertions(+), 23 deletions(-)

diff --git a/TODO/2.1.md b/TODO/2.1.md @@ -2,26 +2,57 @@ ## Rework solver -### Architecture - -* Nail down the theory first -* One generic solve module that does not depend on anything else, - not even on cube if possible -* The generic file includes the logic for branching and calls functions - provided as parameters to move the cube and check the status etc... -* This includes the logic for single/multithreading (simplify if compiled - with N_THREADS = 1 or whatever this option is going to be) -* The data representing the cube is a void pointer +* 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. +* allowed_moves and cancel_niss are moved to move.h. +* All dfs stuff in the same function. Maybe remove also solvestop. * Move two-step solve to a different module -* Each other solver (solve coord, solve fst, solve multistep) - should go in a separate module -### Other practicalities +### 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 -* remove cube from dfsarg? (i still need to save the scramble somewhere, - but I really only use it in dfs_niss) -* Re-work prepare_step process for solve_generic (nxopt table is special). -* is_valid should also unnis and / or cleanup the alg. +* 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) diff --git a/TODO/testing.md b/TODO/testing.md @@ -2,9 +2,5 @@ ## Write tests -* Pretty much all are missing, except fst. -* Start from bottom (utils.c) - -## Other - -* Move test_coord from coord.c to test folder. +* Write tests for each module. Some of might require refactoring (this is + a good thing!)