h48

A prototype for an optimal Rubik's cube solver, work in progress.
git clone https://git.tronto.net/h48
Download | Log | Files | Refs | README | LICENSE

nissy.h (12719B)


      1 /*
      2 This is libnissy (temporarily also known as h48), a Rubik's cube library.
      3 
      4 All the functions return 0 or a positive integer in case of success and
      5 a negative integer in case of error, unless otherwise specified. See
      6 below for the list of error codes and their meaning.
      7 
      8 Cubes are passed as strings in the cccccccc=eeeeeeeeeeee=r format,
      9 see the README.md file for more information.
     10 
     11 Accepted moves are any of the following:
     12 U, D, R, L, F, B, Uw, Dw, Rw, Lw, Fw, Bw, M, S, E, x, y, z
     13 optionally followed by a 2, a ' or a 3.
     14 
     15 A transformation must be given in the format
     16     (rotation|mirrored) (2 letters)
     17 for example 'rotation UF' or 'mirrored BL'.
     18 */
     19 
     20 
     21 /* Constants *****************************************************************/
     22 
     23 /* Some constants for size for I/O buffers */
     24 #define NISSY_SIZE_CUBE           24U
     25 #define NISSY_SIZE_TRANSFORMATION 12U
     26 #define NISSY_SIZE_SOLVE_STATS    10U
     27 #define NISSY_SIZE_DATAID         255U
     28 
     29 /* Flags for NISS options */
     30 #define NISSY_NISSFLAG_NORMAL  1U
     31 #define NISSY_NISSFLAG_INVERSE 2U
     32 #define NISSY_NISSFLAG_MIXED   4U
     33 #define NISSY_NISSFLAG_LINEAR \
     34     (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_INVERSE)
     35 #define NISSY_NISSFLAG_ALL \
     36     (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_INVERSE | NISSY_NISSFLAG_MIXED)
     37 
     38 /* The solved cube */
     39 #define NISSY_SOLVED_CUBE "ABCDEFGH=ABCDEFGHIJKL=A"
     40 
     41 /* Error codes ***************************************************************/
     42 
     43 /*
     44 The value NISSY_OK denotes a success. If returned by solve, it means
     45 that no solution has been found.
     46 */
     47 #define NISSY_OK 0LL
     48 
     49 /*
     50 The value NISSY_WARNING_UNSOLVABLE is a warning. It means that the
     51 operation was completed succesfully, but the resulting cube is in an
     52 unsolvable state. This could be intended, for example if the user has
     53 provided an unsolvable cube as input.
     54 */
     55 #define NISSY_WARNING_UNSOLVABLE -1LL
     56 
     57 /*
     58 The value NISSY_ERROR_INVALID_CUBE means that the provided cube is
     59 invalid. It could be written in an unknown format, or be ill-formed.
     60 */
     61 #define NISSY_ERROR_INVALID_CUBE -10LL
     62 
     63 /*
     64 The value NISSY_ERROR_UNSOLVABLE_CUBE means that the provided cube is in
     65 an unsolvable state for the given solver. This could mean either that the
     66 cube is not solvable at all (for example in case it has a single twisted
     67 corner), or that it is not ready for the given step (for example if the
     68 caller wants to solve a DR finish without the cube being in DR state).
     69 */
     70 #define NISSY_ERROR_UNSOLVABLE_CUBE -11LL
     71 
     72 /*
     73 The value NISSY_ERROR_INVALID_MOVES means that the given moves are
     74 invalid.
     75 */
     76 #define NISSY_ERROR_INVALID_MOVES -20LL
     77 
     78 /*
     79 The value NISSY_ERROR_INVALID_TRANS means that the given transformation
     80 is invalid.
     81 */
     82 #define NISSY_ERROR_INVALID_TRANS -30LL
     83 
     84 /*
     85 The value NISSY_ERROR_INVALID_SOLVER means that the given solver is
     86 not known.
     87 */
     88 #define NISSY_ERROR_INVALID_SOLVER -50LL
     89 
     90 /*
     91 The value NISSY_ERROR_NULL_POINTER means that one of the provided pointer
     92 arguments is NULL. For example, it may be returned by solve when called
     93 with a solver that requires some pre-computed data, but the provided
     94 data is NULL.
     95 */
     96 #define NISSY_ERROR_NULL_POINTER -60LL
     97 
     98 /*
     99 The value NISSY_ERROR_BUFFER_SIZE means that one of the buffers provided
    100 is too small. For example, it could be too small to hold the result or
    101 too small to hold the data generated by gendata.
    102 */
    103 #define NISSY_ERROR_BUFFER_SIZE -61LL
    104 
    105 /*
    106 The value NISSY_ERROR_DATA means that the provided data is invalid. For
    107 example, it may be returned by solve when called with incompatible solver
    108 and data arguments.
    109 */
    110 #define NISSY_ERROR_DATA -70LL
    111 
    112 /*
    113 The value NISSY_ERROR_OPTIONS means that one or more of the given options
    114 are invalid. For example, it may be returned by solve when called with
    115 a negative maximum number of solutions.
    116 */
    117 #define NISSY_ERROR_OPTIONS -80LL
    118 
    119 /*
    120 The value NISSY_ERROR_UNKNOWN denotes an unexpected error. It probably
    121 means that there some bug in this library.  If you can, report any error
    122 of this kind to sebastiano@tronto.net. Thanks!
    123 */
    124 #define NISSY_ERROR_UNKNOWN -999LL
    125 
    126 
    127 /* Library functions *********************************************************/
    128 
    129 /*
    130 Compute the inverse of the given cube.
    131 
    132 Parameters:
    133    cube   - The cube to be inverted.
    134    result - The return parameter for the resulting cube.
    135 
    136 Return values:
    137    NISSY_OK                  - The cube was inverted succesfully.
    138    NISSY_WARNING_UNSOLVABLE  - The resulting cube is not solvable. This is
    139                                either because the given cube was not solvable,
    140                                or due to an unknown internal error.
    141    NISSY_ERROR_INVALID_CUBE  - The given cube is invalid.
    142    NISSY_ERROR_UNKNOWN       - An unknown error occurred.
    143 */
    144 long long
    145 nissy_inverse(
    146 	const char cube[static NISSY_SIZE_CUBE],
    147 	char result[static NISSY_SIZE_CUBE]
    148 );
    149 
    150 /*
    151 Apply the given sequence of moves on the given cube.
    152 
    153 Parameters:
    154    cube   - The cube to move.
    155    moves  - The moves to apply to the cube. Must be a NULL-terminated string.
    156    result - The return parameter for the resulting cube.
    157 
    158 Return values:
    159    NISSY_OK                  - The moves were applied succesfully.
    160    NISSY_WARNING_UNSOLVABLE  - The resulting cube is not solvable. This is
    161                                either because the given cube was not solvable,
    162                                or due to an unknown internal error.
    163    NISSY_ERROR_INVALID_CUBE  - The given cube is invalid.
    164    NISSY_ERROR_INVALID_MOVES - The given moves are invalid.
    165    NISSY_ERROR_NULL_POINTER  - The 'moves' argument is NULL.
    166 */
    167 long long
    168 nissy_applymoves(
    169 	const char cube[static NISSY_SIZE_CUBE],
    170 	const char *moves,
    171 	char result[static NISSY_SIZE_CUBE]
    172 );
    173 
    174 /*
    175 Apply the single given transformation to the given cube.
    176 
    177 Parameters:
    178    cube           - The cube to be transformed.
    179    transformation - The transformation in "(rotation|mirrored) __" format.
    180    result         - The return parameter for the resulting cube.
    181 
    182 Return values:
    183    NISSY_OK                  - The transformation was performed succesfully.
    184    NISSY_WARNING_UNSOLVABLE  - The resulting cube is not solvable. This is
    185                                probably due to an unknown internal error.
    186    NISSY_ERROR_INVALID_CUBE  - The given cube is invalid.
    187    NISSY_ERROR_INVALID_TRANS - The given transformation is invalid.
    188 */
    189 long long
    190 nissy_applytrans(
    191 	const char cube[static NISSY_SIZE_CUBE],
    192 	const char transformation[static NISSY_SIZE_TRANSFORMATION],
    193 	char result[static NISSY_SIZE_CUBE]
    194 );
    195 
    196 /*
    197 Get the cube with the given ep, eo, cp and co values. The values must be in the
    198 ranges specified below, but if the option "fix" is given any values outside its
    199 range will be adjusted before using it. The option "fix" also fixes parity and
    200 orientation issues, resulting always in a solvable cube.
    201 
    202 Parameters:
    203    ep      - The edge permutation, 0 <= ep < 479001600 (12!)
    204    eo      - The edge orientation, 0 <= eo < 2047 (2^11)
    205    cp      - The corner permutation, 0 <= cp < 40320 (8!)
    206    co      - The corner orientation, 0 <= co < 2187 (3^7)
    207    orient  - The orientation of the cube, 0 <= orient < 24
    208    options - Other options.
    209    result  - The return parameter for the resulting cube.
    210 
    211 Return values:
    212    NISSY_OK                 - The cube was generated succesfully.
    213    NISSY_WARNING_UNSOLVABLE - The resulting cube is unsolvable.
    214    NISSY_ERROR_OPTIONS      - One or more of the given parameters is invalid.
    215 */
    216 long long
    217 nissy_getcube(
    218 	long long ep,
    219 	long long eo,
    220 	long long cp,
    221 	long long co,
    222 	long long orient,
    223 	const char *options,
    224 	char result[static NISSY_SIZE_CUBE]
    225 );
    226 
    227 /*
    228 Compute the size of the data generated by nissy_gendata when called for
    229 the given solver, and other useful information.
    230 
    231 Parameters:
    232    solver - The name of the solver.
    233    dataid - An identifier for the data computed for the solver. Different
    234             solvers may use equivalent data. This identifier can be used
    235             e.g. as a filename or database key to save and retrieve the
    236             correct data for each solver, without duplication.
    237 
    238 Return values:
    239    NISSY_ERROR_INVALID_SOLVER - The given solver is not known.
    240    NISSY_ERROR_NULL_POINTER   - The 'solver' argument is null.
    241    NISSY_ERROR_UNKNOWN        - An unknown error occurred.
    242    Any value >= 0             - The size of the data, in bytes.
    243 */
    244 long long
    245 nissy_solverinfo(
    246 	const char *solver,
    247 	char dataid[static NISSY_SIZE_DATAID]
    248 );
    249 
    250 /*
    251 Compute the data for the given solver and store it in generated_data.
    252 
    253 Parameters:
    254    solver    - The name of the solver.
    255    data_size - The size of the data buffer. It is advised to use
    256                nissy_solverinfo to check how much memory is needed.
    257    data      - The return parameter for the generated data.
    258                This buffer must have 8-byte alignment.
    259 
    260 Return values:
    261    NISSY_ERROR_INVALID_SOLVER - The given solver is not known.
    262    NISSY_ERROR_NULL_POINTER   - The 'solver' argument is null.
    263    NISSY_ERROR_UNKNOWN        - An error occurred while generating the data.
    264    NISSY_ERROR_DATA           - The data buffer is invalid, for example because
    265                                 it is not 8-byte aligned.
    266    Any value >= 0             - The size of the data, in bytes.
    267 */
    268 long long
    269 nissy_gendata(
    270 	const char *solver,
    271 	unsigned long long data_size,
    272 	unsigned char data[data_size]
    273 );
    274 
    275 /*
    276 Check that the data is a valid data table for a solver.
    277 
    278 Parameters:
    279    data_size - The size of the data buffer.
    280    data      - The data for the solver. Can be computed with gendata.
    281                This buffer must have 8-byte alignment.
    282 
    283 Return values:
    284    NISSY_OK         - The data is valid.
    285    NISSY_ERROR_DATA - The data is invalid.
    286 */
    287 long long
    288 nissy_checkdata(
    289 	unsigned long long data_size,
    290 	const unsigned char data[data_size]
    291 );
    292 
    293 /*
    294 Solve the given cube using the given solver and options.
    295 
    296 Parameters:
    297    cube      - The cube to solver.
    298    solver    - The name of the solver.
    299    nissflag  - The flags for NISS (linear, inverse, mixed, or combinations).
    300    minmoves  - The minimum number of moves for a solution.
    301    maxmoves  - The maximum number of moves for a solution.
    302    maxsols   - The maximum number of solutions.
    303    optimal   - The maximum number of moves above the optimal solution length.
    304    threads   - The number of threads to use. Must be less than or equalt to
    305                the value of the compile-time constant THREADS. If set to 0,
    306                the default value THREADS will be used.
    307    data_size - The size of the data buffer.
    308    data      - The data for the solver. Can be computed with gendata.
    309                This buffer must have 8-byte alignment.
    310    sols_size - The size of the solutions buffer.
    311    sols      - The return parameter for the solutions. The solutions are
    312                separated by a '\n' (newline) and a '\0' (NULL character)
    313                terminates the list.
    314    stats     - An array to store some statistics about the solve.
    315 
    316 Return values:
    317    NISSY_OK                    - Cube solved succesfully.
    318    NISSY_ERROR_INVALID_CUBE    - The given cube is invalid.
    319    NISSY_ERROR_UNSOLVABLE_CUBE - The given cube is valid, but not solvable with
    320                                  the given solver.
    321    NISSY_ERROR_OPTIONS         - One or more of the given options are invalid.
    322    NISSY_ERROR_INVALID_SOLVER  - The given solver is not known.
    323    NISSY_ERROR_NULL_POINTER    - The 'solver' argument is null.
    324    NISSY_ERROR_DATA            - The data buffer is invalid.
    325    Any value >= 0              - The number of solutions found.
    326 */
    327 long long
    328 nissy_solve(
    329 	const char cube[static NISSY_SIZE_CUBE],
    330 	const char *solver, 
    331 	unsigned nissflag,
    332 	unsigned minmoves,
    333 	unsigned maxmoves,
    334 	unsigned maxsolutions,
    335 	unsigned optimal,
    336 	unsigned threads,
    337 	unsigned long long data_size,
    338 	const unsigned char data[data_size],
    339 	unsigned sols_size,
    340 	char sols[sols_size],
    341 	long long stats[static NISSY_SIZE_SOLVE_STATS]
    342 );
    343 
    344 /*
    345 Parameters:
    346    moves  - The moves to be counted.
    347 
    348 Return values:
    349    NISSY_ERROR_INVALID_MOVES - The given moves are invalid.
    350    NISSY_ERROR_NULL_POINTER  - The 'moves' argument is NULL.
    351    Any value >= 0            - The number of moves.
    352 */
    353 long long
    354 nissy_countmoves(
    355 	const char *moves
    356 );
    357 
    358 /*
    359 Set a global logger function used by this library. Setting the logger to NULL
    360 disables logging.
    361 
    362 Parameters:
    363    logger_function - A pointer to a function that takes two parameters:
    364                      * A C string, the string to be printed.
    365                      * Any other data via a void pointer.
    366    user_data       - Any data that will be provided by the logger when
    367                      calling logger_function.
    368 
    369 Return values:
    370    NISSY_OK - Logger set succesfully. No warning or error is going to be given
    371               if the logger is invalid.
    372 */
    373 long long
    374 nissy_setlogger(
    375 	void (*logger_function)(const char *, void *),
    376 	void *user_data
    377 );