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 (14997B)


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