Following up on @DaftWullie's answer, for certain combinatorial puzzles such as the 3x3 Rubik's cube, it might also be convenient to consider a fixed register of qubits (or qubits and qutrits) for each cell of the cube, because then twists/turns of the faces almost immediately present themselves as (controlled) $\mathsf{SWAP}$'s of the respective cells.

For example, consider the $9$ cells of the front face of a cube. Each cell (apart from the fixed center cell might correspond to $3$ qubits (or $1$ qubit and $1$ qutrit), with a fixed but arbitrary mapping of colors to qubits/qutrits, such as $f(\vert 000\rangle)\mapsto \text{BLUE}, f(\vert 001\rangle)\mapsto\text{RED}$, etc. The quarter-turn twists $F$ and $F'$ are simple permutations of the qubits, and $\vert\psi\rangle$ is the tensor product over each register.

With such a set-up, the circuits that implement the permutations may be as above. Here, $\text{A,B,}\cdots$ are fixed registers of qubits (qutrits) of the cells on the front face, $F$ is a clockwise quarter-turn of the front face, and $F'$ is a counter-clockwise quarter turn. (The corner and cells adjacent to the front would also be permuted in a similar fashion).
I'm working out the circuits for a toy 2x2 version of the 15 puzzle, and another one for the Pyraminx. These have the advantage in that the number of colors/states is $4$, which means no qutrits would be needed. Indeed, the 2x2 puzzle is small enough that it could probably be implemented with existing hardware.