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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
## Big change
* Add tests for multiple moves
* Benchmark: add some simple benchmarking functions to nissy.h,
bench.c becomes very short
### More for moves
* define macro to loop over moves e.g. #define FOREACHMOVE(action)
### API goals:
* manipulate move sequences (invert, unniss, cleanup, mirror / transform...)
* solvers (optimal, generic, coordinates)
* print cube (in various formats)
* print ptables (or layout data in such a way that can be printed
easily, e.g. first bytes are null-terminated strig and can be
printed by user)
### Solvers
* Actually do A*, no fixed depth
* Use threading (see below)
* Return strings, newline separated (see nissy_ffi)
* Instead of depth, I need the following parameters:
int minmoves
int maxmoves
a parameter for all solutions / nmax / optimal / -O n
* How to make the above nicer? can it be done with a minimal
amount of parameters (e.g. at most 2)?
### Rename to libnissy
* prefix public functions with libnissy_ or something similar
* move() that takes a string (alg) as input
## Solving
### Generic solver
* tests: solve full cube (max 7-8 moves?)
* more tests: eo and other stuff
* benchmarks
### Coordinates
TODO: specify in the comments that coordinates return 0 if solved
* [done] eo
* co
* ep
* epsep
* cp
* cpsep
* cphtr
What about symcoord?
### More solvers
* 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:
* Slow: basic solver without any table.
* H48: one-bit-per-entry table + fallback, 48 symmetries and so on.
See planner.
* nxopt31: mostly for comparison.
* other nxopt solvers: make generic and take the type as parameter.
* Step solver: take a coordinate function and a moveset as a parameter.
### New method:
* 48 symmetries, cocsep (or chtr, or similar) + epsep + some EO
* 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
### General things
* Trans: don't do full compose, for some trans composing perm is enough.
Split out sumco() as a separate function and refactor, optimize.
* Use multi-move (up to 4/5 moves at once)
* CO is the worst part of moving, transforming and inverting. Try basing
everything on representing the cube without CO and apply it only at the
end to check that it is actually solved.
* see if vcube's method to flip all corners is better
* find a better way for computing the inverse?
* Improve avx2 instructions in general
### Threading
* THREADS build time option for the number of threads. If set to one,
do not include any threading library or code. Try detecting at build
time, or set to a sane default (e.g. 8? 16?) for generic builds.
* pthread or threads.h? I am more familiar with pthread, but threads.h
is standard (from C11, so it requires switching to it from C99).
Does using threads.h help in any way (e.g. building on Windows)?
## Improvements and other things
* add centers (and moves...)
* for CO: move to bits 5 and 6, no need for padding bit
* NISS: Add mask to moves (e.g. U | NISS where NISS = 32 or something);
adapt readmoves and writemoves.
* Consider adding centers and other moves (for avx2: centers in the
same lane as corners, numbered from 9 to 14)
* More I/O:
nissy
ascii art (color = 1 letter)
twizzle binary https://www.experiments.cubing.net/cubing.js/spec/binary/
reid?
## "Front-end"
* Write adapter code for other languages:
python
hare
rust, go
dart ffi, js
java
* add also example code (e.g. an optimal solver) in examples/
## More documentation?
* Add documentation comments inside cube.c?
* Copy this to cube.c
Transformations can be either simple rotations or a rotation composed
with a mirroring. A composed rotation + mirror is obtained by applying
the corresponding rotation to the solved cube mirrored along the M plane.
For example, to apply the transformation RBm (mirrored RB) to a cube C:
1. Apply a mirror along the M plane to the solved cube
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
|
