# Solving a Rubik's Cube Using its Local Graph Structure

arXiv: https://arxiv.org/abs/2408.07945 · HTML: https://mlsanity.com/paper/2408.07945/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 5 of its 14 references that are in the map.
- First posted on arXiv 15 Aug 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 5 of 5)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)
- [Graph Networks with Spectral Message Passing](https://mlsanity.com/paper/2101.00079/) (2020)
- [Solving the Rubik's Cube Without Human Knowledge](https://mlsanity.com/paper/1805.07470/) (2018)

## Built on by (most cited first, 1 of 1)

- [Node Classification and Search on the Rubik's Cube Graph with GNNs](https://mlsanity.com/paper/2501.18580/) (2025)

## Abstract (arXiv)

The Rubix Cube is a 3-dimensional single-player combination puzzle attracting attention in the reinforcement learning community. A Rubix Cube has six faces and twelve possible actions, leading to a small and unconstrained action space and a very large state space with only one goal state. Modeling such a large state space and storing the information of each state requires exceptional computational resources, which makes it challenging to find the shortest solution to a scrambled Rubix cube with limited resources. The Rubix Cube can be represented as a graph, where states of the cube are nodes and actions are edges. Drawing on graph convolutional networks, we design a new heuristic, weighted convolutional distance, for A star search algorithm to find the solution to a scrambled Rubix Cube. This heuristic utilizes the information of neighboring nodes and convolves them with attention-like weights, which creates a deeper search for the shortest path to the solved state.