Paint a Cube by rolling it (Puzzle Algorithm)

I stumbled across this game in Simon Tatham's puzzle app. It's called cube. The description according to the game is:

You have a grid of 16 squares, six of which are blue; on one square rests a cube. Your move is to use the arrow keys to roll the cube through 90 degrees so that it moves to an adjacent square. If you roll the cube on to a blue square, the blue square is picked up on one face of the cube; if you roll a blue face of the cube on to a non-blue square, the blueness is put down again. (In general, whenever you roll the cube, the two faces that come into contact swap colours.) Your job is to get all six blue squares on to the six faces of the cube at the same time.

Attached is a link to a screenshot of the game .

I would like to ask the CS community if there is a known algorithm for solving such a problem as I haven't found anything online.

As Dmitry noticed there is very little possible states of the game, so it's relevant to search for solution using BFS traversal. But let's start from some numbers.
Staring positions

In terms of possible staring states we have
$$ 16 \cdot {16 \choose 6} = 128128 $$
Coloring of $4\times4$ gird using $6$ colors gives ${16 \choose 6}$ cases, and $16$ for initial position of cube, but you can easily reduce this number by a factor of $16$, because you always can place cuboid on any (white) cell of the gird not changing its coloring pattern (after each move doing its reverse and doing this move again).

notice: we can use such trick only finding any solution, not optimal one.

Secondly we aren't interested in starting positions that are symmetric. So let's eliminate them, and enumerate positions (Burnside lemma will be helpful). The final count equals

$$1051 \; \text{positions}$$

Concluding, we can use this fact and precompute solutions for all possible starting game states and it won't hurt our memory.
Algorithm

Let's construct directed graph of this game. Each node will be representing some state of the game (including current coloring of grid, position of cube and colors on the cube itself). Each directed edge from one state to another will represent possibility of moving between this states (each state has at most $4$ neighbors, so graph isn't dense).

Then using BFS on so build graph, we can calculate (for example) distance to each state from initial one. That's even better, because now we can find optimal solution! And this is description of above approach:

• Create queue containing starting state

• Repeat while solved state aren't found

• Take first state from queue and mark as visited

• For each achievable next state, push it on queue (if next state is unvisited already)

Implementation

I have created github repo with implementation of such approach. Check it out if you are interested!

Lastly, example solution may look like this one:

StackExchange Computer Science Q#156414, answer score: 12