1 files changed, 52 insertions, 72 deletions
diff --git a/TODO.txt b/TODO.txt
index 5e2cfd0..f6a0b10 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,82 +1,43 @@
-## Roadmap
+## (find better name) H48 solver, ideas
-See the sections below for details
-* Tests for multisolve
-* More tests for simple solver?
-* Benchmarks?
-* More complex optimal solvers, pruning tables
-* (More) benchmarks
-* Multithreading (build-time option number of threads)
-* Other optimizations
-* Extend cube and moves to include centers
-* NISS
-* Move manipulation utilities
-* Coordinate solvers and other steps
-* More output formats
-* Adapters for other languages (at least python)
-* More documentation (or keep all in cube.h?)
-* Rename to libnissy
-* Release 1.0
-## Small change
-* solve tests: make smaller, split
-## Solving
-### Simple (slow, light) solver
-* Decide on API for solve() (see above)
-* solve generic becomes private, use cube_fast_t instead of cube_t
-* write simple solver based on generic
-* tests: solve full cube (max 7-8 moves?)
-* benchmarks
-### Coordinates
-TODO: specify in the comments that coordinates return 0 if solved
+First compute co + csep. Use csep as a binary number (2^8 instead of 70,
+loose a factor of 3.66 but still fits in a few megabytes or less). Use
+co + csep as an index in a table whose entries have: 6 bits for ttrep,
+12 bits for rep, 4 bits for pruning. Optionally, 4 more bits could be
+used for the base of the pruning table, if we want to have a different
+base for each corner state; but probably not useful.
-* [done] eo
+If the first pruning is enough, or if the base value of the pruning table
-* co
+(see below) is too low, do not compute the full coordinate (which includes
-* ep
+epsep + partial EO, 12 different sizes depending on how many edges).
-* epsep
-* cp
-* cpsep
-* cphtr
-What about symcoord?
+Otherwise, transform edges only using ttrep and compute full coordinate.
+Look up in table. 3 types of table:
+1. 4 bits per entry, full pruning table
+2. 3 bits with base value (let's try, why not)
+3. 2 bits with base value, nxopt style
+4. 1 bit per entry, telling only if more or less than mid value
+Types 2-4 require benchmarks, a lot of them.
-### More solvers
+Inverse probing (no need to compute inverse, compute one at the beginning
+and keep adding premoves); better do first part of pruning for both
+normal and inverse and only then search in the full table.
-* solve_light: first based on solve_generic, then optimize; benchmark
+If inverse probing gives tight bound, reduce branching factor, optionally
-  to see up to what length it works best (7 moves? 10 moves?)
+switch. Here NISS may be useful.
-### Implement the following solvers:
+## Other solvers
-* Slow: basic solver without any table.
+* ptable should contain some extra data at the beginning: an integer (size)
-* H48: one-bit-per-entry table + fallback, 48 symmetries and so on.
+  a checksum some summary info, maybe even in text form
-  See planner.
+* multisolve
-* nxopt31: mostly for comparison.
+* use threads
-* other nxopt solvers: make generic and take the type as parameter.
+* nxopt (various sizes, for comparison; also use base value probing
-* Step solver: take a coordinate function and a moveset as a parameter.
+  and benchmarking)
+* Coordinate solver for replacing nissy backend (specify in the comments
-### New method:
+  that coordinates return 0 if solved)
+* improve light solver with no table; consider using a small, hard-coded
-* 48 symmetries, cocsep (or chtr, or similar) + epsep + some EO
+  table, e.g. H48 corner table?
-* 1 bit per entry + fallback
-* store necessary stuff (e.g. ttrep) all interleaved in the same table
-### Other considerations:
-* Reconsider going corners-first, so there is no need to sumco()
-### Pruning tables
-* ptable should contain some extra data at the beginning:
-  an integer (size)
-  a checksum
-  some summary info, maybe even in text form
 ## Optimizations
@@ -147,3 +108,22 @@ For example, to apply the transformation RBm (mirrored RB) to a cube C:
        2. Rotate the mirrored cube with z' y2
        3. Apply the cube C to the transformed solved cube
        4. Apply the transformations of step 1a and 1b in reverse
+## Roadmap
+* Tests for multisolve
+* More tests for simple solver?
+* Benchmarks?
+* More complex optimal solvers, pruning tables
+* (More) benchmarks
+* Multithreading (build-time option number of threads)
+* Other optimizations
+* Extend cube and moves to include centers
+* NISS
+* Move manipulation utilities
+* Coordinate solvers and other steps
+* More output formats
+* Adapters for other languages (at least python)
+* More documentation (or keep all in cube.h?)
+* Rename to libnissy
+* Release 1.0

diff --git a/TODO.txt b/TODO.txt index 5e2cfd0..f6a0b10 100644 --- a/TODO.txt +++ b/TODO.txt
@@ -1,82 +1,43 @@
1	## Roadmap	1	## (find better name) H48 solver, ideas
2
3	See the sections below for details
4
5	* Tests for multisolve
6	* More tests for simple solver?
7	* Benchmarks?
8	* More complex optimal solvers, pruning tables
9	* (More) benchmarks
10	* Multithreading (build-time option number of threads)
11	* Other optimizations
12	* Extend cube and moves to include centers
13	* NISS
14	* Move manipulation utilities
15	* Coordinate solvers and other steps
16	* More output formats
17	* Adapters for other languages (at least python)
18	* More documentation (or keep all in cube.h?)
19	* Rename to libnissy
20	* Release 1.0
21
22	## Small change
23
24	* solve tests: make smaller, split
25
26	## Solving
27
28	### Simple (slow, light) solver
29
30	* Decide on API for solve() (see above)
31	* solve generic becomes private, use cube_fast_t instead of cube_t
32	* write simple solver based on generic
33	* tests: solve full cube (max 7-8 moves?)
34	* benchmarks
35
36	### Coordinates
37		2
38	TODO: specify in the comments that coordinates return 0 if solved	3	First compute co + csep. Use csep as a binary number (2^8 instead of 70,
		4	loose a factor of 3.66 but still fits in a few megabytes or less). Use
		5	co + csep as an index in a table whose entries have: 6 bits for ttrep,
		6	12 bits for rep, 4 bits for pruning. Optionally, 4 more bits could be
		7	used for the base of the pruning table, if we want to have a different
		8	base for each corner state; but probably not useful.
39		9
40	* [done] eo	10	If the first pruning is enough, or if the base value of the pruning table
41	* co	11	(see below) is too low, do not compute the full coordinate (which includes
42	* ep	12	epsep + partial EO, 12 different sizes depending on how many edges).
43	* epsep
44	* cp
45	* cpsep
46	* cphtr
47		13
48	What about symcoord?	14	Otherwise, transform edges only using ttrep and compute full coordinate.
		15	Look up in table. 3 types of table:
		16	1. 4 bits per entry, full pruning table
		17	2. 3 bits with base value (let's try, why not)
		18	3. 2 bits with base value, nxopt style
		19	4. 1 bit per entry, telling only if more or less than mid value
		20	Types 2-4 require benchmarks, a lot of them.
49		21
50	### More solvers	22	Inverse probing (no need to compute inverse, compute one at the beginning
		23	and keep adding premoves); better do first part of pruning for both
		24	normal and inverse and only then search in the full table.
51		25
52	* solve_light: first based on solve_generic, then optimize; benchmark	26	If inverse probing gives tight bound, reduce branching factor, optionally
53	to see up to what length it works best (7 moves? 10 moves?)	27	switch. Here NISS may be useful.
54		28
55	### Implement the following solvers:	29	## Other solvers
56		30
57	* Slow: basic solver without any table.	31	* ptable should contain some extra data at the beginning: an integer (size)
58	* H48: one-bit-per-entry table + fallback, 48 symmetries and so on.	32	a checksum some summary info, maybe even in text form
59	See planner.	33	* multisolve
60	* nxopt31: mostly for comparison.	34	* use threads
61	* other nxopt solvers: make generic and take the type as parameter.	35	* nxopt (various sizes, for comparison; also use base value probing
62	* Step solver: take a coordinate function and a moveset as a parameter.	36	and benchmarking)
63		37	* Coordinate solver for replacing nissy backend (specify in the comments
64	### New method:	38	that coordinates return 0 if solved)
65		39	* improve light solver with no table; consider using a small, hard-coded
66	* 48 symmetries, cocsep (or chtr, or similar) + epsep + some EO	40	table, e.g. H48 corner table?
67	* 1 bit per entry + fallback
68	* store necessary stuff (e.g. ttrep) all interleaved in the same table
69
70	### Other considerations:
71
72	* Reconsider going corners-first, so there is no need to sumco()
73
74	### Pruning tables
75
76	* ptable should contain some extra data at the beginning:
77	an integer (size)
78	a checksum
79	some summary info, maybe even in text form
80		41
81	## Optimizations	42	## Optimizations
82		43
@@ -147,3 +108,22 @@ For example, to apply the transformation RBm (mirrored RB) to a cube C:
147	2. Rotate the mirrored cube with z' y2	108	2. Rotate the mirrored cube with z' y2
148	3. Apply the cube C to the transformed solved cube	109	3. Apply the cube C to the transformed solved cube
149	4. Apply the transformations of step 1a and 1b in reverse	110	4. Apply the transformations of step 1a and 1b in reverse
		111
		112	## Roadmap
		113
		114	* Tests for multisolve
		115	* More tests for simple solver?
		116	* Benchmarks?
		117	* More complex optimal solvers, pruning tables
		118	* (More) benchmarks
		119	* Multithreading (build-time option number of threads)
		120	* Other optimizations
		121	* Extend cube and moves to include centers
		122	* NISS
		123	* Move manipulation utilities
		124	* Coordinate solvers and other steps
		125	* More output formats
		126	* Adapters for other languages (at least python)
		127	* More documentation (or keep all in cube.h?)
		128	* Rename to libnissy
		129	* Release 1.0