Added API function for solution variations

25 files changed, 586 insertions, 36 deletions

diff --git a/.dockerignore b/.dockerignore
deleted file mode 120000
index 3e4e48b..0000000
--- a/.dockerignore
+++ /dev/null
@@ -1 +0,0 @@
-.gitignore
\ No newline at end of file
diff --git a/cpp/examples/variations.cpp b/cpp/examples/variations.cpp
new file mode 100644
index 0000000..3c6421d
--- /dev/null
+++ b/cpp/examples/variations.cpp
@@ -0,0 +1,15 @@
+/* A simple example showing how to move a cube and print it in H48 format. */
+
+#include "../nissy.h"
+#include <iostream>
+
+int main() {
+        std::string moves = "R U' Bw2 M D' x' F B(E2 F D B' Lw2 U2 U' S2 B)";
+        auto v = std::get<nissy::variation>(nissy::variation::get("lastqt"));
+        auto variations = v.find_variations(moves).solutions;
+
+        std::cout << "Changing the last quarter turn of " << moves << " gives:"
+            << std::endl << variations;
+
+        return 0;
+}
diff --git a/cpp/nissy.cpp b/cpp/nissy.cpp
index 90fcf20..6ca4884 100644
--- a/cpp/nissy.cpp
+++ b/cpp/nissy.cpp
@@ -12,6 +12,7 @@ extern "C" {
         long long nissy_inverse(const char *, char *);
         long long nissy_applymoves(const char *, const char *, char *);
         long long nissy_applytrans(const char *, const char *, char *);
+        long long nissy_variations(const char *, const char *, size_t, char*);
         long long nissy_getcube(long long, long long, long long, long long,
             long long, const char *, char *);
         long long nissy_solverinfo(const char *, char *);
@@ -44,6 +45,7 @@ namespace nissy {
         const error error::INVALID_MOVES{-20};
         const error error::INVALID_TRANS{-30};
         const error error::INVALID_SOLVER{-50};
+        const error error::INVALID_VARIATION{-51};
         const error error::NULL_POINTER{-60};
         const error error::BUFFER_SIZE{-61};
         const error error::DATA{-70};
@@ -62,10 +64,42 @@ namespace nissy {
                 constexpr size_t TRANSFORMATION = 12;
                 constexpr size_t SOLVE_STATS = 10;
                 constexpr size_t DATAID = 255;
+                constexpr size_t MOVES = 1000;
         }
 
         bool error::ok() const { return value >= 0; }
 
+        variation::variation(const std::string& str) : name{str} {}
+
+        variation::variations_result
+        variation::find_variations(const std::string& moves)
+        {
+                variation::variations_result result;
+
+                const size_t len = 3 * size::MOVES * 16;
+                result.solutions.resize(len);
+
+                auto err = nissy_variations(moves.c_str(), name.c_str(), len,
+                    result.solutions.data());
+
+                int size = result.solutions.find_first_of('\0');
+                result.solutions.resize(size);
+                result.err = error{err};
+
+                return result;
+        }
+
+        std::variant<variation, error>
+        variation::get(const std::string& name) {
+                char result[10];
+                variation s(name);
+
+                if (nissy_variations("", name.c_str(), 10, result) < 0)
+                        return error::INVALID_VARIATION;
+                else
+                        return s;
+        }
+
         cube::cube() {}
 
         error cube::move(const std::string& moves)
diff --git a/cpp/nissy.h b/cpp/nissy.h
index 199af10..74bbd32 100644
--- a/cpp/nissy.h
+++ b/cpp/nissy.h
@@ -39,6 +39,7 @@ namespace nissy {
                 static const error INVALID_MOVES;
                 static const error INVALID_TRANS;
                 static const error INVALID_SOLVER;
+                static const error INVALID_VARIATION;
                 static const error NULL_POINTER;
                 static const error BUFFER_SIZE;
                 static const error DATA;
@@ -63,6 +64,21 @@ namespace nissy {
                 static const compare_result DIFFERENT;
         };
 
+        class variation {
+        public:
+                struct variations_result {
+                        error err;
+                        std::string solutions;
+                };
+
+                const std::string name;
+
+                variations_result find_variations(const std::string&);
+                static std::variant<variation, error> get(const std::string&);
+        private:
+                variation(const std::string&);
+        };
+
         class cube {
         public:
                 cube();
diff --git a/python/examples/variations.py b/python/examples/variations.py
new file mode 100644
index 0000000..1b85d32
--- /dev/null
+++ b/python/examples/variations.py
@@ -0,0 +1,12 @@
+# Small example of nissy_python_module usage
+# See the solve.py example for more details on how this works
+
+from sys import path
+path.append("./")
+import nissy_python_module as nissy
+
+moves = "R U' Bw2 M D' x' F B(E2 F D B' Lw2 U2 U' S2 B)"
+
+print("Changing the last quarter turns of {} gives:".format(moves))
+for s in nissy.variations(moves, "lastqt"):
+        print(s)
diff --git a/python/nissy_module.c b/python/nissy_module.c
index a86b23f..88109d3 100644
--- a/python/nissy_module.c
+++ b/python/nissy_module.c
@@ -44,6 +44,29 @@ string_result(long long err, const char *result)
 }
 
 static PyObject *
+stringlist_result(long long err, char *result)
+{
+        int i, j, k;
+        PyObject *list, *item;
+
+        if(!check_error(err)) {
+                return NULL;
+        } else {
+                list = PyList_New(err);
+                for (i = 0, j = 0, k = 0; result[i] != 0; i++) {
+                        if (result[i] != '\n')
+                                continue;
+                        result[i] = 0;
+                        item = PyUnicode_FromString(&result[k]);
+                        PyList_SetItem(list, j, item);
+                        j++;
+                        k = i+1;
+                }
+                return list;
+        }
+}
+
+static PyObject *
 string_result_free(long long err, char *result)
 {
         PyObject *ret;
@@ -287,12 +310,11 @@ solve(PyObject *self, PyObject *args)
 {
         long long result;
         unsigned nissflag, minmoves, maxmoves, maxsolutions;
-        int optimal, i, j, k, threads;
+        int optimal, threads;
         const char *cube, *solver;
         char solutions[MAX_SOLUTIONS_SIZE];
         long long stats[NISSY_SIZE_SOLVE_STATS];
         PyByteArrayObject *data;
-        PyObject *list, *item;
 
         if (!PyArg_ParseTuple(args, "ssIIIIIIY", &cube, &solver, &nissflag,
              &minmoves, &maxmoves, &maxsolutions, &optimal, &threads, &data))
@@ -305,21 +327,7 @@ solve(PyObject *self, PyObject *args)
             stats, NULL, NULL);
         Py_END_ALLOW_THREADS
 
-        if(!check_error(result)) {
-                return NULL;
-        } else {
-                list = PyList_New(result);
-                for (i = 0, j = 0, k = 0; solutions[i] != 0; i++) {
-                        if (solutions[i] != '\n')
-                                continue;
-                        solutions[i] = 0;
-                        item = PyUnicode_FromString(&solutions[k]);
-                        PyList_SetItem(list, j, item);
-                        j++;
-                        k = i+1;
-                }
-                return list;
-        }
+        return stringlist_result(result, solutions);
 }
 
 PyDoc_STRVAR(countmoves_doc,
@@ -368,8 +376,9 @@ comparemoves(PyObject *self, PyObject *args)
         if (!PyArg_ParseTuple(args, "ss", &m1, &m2))
                 return NULL;
 
-        if ((cmp = nissy_comparemoves(m1, m2)) < 0)
-                return long_result(cmp);
+        cmp = nissy_comparemoves(m1, m2);
+        if (!check_error(cmp))
+                return NULL;
 
         switch (cmp) {
         case NISSY_COMPARE_MOVES_EQUAL:
@@ -381,6 +390,32 @@ comparemoves(PyObject *self, PyObject *args)
         }
 }
 
+PyDoc_STRVAR(variations_doc,
+"variations(moves, variation)\n"
+"--\n\n"
+"Find variations of a given move sequence\n"
+"\n"
+"Parameters:\n"
+"  - moves: the moves\n"
+"  - variation: the variation to apply, such as 'unniss' or 'lastqt'\n"
+"\n"
+"Returns: a list of move sequences, the variation of the given moves.\n"
+);
+PyObject *
+variations(PyObject *self, PyObject *args)
+{
+        long long err;
+        const char *m, *v;
+        char result[MAX_SOLUTIONS_SIZE];
+
+        if (!PyArg_ParseTuple(args, "ss", &m, &v))
+                return NULL;
+
+        err = nissy_variations(m, v, MAX_SOLUTIONS_SIZE, result);
+
+        return stringlist_result(err, result);
+}
+
 static PyMethodDef nissy_methods[] = {
         { "inverse", inverse, METH_VARARGS, inverse_doc },
         { "applymoves", applymoves, METH_VARARGS, applymoves_doc },
@@ -392,6 +427,7 @@ static PyMethodDef nissy_methods[] = {
         { "solve", solve, METH_VARARGS, solve_doc },
         { "countmoves", countmoves, METH_VARARGS, countmoves_doc },
         { "comparemoves", comparemoves, METH_VARARGS, comparemoves_doc },
+        { "variations", variations, METH_VARARGS, variations_doc },
         { NULL, NULL, 0, NULL }
 };
 
diff --git a/shell/shell.c b/shell/shell.c
index 8800094..0e624c9 100644
--- a/shell/shell.c
+++ b/shell/shell.c
@@ -21,6 +21,7 @@
 #define FLAG_MOVES2       "-moves2"
 #define FLAG_TRANS        "-trans"
 #define FLAG_SOLVER       "-solver"
+#define FLAG_VARIATION    "-variation"
 #define FLAG_NISSTYPE     "-nisstype"
 #define FLAG_MINMOVES     "-m"
 #define FLAG_MAXMOVES     "-M"
@@ -43,6 +44,7 @@ typedef struct {
         char *str_moves2;
         char *str_trans;
         char *str_solver;
+        char *str_variation;
         char *str_nisstype;
         unsigned minmoves;
         unsigned maxmoves;
@@ -62,6 +64,7 @@ static int64_t solve_exec(args_t *);
 static int64_t solve_scramble_exec(args_t *);
 static int64_t countmoves_exec(args_t *);
 static int64_t comparemoves_exec(args_t *);
+static int64_t variation_exec(args_t *);
 static int64_t help_exec(args_t *);
 
 static int parse_args(int, char **, args_t *);
@@ -75,6 +78,7 @@ static bool set_str_moves(int, char **, args_t *);
 static bool set_str_moves2(int, char **, args_t *);
 static bool set_str_trans(int, char **, args_t *);
 static bool set_str_solver(int, char **, args_t *);
+static bool set_str_variation(int, char **, args_t *);
 static bool set_str_nisstype(int, char **, args_t *);
 static bool set_minmoves(int, char **, args_t *);
 static bool set_maxmoves(int, char **, args_t *);
@@ -98,6 +102,7 @@ struct {
         OPTION(FLAG_MOVES2, 1, set_str_moves2),
         OPTION(FLAG_TRANS, 1, set_str_trans),
         OPTION(FLAG_SOLVER, 1, set_str_solver),
+        OPTION(FLAG_VARIATION, 1, set_str_variation),
         OPTION(FLAG_NISSTYPE, 1, set_str_nisstype),
         OPTION(FLAG_MINMOVES, 1, set_minmoves),
         OPTION(FLAG_MAXMOVES, 1, set_maxmoves),
@@ -114,7 +119,6 @@ struct {
         char *desc;
         int64_t (*exec)(args_t *);
 } commands[] = {
-/* TODO: add synopsis and description here */
         COMMAND(
                 "inverse",
                 "inverse " FLAG_CUBE " CUBE ",
@@ -197,6 +201,13 @@ struct {
                 comparemoves_exec
         ),
         COMMAND(
+                "variations",
+                "variations " FLAG_MOVES " MOVES " FLAG_VARIATION " VARIATION",
+                "Find variations of a move sequence."
+                INFO_MOVESFORMAT,
+                variation_exec
+        ),
+        COMMAND(
                 "help",
                 "help [" FLAG_COMMAND " COMMAND]",
                 "If no COMMAND is specified, prints some generic information "
@@ -511,6 +522,22 @@ comparemoves_exec(args_t *args)
 }
 
 static int64_t
+variation_exec(args_t *args)
+{
+        long long err;
+        char result[SOLUTIONS_BUFFER_SIZE];
+
+        err = nissy_variations(args->str_moves, args->str_variation,
+            SOLUTIONS_BUFFER_SIZE, result);
+
+        if (err < 0)
+                return err;
+        printf("%s", result);
+
+        return 0;
+}
+
+static int64_t
 help_exec(args_t *args)
 {
         int i;
@@ -550,6 +577,7 @@ parse_args(int argc, char **argv, args_t *args)
                 .str_moves2 = "",
                 .str_trans = "",
                 .str_solver = "",
+                .str_variation = "",
                 .str_nisstype = "",
                 .minmoves = 0,
                 .maxmoves = 20,
@@ -692,6 +720,14 @@ set_str_solver(int argc, char **argv, args_t *args)
 }
 
 static bool
+set_str_variation(int argc, char **argv, args_t *args)
+{
+        args->str_variation = argv[0];
+
+        return true;
+}
+
+static bool
 set_str_nisstype(int argc, char **argv, args_t *args)
 {
         args->str_nisstype = argv[0];
diff --git a/src/core/constants.h b/src/core/constants.h
index 26f6916..d8f2471 100644
--- a/src/core/constants.h
+++ b/src/core/constants.h
@@ -845,3 +845,69 @@ STATIC equivalent_moves_t equivalent_moves_table[] = {
         [MOVE_z2]  = {{UINT8_MAX}, {2, 2, UINT8_MAX}},
         [MOVE_z3]  = {{UINT8_MAX}, {2, 2, 2, UINT8_MAX}},
 };
+
+STATIC uint8_t slice_to_basic[] = {
+        [MOVE_M]  = MOVE_L,
+        [MOVE_M2] = MOVE_L2,
+        [MOVE_M3] = MOVE_L3,
+        [MOVE_S]  = MOVE_F,
+        [MOVE_S2] = MOVE_F2,
+        [MOVE_S3] = MOVE_F3,
+        [MOVE_E]  = MOVE_D,
+        [MOVE_E2] = MOVE_D2,
+        [MOVE_E3] = MOVE_D3,
+};
+
+STATIC uint8_t basic_to_slice[] = {
+        [MOVE_U]  = MOVE_E3,
+        [MOVE_U2] = MOVE_E2,
+        [MOVE_U3] = MOVE_E,
+        [MOVE_D]  = MOVE_E,
+        [MOVE_D2] = MOVE_E2,
+        [MOVE_D3] = MOVE_E3,
+        [MOVE_R]  = MOVE_M3,
+        [MOVE_R2] = MOVE_M2,
+        [MOVE_R3] = MOVE_M,
+        [MOVE_L]  = MOVE_M,
+        [MOVE_L2] = MOVE_M2,
+        [MOVE_L3] = MOVE_M3,
+        [MOVE_F]  = MOVE_S,
+        [MOVE_F2] = MOVE_S2,
+        [MOVE_F3] = MOVE_S3,
+        [MOVE_B]  = MOVE_S3,
+        [MOVE_B2] = MOVE_S2,
+        [MOVE_B3] = MOVE_S,
+};
+
+STATIC uint8_t rotation_to_basic[] = {
+        [MOVE_x]  = MOVE_R,
+        [MOVE_x2] = MOVE_R2,
+        [MOVE_x3] = MOVE_R3,
+        [MOVE_y]  = MOVE_U,
+        [MOVE_y2] = MOVE_U2,
+        [MOVE_y3] = MOVE_U3,
+        [MOVE_z]  = MOVE_F,
+        [MOVE_z2] = MOVE_F2,
+        [MOVE_z3] = MOVE_F3,
+};
+
+STATIC uint8_t basic_to_rotation[] = {
+        [MOVE_U]  = MOVE_y,
+        [MOVE_U2] = MOVE_y2,
+        [MOVE_U3] = MOVE_y3,
+        [MOVE_D]  = MOVE_y3,
+        [MOVE_D2] = MOVE_y2,
+        [MOVE_D3] = MOVE_y,
+        [MOVE_R]  = MOVE_x,
+        [MOVE_R2] = MOVE_x2,
+        [MOVE_R3] = MOVE_x3,
+        [MOVE_L]  = MOVE_x3,
+        [MOVE_L2] = MOVE_x2,
+        [MOVE_L3] = MOVE_x,
+        [MOVE_F]  = MOVE_z,
+        [MOVE_F2] = MOVE_z2,
+        [MOVE_F3] = MOVE_z3,
+        [MOVE_B]  = MOVE_z3,
+        [MOVE_B2] = MOVE_z2,
+        [MOVE_B3] = MOVE_z,
+};
diff --git a/src/core/core_types.h b/src/core/core_types.h
index 19a9f42..53cc95e 100644
--- a/src/core/core_types.h
+++ b/src/core/core_types.h
@@ -1,5 +1,3 @@
-#define MOVES_STRUCT_MAXLEN 1000
-
 typedef struct {
         cube_t cube;
         uint8_t orientation;
@@ -8,6 +6,6 @@ typedef struct {
 typedef struct {
         size_t nnormal;
         size_t ninverse;
-        uint8_t normal[MOVES_STRUCT_MAXLEN];
-        uint8_t inverse[MOVES_STRUCT_MAXLEN];
+        uint8_t normal[NISSY_SIZE_MOVES];
+        uint8_t inverse[NISSY_SIZE_MOVES];
 } moves_struct_t;
diff --git a/src/core/moves.h b/src/core/moves.h
index 9c8cc90..6169c6e 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -11,6 +11,8 @@ STATIC bool moves_struct_equal(
 STATIC long long comparemoves(const char *, const char *);
 STATIC uint8_t readmodifier(char);
 STATIC int64_t writemoves(size_t, const uint8_t *, size_t, char *);
+STATIC int64_t writemoves_struct(
+    const moves_struct_t [static 1], size_t, char *);
 
 STATIC_INLINE bool allowednextmove(uint8_t, uint8_t);
 STATIC bool allowedmoves(size_t, const uint8_t *);
@@ -23,6 +25,7 @@ STATIC_INLINE uint8_t moveopposite(uint8_t);
 STATIC_INLINE uint8_t reorient_move(uint8_t, uint8_t);
 STATIC_INLINE uint8_t inverse_reorient_move(uint8_t, uint8_t);
 STATIC_INLINE uint8_t movefollow(uint8_t);
+STATIC uint8_t transform_move_basic(uint8_t, uint8_t);
 STATIC uint8_t transform_move(uint8_t, uint8_t);
 
 STATIC cube_t move(cube_t, uint8_t);
@@ -31,6 +34,12 @@ STATIC uint8_t inverse_move(uint8_t);
 STATIC void sortparallel_moves(size_t, uint8_t*);
 STATIC bool are_lastmoves_singlecw(size_t, const uint8_t*);
 
+STATIC int64_t move_variations(const char *, const char *, size_t, char *);
+STATIC int64_t move_variations_lastqt(
+    const moves_struct_t [static 1], size_t, char *);
+STATIC int64_t move_variations_unniss(
+    const moves_struct_t [static 1], size_t, char *);
+
 #define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \
         RET_ERROR, ARG_ACTION) \
         const char *VAR_B; \
@@ -160,7 +169,7 @@ readmoves(
 STATIC int64_t
 readmoves_struct(const char *moves, moves_struct_t ret[static 1])
 {
-        return readmoves(moves, MOVES_STRUCT_MAXLEN, MOVES_STRUCT_MAXLEN,
+        return readmoves(moves, NISSY_SIZE_MOVES, NISSY_SIZE_MOVES,
             &ret->nnormal, &ret->ninverse, ret->normal, ret->inverse);
 }
 
@@ -270,6 +279,51 @@ writemoves_error:
         return NISSY_ERROR_BUFFER_SIZE;
 }
 
+STATIC int64_t
+writemoves_struct(
+        const moves_struct_t moves[static 1],
+        size_t buf_size,
+        char *buf
+)
+{
+        int64_t w, u;
+
+        w = 0;
+        if (moves->nnormal > 0) {
+                w = writemoves(moves->nnormal, moves->normal, buf_size, buf);
+                if (w < 0)
+                        goto writemoves_struct_error;
+        }
+
+        u = 0;
+        if (moves->ninverse > 0) {
+                if (moves->nnormal > 0) {
+                        if ((size_t)w >= buf_size)
+                                goto writemoves_struct_error;
+                        buf[w++] = ' ';
+                }
+                if ((size_t)w >= buf_size)
+                        goto writemoves_struct_error;
+                buf[w++] = '(';
+
+                u = writemoves(moves->ninverse, moves->inverse,
+                    buf_size-w, buf+w);
+                if (u < 0)
+                        goto writemoves_struct_error;
+
+                if ((size_t)w >= buf_size)
+                        goto writemoves_struct_error;
+                buf[w + (u++)] = ')';
+        }
+
+        buf[u+w] = '\0';
+        return u+w;
+
+writemoves_struct_error:
+        buf[w] = '\0';
+        return NISSY_ERROR_BUFFER_SIZE;
+}
+
 STATIC_INLINE bool
 allowednextmove(uint8_t m1, uint8_t m2)
 {
@@ -408,14 +462,12 @@ move(cube_t c, uint8_t m)
 }
 
 STATIC uint8_t
-transform_move(uint8_t m, uint8_t t)
+transform_move_basic(uint8_t m, uint8_t t)
 {
         uint8_t a, base, modifier;
 
-        if (m > MOVE_B3) {
-                LOG("transform_move: attempting to transform %s, but "
-                    "transofrmations are only supported for basic moves\n",
-                    movestr[m]);
+        if (t > 47) {
+                LOG("transform_move: invalid trans %" PRIu8 "\n", t);
                 return UINT8_ERROR;
         }
 
@@ -431,6 +483,27 @@ transform_move(uint8_t m, uint8_t t)
         return base + modifier;
 }
 
+STATIC uint8_t
+transform_move(uint8_t m, uint8_t t)
+{
+        if (m <= MOVE_B3)
+                return transform_move_basic(m, t);
+
+        if (m >= MOVE_Uw && m <= MOVE_Bw3)
+                return 18+transform_move_basic(m-18, t);
+
+        if (m >= MOVE_M && m <= MOVE_E3)
+                return basic_to_slice[
+                    transform_move_basic(slice_to_basic[m], t)];
+
+        if (m >= MOVE_x && m <= MOVE_z3)
+                return basic_to_rotation[
+                    transform_move_basic(rotation_to_basic[m], t)];
+
+        LOG("transform_move: invalid move %" PRIu8 "\n", m);
+        return UINT8_ERROR;
+}
+
 /* Applies the INVERSE of m BEFORE the scramble corresponding to c */
 STATIC cube_t
 premove(cube_t c, uint8_t m)
@@ -509,3 +582,140 @@ are_lastmoves_singlecw(size_t n, const uint8_t *moves)
 
         return isbase(moves[n-1]) && (!two || isbase(moves[n-2]));
 }
+
+STATIC int64_t
+move_variations(
+        const char *moves,
+        const char *variation,
+        size_t result_size,
+        char *result
+)
+{
+        moves_struct_t m;
+        int64_t err;
+
+        err = readmoves_struct(moves, &m);
+        if (err < 0) {
+                LOG("[variations] Error reading moves.\n");
+                return err;
+        }
+
+        if (!strcmp(variation, "lastqt")) {
+                return move_variations_lastqt(&m, result_size, result);
+        } else if (!strcmp(variation, "unniss")) {
+                return move_variations_unniss(&m, result_size, result);
+        } else {
+                LOG("[variations] Error: unknown variation '%s'\n", variation);
+                return NISSY_ERROR_INVALID_VARIATION;
+        }
+}
+
+STATIC int64_t
+move_variations_lastqt(
+        const moves_struct_t s[static 1],
+        size_t result_size,
+        char *result
+)
+{
+        uint8_t n1, n2, i1, i2, swapn1, swapn2, swapi1, swapi2, i, j, k, l;
+        int8_t in1, in2, ii1, ii2;
+        int64_t err, count;
+        size_t u;
+        moves_struct_t ss;
+
+        in1 = s->nnormal-1;
+        in2 = s->nnormal-2;
+        ii1 = s->ninverse-1;
+        ii2 = s->ninverse-2;
+
+        n1 = in1 >= 0 ? s->normal[in1] : UINT8_ERROR;
+        n2 = in2 >= 0 ? s->normal[in2] : UINT8_ERROR;
+        i1 = ii1 >= 0 ? s->inverse[ii1] : UINT8_ERROR;
+        i2 = ii2 >= 0 ? s->inverse[ii2] : UINT8_ERROR;
+
+        swapn1 = in1 >= 0 && n1 % 3 != 1 ? 1 : 0;
+        swapn2 = swapn1 && in2 >= 0 && n2 % 3 != 1 && parallel(n1, n2) ? 1 : 0;
+        swapi1 = ii1 >= 0 && i1 % 3 != 1 ? 1 : 0;
+        swapi2 = swapi1 && ii2 >= 0 && i2 % 3 != 1 && parallel(i1, i2) ? 1 : 0;
+
+        /* Reset ending qt to base so that they are sorted */
+        ss = *s;
+        if (swapn1 == 1) ss.normal[in1] = 3*movebase(n1);
+        if (swapn2 == 1) ss.normal[in2] = 3*movebase(n2);
+        if (swapi1 == 1) ss.inverse[ii1] = 3*movebase(i1);
+        if (swapi2 == 1) ss.inverse[ii2] = 3*movebase(i2);
+
+        u = 0;
+        count = 0;
+        for (i = 0; i <= swapn2; i++) {
+                if (i == 1) ss.normal[in2] += 2;
+                for (j = 0; j <= swapn1; j++) {
+                        if (j == 1) ss.normal[in1] += 2;
+                        for (k = 0; k <= swapi2; k++) {
+                                if (k == 1) ss.inverse[ii2] += 2;
+                                for (l = 0; l <= swapi1; l++) {
+                                        if (l == 1) ss.inverse[ii1] += 2;
+
+                                        err = writemoves_struct(
+                                            &ss, result_size-u, result+u);
+                                        if (err < 0)
+                                                goto lastqt_error;
+                                        u += err;
+                                        count++;
+
+                                        if (u >= result_size)
+                                                goto lastqt_error;
+                                        result[u++] = '\n';
+                                        result[u] = '\0';
+
+                                        if (l == 1) ss.inverse[ii1] -= 2;
+                                }
+                                if (k == 1) ss.inverse[ii2] -= 2;
+                        }
+                        if (j == 1) ss.normal[in1] -= 2;
+                }
+                if (i == 1) ss.normal[in2] -= 2;
+        }
+
+        return count;
+
+lastqt_error:
+        LOG("[variations] Error writing result.\n");
+        return NISSY_ERROR_BUFFER_SIZE;
+}
+
+STATIC int64_t
+move_variations_unniss(
+        const moves_struct_t s[static 1],
+        size_t result_size,
+        char *result
+)
+{
+        size_t i, tot;
+        uint8_t res[NISSY_SIZE_MOVES];
+        int64_t err;
+
+        tot = s->nnormal + s->ninverse;
+        if (tot > NISSY_SIZE_MOVES) {
+                LOG("[variations] Error: %zu total moves, more than maximum "
+                    "allowed %zu", tot, NISSY_SIZE_MOVES);
+                return NISSY_ERROR_BUFFER_SIZE;
+        }
+
+        for (i = 0; i < s->nnormal; i++)
+                res[i] = s->normal[i];
+        for (i = 0; i < s->ninverse; i++)
+                res[i+s->nnormal] = inverse_move(s->inverse[s->ninverse-i-1]);
+
+        err = writemoves(tot, res, result_size, result);
+        if (err < 0 || (size_t)err > result_size)
+                goto unniss_error;
+
+        result[err++] = '\n';
+        result[err] = '\0';
+        return 1;
+
+unniss_error:
+        LOG("[variations] Error writing result.\n");
+        return NISSY_ERROR_BUFFER_SIZE;
+}
diff --git a/src/nissy.c b/src/nissy.c
index 4b5d476..17ef960 100644
--- a/src/nissy.c
+++ b/src/nissy.c
@@ -149,6 +149,32 @@ nissy_applytrans_error:
 }
 
 long long
+nissy_variations(
+        const char *moves,
+        const char *variation,
+        unsigned long long result_size,
+        char *result
+)
+{
+        if (moves == NULL) {
+                LOG("[variations] Error: 'moves' argument is NULL\n");
+                return NISSY_ERROR_NULL_POINTER;
+        }
+
+        if (variation == NULL) {
+                LOG("[variations] Error: 'variation' argument is NULL\n");
+                return NISSY_ERROR_NULL_POINTER;
+        }
+
+        if (result == NULL) {
+                LOG("[variations] Error: 'result' argument is NULL\n");
+                return NISSY_ERROR_NULL_POINTER;
+        }
+
+        return move_variations(moves, variation, result_size, result);
+}
+
+long long
 nissy_getcube(
         long long ep,
         long long eo,
diff --git a/src/nissy.h b/src/nissy.h
index 38fe656..959b2d8 100644
--- a/src/nissy.h
+++ b/src/nissy.h
@@ -27,6 +27,7 @@ for example 'rotation UF' or 'mirrored BL'.
 #define NISSY_SIZE_TRANSFORMATION 12U
 #define NISSY_SIZE_SOLVE_STATS    10U
 #define NISSY_SIZE_DATAID         255U
+#define NISSY_SIZE_MOVES          1000U
 
 /* Flags for NISS options */
 #define NISSY_NISSFLAG_NORMAL  1U
@@ -99,6 +100,12 @@ not known.
 #define NISSY_ERROR_INVALID_SOLVER -50LL
 
 /*
+The value NISSY_ERROR_INVALID_VARIATION means that the given method of
+finding variations for a solution is not known.
+*/
+#define NISSY_ERROR_INVALID_VARIATION -51LL
+
+/*
 The value NISSY_ERROR_NULL_POINTER means that one of the provided pointer
 arguments is NULL. For example, it may be returned by solve when called
 with a solver that requires some pre-computed data, but the provided
@@ -205,6 +212,36 @@ nissy_applytrans(
 );
 
 /*
+Find variations of a given move sequence, for example by changing
+the direction of the last quarter turn(s), or linearizing a NISS move
+sequence. The result consists of one or more move sequences, one per line,
+and it always ends in a newline character.
+
+Parameters:
+   moves       - The moves of which to find the variation. Must be at most
+                 NISSY_SIZE_MOVES long.
+   variations  - Specify which kind of variations to find, e.g. "lastqt".
+   result_size - The size of the result buffer.
+   result      - The result buffer.
+
+Return values:
+   NISSY_ERROR_NULL_POINTER      - One of the provided pointers is NULL.
+   NISSY_ERROR_INVALID_MOVES     - The given moves are invalid.
+   NISSY_ERROR_INVALID_VARIATION - The given transformer is not known.
+   NISSY_ERROR_BUFFER_SIZE       - Either the result buffer is too small or the
+                                   given move sequence is longer than
+                                   NISSY_SIZE_MOVES.
+   Any value >= 0                - The number of variations found.
+*/
+long long
+nissy_variations(
+        const char *moves,
+        const char *variation,
+        unsigned long long result_size,
+        char *result
+);
+
+/*
 Get the cube with the given ep, eo, cp and co values. The values must be in the
 ranges specified below, but if the option "fix" is given any values outside its
 range will be adjusted before using it. The option "fix" also fixes parity and
@@ -365,6 +402,8 @@ nissy_solve(
 );
 
 /*
+Count the given moves.
+
 Parameters:
    moves  - The moves to be counted.
 
@@ -379,6 +418,8 @@ nissy_countmoves(
 );
 
 /*
+Compare the two moves sequences. Both must be at most NISSY_SIZE_MOVES long.
+
 Parameters:
    moves1 - The first sequence of moves to compare.
    moves2 - The second sequence of moves to compare.
diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h
index 00ed84c..9f209d1 100644
--- a/src/solvers/solutions.h
+++ b/src/solvers/solutions.h
@@ -55,7 +55,7 @@ solution_list_init(solution_list_t sols[static 1], size_t n, char *buf)
                 return false;
 
         sols->nsols = 0;
-        sols->shortest_sol = MAXLEN + 1;
+        sols->shortest_sol = SOLUTION_MAXLEN + 1;
         sols->size = n;
         sols->used = 0;
         sols->buf = buf;
@@ -162,7 +162,7 @@ appendsolution(
         uint8_t t;
         solution_moves_t tsol[NTRANS];
 
-        if (moves->nmoves + moves->npremoves > MAXLEN)
+        if (moves->nmoves + moves->npremoves > SOLUTION_MAXLEN)
                 goto appendsolution_error_solution_length;
 
         for (
diff --git a/src/solvers/solutions_types_macros.h b/src/solvers/solutions_types_macros.h
index f1cb517..e57e039 100644
--- a/src/solvers/solutions_types_macros.h
+++ b/src/solvers/solutions_types_macros.h
@@ -1,10 +1,10 @@
-#define MAXLEN 20
+#define SOLUTION_MAXLEN 20
 
 typedef struct {
         uint8_t nmoves;
-        uint8_t moves[MAXLEN];
+        uint8_t moves[SOLUTION_MAXLEN];
         uint8_t npremoves;
-        uint8_t premoves[MAXLEN];
+        uint8_t premoves[SOLUTION_MAXLEN];
 } solution_moves_t;
 
 typedef struct {
diff --git a/test/150_variations/00_unniss.in b/test/150_variations/00_unniss.in
new file mode 100644
index 0000000..84c3c3d
--- /dev/null
+++ b/test/150_variations/00_unniss.in
@@ -0,0 +1,2 @@
+unniss
+Uw2 F B' L x M R D' (D' R2 F' L2 B D')
diff --git a/test/150_variations/00_unniss.out b/test/150_variations/00_unniss.out
new file mode 100644
index 0000000..f38061b
--- /dev/null
+++ b/test/150_variations/00_unniss.out
@@ -0,0 +1,2 @@
+1
+Uw2 F B' L x M R D' D B' L2 F R2 D
diff --git a/test/150_variations/01_lastqt_simple.in b/test/150_variations/01_lastqt_simple.in
new file mode 100644
index 0000000..f7ecc50
--- /dev/null
+++ b/test/150_variations/01_lastqt_simple.in
@@ -0,0 +1,2 @@
+lastqt
+U2 D L' F
diff --git a/test/150_variations/01_lastqt_simple.out b/test/150_variations/01_lastqt_simple.out
new file mode 100644
index 0000000..53fbdcc
--- /dev/null
+++ b/test/150_variations/01_lastqt_simple.out
@@ -0,0 +1,3 @@
+2
+U2 D L' F
+U2 D L' F'
diff --git a/test/150_variations/02_lastqt_niss.in b/test/150_variations/02_lastqt_niss.in
new file mode 100644
index 0000000..fc72321
--- /dev/null
+++ b/test/150_variations/02_lastqt_niss.in
@@ -0,0 +1,2 @@
+lastqt
+U B2 L (F R')
diff --git a/test/150_variations/02_lastqt_niss.out b/test/150_variations/02_lastqt_niss.out
new file mode 100644
index 0000000..52c0db0
--- /dev/null
+++ b/test/150_variations/02_lastqt_niss.out
@@ -0,0 +1,5 @@
+4
+U B2 L (F R)
+U B2 L (F R')
+U B2 L' (F R)
+U B2 L' (F R')
diff --git a/test/150_variations/03_lastqt_parallel.in b/test/150_variations/03_lastqt_parallel.in
new file mode 100644
index 0000000..8a650fb
--- /dev/null
+++ b/test/150_variations/03_lastqt_parallel.in
@@ -0,0 +1,2 @@
+lastqt
+U F B'
diff --git a/test/150_variations/03_lastqt_parallel.out b/test/150_variations/03_lastqt_parallel.out
new file mode 100644
index 0000000..611b3df
--- /dev/null
+++ b/test/150_variations/03_lastqt_parallel.out
@@ -0,0 +1,5 @@
+4
+U F B
+U F B'
+U F' B
+U F' B'
diff --git a/test/150_variations/04_lastqt_parallel_niss.in b/test/150_variations/04_lastqt_parallel_niss.in
new file mode 100644
index 0000000..8f186f5
--- /dev/null
+++ b/test/150_variations/04_lastqt_parallel_niss.in
@@ -0,0 +1,2 @@
+lastqt
+L2 R U' D (U' D')
diff --git a/test/150_variations/04_lastqt_parallel_niss.out b/test/150_variations/04_lastqt_parallel_niss.out
new file mode 100644
index 0000000..5600d88
--- /dev/null
+++ b/test/150_variations/04_lastqt_parallel_niss.out
@@ -0,0 +1,17 @@
+16
+L2 R U D (U D)
+L2 R U D (U D')
+L2 R U D (U' D)
+L2 R U D (U' D')
+L2 R U D' (U D)
+L2 R U D' (U D')
+L2 R U D' (U' D)
+L2 R U D' (U' D')
+L2 R U' D (U D)
+L2 R U' D (U D')
+L2 R U' D (U' D)
+L2 R U' D (U' D')
+L2 R U' D' (U D)
+L2 R U' D' (U D')
+L2 R U' D' (U' D)
+L2 R U' D' (U' D')
diff --git a/test/150_variations/variations.c b/test/150_variations/variations.c
new file mode 100644
index 0000000..2c08607
--- /dev/null
+++ b/test/150_variations/variations.c
@@ -0,0 +1,19 @@
+#include "../test.h"
+
+long long nissy_variations(
+    const char *, const char *, long long unsigned, char *);
+
+void run(void) {
+        long long err;
+        char variation[STRLENMAX], moves[STRLENMAX], result[STRLENMAX];
+
+        fgets(variation, STRLENMAX, stdin);
+        variation[strlen(variation)-1] = '\0'; /* Remove newline */
+        fgets(moves, STRLENMAX, stdin);
+
+        err = nissy_variations(moves, variation, STRLENMAX, result);
+        if (err < 0)
+                printf("Error %lld\n", err);
+        else
+                printf("%lld\n%s", err, result);
+}