The goal of this competition is to develop solving/sorting methods for certain kind of permutation transformations which are mathematical model for [transposons](https://en.wikipedia.org/wiki/Transposable_element). Problem is known to be NP-hard in general, but still for limited sizes it might be possible to achieve optimal solution, while larger sizes just - the shorter solutions achieved the better. Challenge can serve as one of the benchmarks for modern pathfinding methods, as well as for LLM to solve real research tasks. The problem represents a wide class of pathfinding/planning/reinforcements learning problems, which are important in mathematics, computer science, bionformatics, communication theory, etc. The open conjecture https://oeis.org/A065603 predicts the worst case performance (also called [God's algorithm](https://en.wikipedia.org/wiki/God%27s_algorithm) or diameter of Cayley graph) is ceiling((n+1)/2). Such problems are known to be hard, conjecture is open for 25 years. The challenge is almost identical to the [Kaggle Santa 2023 challenge ](https://www.kaggle.com/competitions/santa-2023), with the only difference to focus on the single puzzle. The advanced machine learning methods are proposed e.g. in [CayleyPy project ](https://cayleypy.github.io/cayleypy-docs/api.html), [CayleyPy-Cube](https://arxiv.org/abs/2502.13266), [CayleyPy-RL](https://arxiv.org/abs/2502.18663), [CayleyPy-Growth](https://www.arxiv.org/abs/2509.19162). CayleyPy is open-source crowd-sourcing project to develop effective AI-based library for mathematics - you are welcome to contribute - contact us. For the challenge you are welcome to use any methods you prefer, only score matters. **Computer science perspective - it is a sorting problem** [Pancakes sorting](https://en.wikipedia.org/wiki/Pancake_sorting) is another example (with Bill Gates involved - not a joke). **Broader Mathematical Context - groups and Cayley graphs** From a mathematical perspective it is a typical task in mathematics: decompose an element of a group into a product of given generators ("moves"), or, in the other words, find a path on the [Cayley graph](https://en.wikipedia.org/wiki/Cayley_graph) of a group. For example - [bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) algorithm provides the shortest paths on the the [permutohedron](https://en.wikipedia.org/wiki/Permutohedron) Cayley graph - with nodes all n! permutations, and edges connect permutations different only in neighbour positions - thus represents a permutation as a sequence of neighbour transpositions. Length of the decomposition (path) is called "[word metric](https://en.wikipedia.org/wiki/Word_metric)" in group theory. Research on Cayley graphs is of fundamental importance for mathematics and the field contains many notoriously hard problems, which has been addressed by renowned mathematicians such as [M. Gromov](https://en.wikipedia.org/wiki/Mikhael_Gromov_(mathematician)) ([theorem](https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_of_polynomial_growth)) and [T. Tao](https://en.wikipedia.org/wiki/Terence_Tao) ([posts](https://terrytao.wordpress.com/2010/07/10/cayley-graphs-and-the-geometry-of-groups/)), among others. Moreover, it has numerous applications, ranging from bioinformatics (e.g., estimating evolutionary distance—"[Transform men into mice](https://ieeexplore.ieee.org/abstract/document/492588/)" 😃), to the optimisation of [interprocessor networks](https://ieeexplore.ieee.org/document/21148), and beyond. Famous computer scientist [Donald Knuth ](https://en.wikipedia.org/wiki/Donald_Knuth) contributed to [improving the algorithm](https://arxiv.org/abs/math/9201304) to solve the problems like that. Such algorithm is implemented in computer algebra systems like [GAP/SAGE](https://doc.sagemath.org/html/en/reference/groups/sage/groups/perm_gps/cubegroup.html), however these methods are [not efficient](https://mathoverflow.net/q/482661/10446) ([notebook](https://www.kaggle.com/code/alexandervc/gap-cannot-solve-rubik-s-cube-444)) on large groups. And the challenge is to improve them. **Broader RL Context - RL with severely sparse reward** The problem is a typical reinforcement learning problem - states of puzzle (nodes of Cayley graph) is a space of states, moves (edges of Cayley graph) - are actions, while rewards (penalties) are always "1", unless you found the solution. The cumulative reward (penalty) becomes exactly the length of the path to the solution state. And the goal is to minimize it, i.e. to find the shortest path. Value function has very clear and natural interpretation - length of the path. Bellman equation for the value function comes from trivial relation on path length. (See [CayleyPy-RL](https://arxiv.org/abs/2502.18663) for more details). There is a severe "sparse reward problem", since "always 1" is meaningless reward (only tiny detail that for the solution state reward is not 1, but 0, makes setup meaningful). Thus advancing the challenge you will contribute to development of RL methods overcoming the "sparse reward problem" on extremely huge spaces like 10^33 and beyond. **Similar Challenges** [Kaggle Santa 2023 challenge ](https://www.kaggle.com/competitions/santa-2023) - several puzzles: cubes, rings, globes. LRX series - [OEIS-A186783 conjecture](https://www.kaggle.com/competitions/lrx-oeis-a-186783-brainstorm-math-conjecture), [Towards God's algorithm](https://www.kaggle.com/competitions/lrx-discover-math-gods-algorithm) , [Binary states 0/1](https://www.kaggle.com/competitions/lrx-binary-in-search-of-gods-number) - just three moves - L,R - left/right cyclic shifts, X - eXchange positions 0 and 1. Questions go back to "one of the founding fathers of Soviet cybernetics" [V.M. Glushkov](https://en.wikipedia.org/wiki/Victor_Glushkov) 1968 seminal work and are still unsolved. See survey [link1](https://library.keldysh.ru/prep_vw.asp?lg=e&pid=8508) , [link2](https://www.kaggle.com/datasets/alexandervc/cayleypy-development-3-growth-computations/data?select=Glukhov_Zubov1999review.pdf) (pages 21-22). [Pancake sorting](https://www.kaggle.com/competitions/CayleyPy-pancake) [Transposons](https://www.kaggle.com/competitions/cayleypy-transposons) [Reversals](https://www.kaggle.com/competitions/cayleypy-reversals) [Glushkov problem](https://www.kaggle.com/competitions/cayleypy-glushkov) [RapapportM2](https://www.kaggle.com/competitions/cayleypy-rapapport-m2) [Rubik's cube 444](https://www.kaggle.com/competitions/cayley-py-444-cube) [Professor Tetraminx](https://www.kaggle.com/competitions/cayley-py-professor-tetraminx-solve-optimally) [Megaminx](https://www.kaggle.com/competitions/cayley-py-megaminx) [Christophers jewel](https://www.kaggle.com/competitions/cayleypy-christophers-jewel) [SuperCube from IHES](https://www.kaggle.com/competitions/cayleypy-ihes-cube)