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


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