Happy New Year: solving the Rubik's Cube in SQL - EXPLAIN EXTENDED at EXPLAIN EXTENDED

Happy New Year: solving the Rubik’s Cube in SQL

It's the holiday season again. This time of year, in between shopping, visiting friends and watching old movies on TV, I really like to solve puzzles. I like them all: crossword puzzles, jigsaw puzzles, logic puzzles, you name it. But one thing I never quite learned to solve is most popular puzzle in the world, the Rubik's Cube. It's time to fill the gap!

This year, we will be solving the Rubik's Cube in SQL.

The Rubik's Cube probably needs little introduction, but just in case. This is a small plastic cube made of 3×3×3 = 27 smaller cubes (called cubies in the community's parlance). It's equipped with a clever mechanism which lets you turn its faces about all six axes. Initially, the cubies are positioned so that every face has its own uniform color, but as you turn the faces in different directions, all the colors mix and spread around. Your goal is to restore the original colors by putting the cubies back in place.

The cubies in the centers of the faces never move relatively to each other. The red center always opposes the orange center, the blue the green, and the white the yellow. Also, if you look at the red, white and blue centers, they will always run clockwise in that order. No matter how you turn the faces on the cube, the center cubies will always stay this way.

Each cubie is unique. Apart from the center cubie in the middle (which we never see) and the six face center cubies, there are 8 corner cubies (with three stickers on them) and 12 edge cubies (with two stickers on them). In a solved cubie, all faces have the same color. This means that every corner cubie has its own unique set of colors, and every edge cubie too. The blue-white edge is the one sitting on the blue and white faces in a solved cube, and so it. Naturally, it means that there's no such thing as a red-orange edge or a red-orange-green corner (because the red face opposes the orange). Since the stickers stay on the cubies as we move them about, we can just name the cubies by their colors. There is only one red-white-blue corner which would move about but always stay red-white-blue.

When the cube is scrambled, it might seem to the untrained eye that the cubies can turn any old way. Yet, that's not the case. Because of the way the mechanism works, there are certain principles that limit the cubies' positions. For instance, no matter how you turn the cube, you cannot make a single corner or a single edge cubie turn in its place, or make just two cubies trade their places, with all the rest staying in place. These limitations are known as cube laws. In fact, if you take the cube apart and put the cubies back in random order, there's only one chance in 12 that you will get it right (i.e. you make a cube that can be solved by making legal turns). It will come handy later.

To describe a cube scramble, we could just list the stickers' colors ("the colors on the face with the red center, counting from the red-white-blue corner clockwise are red, white, yellow, green…") or cubie positions ("the red-yellow-green corner cubie is between the orange, white and green faces…"). But turns out, there is another way.

Similar to other famous combination puzzles, the Rubik's Cube runs on group theory. Even the Wikipedia page on group theory is illustrated by nothing else than an image of a Rubik's Cube. For those wishing to delve into the finer detail, there's a nice article on Wikipedia on the Rubik's Cube group. For the rest of us laypeople, this means that every valid state of the cube can be described by the sequence of moves (face turns) that have lead to this state. Come to think of it, that's only natural: if the cube came out of the box solved and we only scrambled it using the legal moves, then if we replay these moves on another cube, we will get the same scramble with the same colors. So, instead of naming the colors or cubies' positions, we can just say "take a solved cube, turn the white face clockwise, then the red face counterclockwise, then…"). In the end, it will be the same thing.

Note that in the previous paragraph I said that it would be possible, not that it would be easy. In fact, if we take a scrambled cube described by the series of moves from the solved cube, and replay these moves in reverse, we will get back to the solved cube. And that's the very essence of the problem: how do we, looking at a scrambled cube, find the sequence of moves that has lead to this particular state? Once we find the answer to this question, we'll just need to reverse this sequence and the cube will be solved. This answer, however, is not trivial to find.

The original slogan for the Rubik's Cube was "over three billion combinations, and only one right". Albeit technically correct, this was a sheer understatement. If you just take the cube apart and assemble it, there are $12! = 479\,001,600$ ways you can put the edge cubies in and $8! = 40\,320$ ways you can put the corner cubies in. In addition, there are $3^8 = 6\,561$ ways you can turn the corner cubies and $2^{12} = 4\,096$ ways you can turn the edge cubies. As I told before, only one in 12 of those combinations would be correct, still, it leaves us with $\frac{12!8!3^{8}2^{12}}{12} \approxeq 4.3\cdot10^{19}$ possible cube states — way way over three billion!

Even the "only one right" part is not quite correct, depending on how you look at it. If we represent the cube by defining the permutations and turns of its corners and edges, there is exactly one representation of the solved state indeed. But let's look at the cube which is one red clockwise turn away from solved. This state is achievable from the solved state by turning the red face counterclockwise once. But so it is by turning the red face counterclockwise five times, or nine; or clockwise three times, or seven. This means that the representation of the cube's state by sequences of moves is not unique. Given that there is an infinite number of move sequences, but only a finite number of valid cube states, it's hardly a surprise.

A naïve way to solve the cube on a computer would be to represent it as a graph. The nodes of the graph would be cube states. The edges would be face turns turning the states one into another. Finding the cube solution would then be equivalent to the task of finding the shortest path in a graph. In general, this is not a hard task, and efficient algorithms do exist for it. However, the number of the cube states has a lot of zeros. It makes straightforward approaches to solving this problem computationally infeasible. However efficient the algorithms are, $10^{19}$ is too many numbers to crunch.

If you see a puzzle which works in discrete turns, and the turns can be reversed, then most probably you are looking at a group in disguise. One way to deal with a nasty group is to split it into subgroups and see if they would be easier to reason about. If you are not familiar with group theory, this is probably best illustrated with an example.

Let's assume you locked your bike to a rail with a five-digit combination lock and forgot the combination (this, kids, is exactly what we assume when we are talking about cracking combination locks). This is a puzzle not unlike the Rubik's Cube: by turning the dials, you try to set the device into the target state, and the dials are cyclic and reversible. You want to get there as fast as possible, in a minimum number of turns (because it's late, you're tired and want to get home, and not for any other reason you might be thinking of). The lock states are a group as well, with single turns of every dial as generators, and composition of these turns as the group operation.

There are exactly 100 000 states of a five-digit lock. If you work fast and it takes you a second to switch the lock combination and try the lock, on average, you will still need to try 50 000 combinations before you open the lock. This would take you all day and a good portion of the night.

However, if the lock is crappy (most of them are), you can pull the shackle and turn the last dial (or the first, depending on the lock mechanism), while the shackle is under tension. You will feel or even hear a faint click as the dial locks into its place, and after that it will be somewhat hard to turn it further. You then leave this dial be, and, still pulling the shackle, try the next dial, and so on. This way, you will need to make at most 50 turns to get the combination right, less than a minute.

What you just did was an exercise in group theory. You, incrementally, identified subgroups containing the target state and pruned the graph so that it would only connect vertices of those subgroups. Should the police ask you what you were doing, you could just tell them you were doing math!

The Rubik's Cube puzzle is a little bit different from the padlock puzzle. With the Rubik's Cube we know the target state but don't know how to get there. This is exactly the opposite of the combination lock problem. However, the subgroup strategy remains the same: first, we figure out how to get into the subgroup, then how to get to the target state within the subgroup.

If you ever start googling for computer algorithms solving the Rubik's Cube, you will inevitably land on Jaap Scherphuis's Puzzle Page, describing the Thistlethwaite's algorithm for solving the cube. This algorithm was developed by Morwen Thistlethwaite in the 80's. It's quite old, and better algorithms have been developed since, but this one is still of high theoretical and practical importance. It's less resource intensive than the others, relatively easy to implement, and for a quite a long time the humanity knew nothing better.

Thistlethwaite's algorithm sequentially breaks the Rubik's Cube group into subgroups by limiting the inventory of turns. The indexes of each subgroup (the factor by which we shrink the space of target states on each step) are of palatable size. When solving the padlock, each time we locked a dial, we had been limiting our moves within the graph to a subgroup of index 10 (thus decreasing the space of possible solutions by the factor of 10 on each step). Thistlethwaite's algorithm uses four subgroups with indexes of 2 048, 1 082 656, 29 400, and 663 552, accordindly. The product of these numbers is the enormous cardinality of the Rubik's Cube group. But by breaking the solution into subgroups, we can, roughly speaking, reduce the algorithm complexity from product of these numbers to their sum, which is in the range of millions. Millions is still a big number, but nothing a today's computer can't handle, even in SQL.

Jaap's page hosts the original scans of Dr. Thistlethwaite's letter with the description of the algorithm. The letter begins with an optimistic passage:

I should perhaps point out that this strategy isn't easy to perform (even John Conway finds it quite hard!), for two reasons: first, only one representative of each symmetry class is given in the tables; second, I have given only the barest documentation.

This is true in every possible way. Grasping that algorithm was a very hard task for me, even though knowing that John Conway had the same problem was in some weird way a little bit reassuring. I spent a great deal of time, first trying to figure it out on my own, and, then, looking for an existing implementation. I found lots of questions and answers on Stack Exchange and other resources, including those from Mr. Scherphuis himself, but they didn't quite click with me until I found this implementation in Go by Drew Finnis and Anya Schukin. This one was really easy to follow, and I adopted it for this post with some changes.

Terminology

Rubik's Cube's states, moves and solutions are traditionally written down and evaluated using so called Singmaster's notation. The cube is fixed in space so that, say, the red face is always up, the blue one right, and the white one front, but you are free to select any initial reference position you want, as long as you stick to it. Then, the moves are written down using the acronyms $U, R, F, D, L, B$ (for up, right, front, down, left and back, respectively). A letter on its own means a clockwise quarter-turn, a letter followed by a prime symbol means a counterclockwise quarter-turn, and a letter followed by a square means a half-turn (traditionally, a half-turn counts as one turn when evaluating the solution length, even though it's composed of two quarter-turns). So, in Singmaster's notation, $DU'F^2$ would mean "turn the down face clockwise by 90 degrees, then the up face counterclockwise by 90 degrees, then the front face by 180 degrees".

We will use a slightly modified Singmaster's notation, because the prime symbol and the superscript are not that easy to type on my keyboard. I first thought about replacing the prime symbol with a single quote, but this is a special symbol in SQL and I would need to escape it in strings. So we will be using uppercase letters, like $U$ , for 90° turns (quarter-turn clockwise); uppercase letters appended with 2, like $U2$ , for 180° turns (half-turns); and lowercase letters, like $u$ , for 270° turns (quarter-turn counterclockwise).

As the algorithm works its way through the moves, it needs to look at the cube's representation in terms of cubies' positions. As we saw above, to describe the cube, it's enough to list the positions and turns of its corner and edge cubies. We can do that by looking at the solved state and assigning a number from 0 to 7 to every corner cubie, a number from 0 to 11 to every edge cubie, and also encode the corner cubies' orientations and edge cubies' orientations with a number from 0 to 2 and 0 to 1, respectively. So, to completely encode the cube's state, we would need two arrays of size 12 (positions and orientations of the edge cubies) and two arrays of size 8 (positions and orientation of the corner cubies). The first array in these pairs would hold the permutations (unique numbers from 0 to the size of the array less one, in different order); the second would orientations (any combination of numbers from 0 to 2 and from 0 to 1, respectively). This notation is slightly redundant because it can encode invalid states, but it's easy to work with.

The way we enumerate the cubies doesn't really matter, as long as it's consistent, but a smart choice of the enumeration system will make our SQL queries a little bit easier to grasp. I used the same encoding as the Go program did, which in its turn had been adopted from Dr. Thistletwaite's paper. At first glance it looks a little bit confusing, but it will make sense later.

The permutations are easy to read: if we see something like $0, 1, 5, 7, 2, 4, 3, 6$ for the corner cubies, it means that the cubies 0 and 1 are in their original corners (ULB and DLF, respectively), the cubie 5 (the DLB cubie) sits in the corner 2 (the DRB corner), and so on. $0, 1, 2, 3, 4, 5, 6, 7$ means that all the corner cubies sit in their right places (although some of them might be turned the wrong way). It works the same way for the edge cubies.

Orientations are a little bit trickier. Let's consider the corners first. If a cubie sits in its own corner, then 0 means that the cubie is turned the right way, 1 that it's turned one third clockwise and 2 that it's turned one third counterclockwise. On that much we can easily agree. But what exactly is the "right" way if it doesn't sit in its own corner?

We can notice that every corner cubie has one U or D facet, one L or R facet and one F or B facet. Let's, for a moment, imagine that the opposing colors are the same. We'll call these colors "dup", "reft" and ~~"fack"~~ "bront". This way, all corner cubies will have the same colors, but four of them will become mirror reflections of the other four. We'll randomly assign one of the colors (say, "reft") to be the reference color. This way it becomes easy: every cubie, regardless of its position, will have a natural orientation — that of its "reft" facet. Let's notice that turning the faces about the L/R axis (making the L or R turns, or combinations thereof) does not change the orientations of the cubies. It will become important later.

We can reason about the edge orientation in a similar way. The edge cubies have just two facets with stickers on them, but let's pretend they have all six and we just don't see the rest. We can assign a reference axis (let it be the U/B axis) and just say that a quarter turn of an edge cubie in place about the U/D axis changes its orientation, while the turns about all other axes keep it. So if an F/L cubie sits in the U/R slot, we just need to count how many quarter-turns about the U/D axis we need to make to drive it into the correct orientation in space. We have two special axes for the edge cubies (L/R and F/B) which don't change their orientation being turned about.

Equipped with this knowledge, we can start attacking the problem.

Subgroup 1

A scrambled cube can have, modulo cube laws, any old combination of corner and edge permutations and orientations. However, we can note that the only way we can change the edge orientations is by quarter-turning up or down faces (i.e. making moves from this list: $U, D, u, d$ ). Since the other two axes are special, turns about them don't change edge orientations.

If we can orient all the edges correctly, and then refrain from making the edge-turning moves (quarter-turns about the U/D axis; half-turns are OK), then the edges will stay oriented correctly. This is exactly what we did with the padlock: as soon as we had found a part of the solution, we locked it in place and then refrained from the moves which would change it.

From the group-theoretic point of view, we would need to find an element in the cube's group so that its product with the scrambled state as a left factor would be in subgroup $\langle U2, D2, F, B, L, R\rangle$ . In plain English it means that we need to look at the cube, find a sequence of moves which would fix the edges' orientations, and then stop making any moves which would break it.

We will further call the subgroup $\langle U2, D2, F, B, L, R\rangle$ Subgroup 1. How do we find out how to get into Subgroup 1?

There are 12 edge cubies, which, if you take the cube apart and assemble it, can be oriented $2^{12} = 4096$ different ways. Due to the cube's laws, only half of these orientations are reachable through legal moves. This means that there are only 2 048 different orientation combinations.

Of course, not only edge orientations change as we turn the cube. The cubies also travel and turn all around the surface. But at this stage, these other things don't interest us. Right now, we should be laser-focused on this one particular aspect. When we were probing the padlock for the correct position of the first dial, we didn't pay attention to the other ones. From the shackle's perspective, the other dials don't exist until you solve the first one. So would could as well cover them with the painter's tape to focus on the first one.

We can do a similar thing with the cube. Let's take a piece of painter's tape and cover all the cubies' stickers with it. Then let's put new images on the edge cubies. The F and B facets of all the edge cubies get a purple sticker, and the R and L facets get a teal one. The U and D facets of the edge cubies get the opposite of what it is on their other sticker. The solved cube would look like this:

To get us into Subgroup 1, we would just need to solve this simpler cube. And this is something we can just do with extensive search in a smaller graph, only containing 2 048 vertices.

There are several algorithms that can find the shortest path in a graph. Of them, the breadth-first search is the most simple one, although it's usually the most memory-demanding. We're working with SQL, though, which is not shy of storing data.

For this task, we will encode the states of the edge orientations with numbers 0 and 1. We will start from the solved cube (all 0's). For the first step we will see what happens one turn away from the solved state, and there are 18 ways we can do that. These turns will takes us to the new cube states. For these new states, we will know that there is a one-turn sequence which can bring us back to solved.

Some of these moves (F, B, L, R, their inverses and squares, and also U2 and D2) will get us back to the solved state. We don't really need any moves to get us back to where we were, so these sequences we will discard.

Other moves will get us to a new state, materially different from the solved one. We just learned something new about these states: to get from these states back to solved, we need exactly one move, the inverse of what we just did. Since it's really hard to compete with one-turn, we can be sure that it's the optimal path. There will be some duplicates: $U$ and $u$ are really the same move, as long as the edge orientations are concerned. We don't need the duplicates either, so we will toss them as well. We will be left with a list of new edge orientation states and sequences of one-turn moves that have lead to them.

Starting from these new sequences, we continue our search. To every sequence, we will append all of the moves in our inventory and see where they will lead us. Sometimes, they will lead us back to the solved state, or back to some state we saw earlier. Since everything that we saw earlier required less turns to get there (otherwise we wouldn't see it), this new sequence is not optimal. We will discard it and repeat our search.

On each stage $N$ of this algorithm, we will have an ever-growing table of states. With each state comes a sequence of $N$ or less turns. It may seem that this list of states would be exponentially increasing on every step of the algorithm, but it's not. As we travel about the graph, we remember where we already have been, how many turns it got us to get there, and make sure not to take the same route twice. At some point the duplicates will start to outnumber new solutions. On a certain step of the algorithm we won't be able to add anything new into the lookup table: we will already have seen it all. This is our cue to stop searching and return the results.

Applying the same transformation to a recordset in a loop is something that recursive CTE's lend themselves naturally to. So let's try to implement it.

First, we will need to code states and turns of the Rubik's cube. We will start with basic moves, and encode the permutations and orientation changes these moves make. PostgreSQL arrays are a good way to do this. We will also create a simple helper function to encode the group multiplication operation. This function will take two group elements, encoded as four arrays each, and return them as a single record with four arrays:

CREATE OR REPLACE FUNCTION turn(cornerPosition INT[], edgePosition INT[], cornerOrientation INT[], edgeOrientation INT[], cornerMove INT[], edgeMove INT[], cornerTurn INT[], edgeTurn INT[])
RETURNS TABLE
        (
        cornerPosition INT[],
        edgePosition INT[],
        cornerOrientation INT[],
        edgeOrientation INT[]
        )
AS
$$

SELECT  ARRAY
        (
        SELECT  cornerPosition
        FROM    UNNEST(cornerMove) AS move (source)
        ),
        ARRAY
        (
        SELECT  edgePosition
        FROM    UNNEST(edgeMove) AS move (source)
        ),
        ARRAY
        (
        SELECT  (cornerOrientation + cornerTurn[destination] + 3) % 3
        FROM    UNNEST(cornerMove) WITH ORDINALITY AS move (source, destination)
        ),
        ARRAY
        (
        SELECT  (edgeOrientation + edgeTurn[destination] + 2) % 2
        FROM    UNNEST(edgeMove) WITH ORDINALITY AS move (source, destination)
        );
$$
LANGUAGE 'sql'
STRICT
IMMUTABLE
PARALLEL SAFE
ROWS 1

Of course, using procedural code in SQL would be cheating. But this function is not procedural, it's just a little syntax sugar to help us with bulky expressions. We could easily make do without it, at expense of doing more typing.

With this function, we can define clockwise quarter-turns in query code and generate all other single turns from them:

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, reverse, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, initial, LOWER(initial),
                cornerMove, edgeMove, cornerTurn, edgeTurn
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, initial,
                CASE turns WHEN 1 THEN initial || '2' WHEN 2 THEN LOWER(initial) END,
                CASE turns WHEN 1 THEN initial || '2' WHEN 2 THEN initial END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        )
SELECT  move, reverse, cornerMove, edgeMove, cornerTurn, edgeTurn
FROM    moves

move	reverse	cornermove	edgemove	cornerturn	edgeturn
U	u	[4, 1, 2, 7, 3, 5, 6, 0]	[8, 1, 2, 11, 4, 5, 6, 7, 3, 9, 10, 0]	[2, 0, 0, 2, 1, 0, 0, 1]	[1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
D	d	[0, 5, 6, 3, 4, 2, 1, 7]	[0, 10, 9, 3, 4, 5, 6, 7, 8, 1, 2, 11]	[0, 2, 2, 0, 0, 1, 1, 0]	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0]
F	f	[0, 6, 2, 4, 1, 5, 3, 7]	[0, 1, 2, 3, 4, 9, 8, 7, 5, 6, 10, 11]	[0, 1, 0, 1, 2, 0, 2, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
B	b	[7, 1, 5, 3, 4, 0, 6, 2]	[0, 1, 2, 3, 11, 5, 6, 10, 8, 9, 4, 7]	[1, 0, 1, 0, 0, 2, 0, 2]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L	l	[5, 4, 2, 3, 0, 1, 6, 7]	[4, 5, 2, 3, 1, 0, 6, 7, 8, 9, 10, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
R	r	[0, 1, 7, 6, 4, 5, 2, 3]	[0, 1, 7, 6, 4, 5, 2, 3, 8, 9, 10, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
U2	U2	[3, 1, 2, 0, 7, 5, 6, 4]	[3, 1, 2, 0, 4, 5, 6, 7, 11, 9, 10, 8]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
D2	D2	[0, 2, 1, 3, 4, 6, 5, 7]	[0, 2, 1, 3, 4, 5, 6, 7, 8, 10, 9, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
F2	F2	[0, 3, 2, 1, 6, 5, 4, 7]	[0, 1, 2, 3, 4, 6, 5, 7, 9, 8, 10, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
B2	B2	[2, 1, 0, 3, 4, 7, 6, 5]	[0, 1, 2, 3, 7, 5, 6, 4, 8, 9, 11, 10]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
L2	L2	[1, 0, 2, 3, 5, 4, 6, 7]	[1, 0, 2, 3, 5, 4, 6, 7, 8, 9, 10, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
R2	R2	[0, 1, 3, 2, 4, 5, 7, 6]	[0, 1, 3, 2, 4, 5, 7, 6, 8, 9, 10, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
u	U	[7, 1, 2, 4, 0, 5, 6, 3]	[11, 1, 2, 8, 4, 5, 6, 7, 0, 9, 10, 3]	[2, 0, 0, 2, 1, 0, 0, 1]	[1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
d	D	[0, 6, 5, 3, 4, 1, 2, 7]	[0, 9, 10, 3, 4, 5, 6, 7, 8, 2, 1, 11]	[0, 2, 2, 0, 0, 1, 1, 0]	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0]
f	F	[0, 4, 2, 6, 3, 5, 1, 7]	[0, 1, 2, 3, 4, 8, 9, 7, 6, 5, 10, 11]	[0, 1, 0, 1, 2, 0, 2, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b	B	[5, 1, 7, 3, 4, 2, 6, 0]	[0, 1, 2, 3, 10, 5, 6, 11, 8, 9, 7, 4]	[1, 0, 1, 0, 0, 2, 0, 2]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
l	L	[4, 5, 2, 3, 1, 0, 6, 7]	[5, 4, 2, 3, 0, 1, 6, 7, 8, 9, 10, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
r	R	[0, 1, 6, 7, 4, 5, 3, 2]	[0, 1, 6, 7, 4, 5, 3, 2, 8, 9, 10, 11]	[0, 0, 0, 0, 0, 0, 0, 0]	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

This CTE returns the moves, their reverses and the group elements corresponding to these moves. Note the AS MATERIALIZED hint at the end of the CTE definition. We will be using this CTE a lot in joins, and it makes more sense to store it in an internal temp table rather than recalculate every time.

Next, we need to implement breadth-first search algorithm to find the sequences of moves leading to correct edge orientations. As I said above, we will be doing it in a recursive CTE.

We encode the solved state as string '000000000000'. For the anchor part of the CTE, we will select this solved state along with three more service fields:

WITH    g1s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '000000000000' AS edgeOrientation,
                ARRAY[]::TEXT[] AS moves
        )
SELECT  *
FROM    g1s

depth	distance	edgeorientation	moves
0	0	000000000000	[]

Now, let's do the breadth-first search part. We need to take all possible moves, apply them to the state and see what happens. To do this, we will cross join our anchor part with moves, do some array computations and append the results to the anchor part. For the sake of clarity, we are not doing the any recursive CTE's just yet and code everything explicitly.

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, bm.*
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, move,
                CASE turns + 1 WHEN 2 THEN initial || '2' WHEN 3 THEN LOWER(initial) END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        g1s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '000000000000' AS state,
                ARRAY[]::TEXT[] AS moves
        )
SELECT  distance, state, moves
FROM    g1s
UNION ALL
SELECT  distance + 1, newState, moves || move
FROM    g1s
CROSS JOIN
        moves
CROSS JOIN LATERAL
        (
        SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + edgeTurn[destination] + 2) % 2)::TEXT, '')
        FROM    UNNEST(edgeMove) WITH ORDINALITY AS move (source, destination)
        ) AS n1 (newState)

distance	state	moves
0	000000000000	[]
1	100100001001	['U']
1	011000000110	['D']
1	000000000000	['F']
1	000000000000	['B']
1	000000000000	['L']
1	000000000000	['R']
1	000000000000	['U2']
1	000000000000	['D2']
1	000000000000	['F2']
1	000000000000	['B2']
1	000000000000	['L2']
1	000000000000	['R2']
1	100100001001	['u']
1	011000000110	['d']
1	000000000000	['f']
1	000000000000	['b']
1	000000000000	['l']
1	000000000000	['r']

We see a lot of duplicates in the results. Most of them are from the previous (solved) stage with distance 0. Others are from the current stage. We will need to get rid of all of them. The former we will need to eliminate with a simple NOT IN construct. For the latter, we will use PostgreSQL's native DISTINCT ON construct. In other SQL dialects, we would need to use ROW_NUMBER and wrap it into an additional layer of nested views to be able to filter on it.

Here's how looks (again, without the recursion just yet):

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, bm.*
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, move,
                CASE turns + 1 WHEN 2 THEN initial || '2' WHEN 3 THEN LOWER(initial) END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        g1s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '000000000000' AS state,
                ARRAY[]::TEXT[] AS moves
        )
SELECT  distance, state, moves
FROM    g1s
UNION ALL
SELECT  DISTINCT ON (newState)
        distance + 1, newState, moves || move
FROM    g1s
CROSS JOIN
        moves
CROSS JOIN LATERAL
        (
        SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + edgeTurn[destination] + 2) % 2)::TEXT, '')
        FROM    UNNEST(edgeMove) WITH ORDINALITY AS move (source, destination)
        ) AS n1 (newState)
WHERE   newState NOT IN
        (
        SELECT  state
        FROM    g1s
        )

distance	state	moves
0	000000000000	[]
1	011000000110	['D']
1	100100001001	['U']

This means that the only meaningful moves that get the edge orientations out of the solved state are $D$ and $U$ . Of course, so do $d$ and $u$ , but they will lead to the same exact result, as far as Subgroup 1 is concerned, so we don't really need to clutter our solution table with them.

For the second pass of the algorithm (again, without recursion):

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, bm.*
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, move,
                CASE turns + 1 WHEN 2 THEN initial || '2' WHEN 3 THEN LOWER(initial) END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        g1s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '000000000000' AS state,
                ARRAY[]::TEXT[] AS moves
        ),
        pass1 AS
        (
        SELECT  distance, state, moves
        FROM    g1s
        UNION ALL
        SELECT  DISTINCT ON (newState)
                distance + 1, newState, moves || move
        FROM    g1s
        CROSS JOIN
                moves
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + edgeTurn[destination] + 2) % 2)::TEXT, '')
                FROM    UNNEST(edgeMove) WITH ORDINALITY AS move (source, destination)
                ) AS n1 (newState)
        WHERE   newState NOT IN
                (
                SELECT  state
                FROM    g1s
                )
        )
SELECT  distance, state, moves
FROM    pass1
UNION ALL
SELECT  DISTINCT ON (newState)
        distance + 1, newState, moves || move
FROM    pass1
CROSS JOIN
        moves
CROSS JOIN LATERAL
        (
        SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + edgeTurn[destination] + 2) % 2)::TEXT, '')
        FROM    UNNEST(edgeMove) WITH ORDINALITY AS move (source, destination)
        ) AS n1 (newState)
WHERE   newState NOT IN
        (
        SELECT  state
        FROM    pass1
        )

distance	state	moves
0	000000000000	[]
1	011000000110	['D']
1	100100001001	['U']
2	000101001001	['U', 'L']
2	000110001001	['U', 'l']
2	001001000110	['D', 'l']
2	001010000110	['D', 'L']
2	010000010110	['D', 'r']
2	010000100110	['D', 'R']
2	010100000110	['D', 'R2']
2	010100001001	['U', 'L2']
2	011000000101	['D', 'B2']
2	011000001010	['D', 'F2']
2	011000010100	['D', 'B']
2	011000100010	['D', 'f']
2	011001000010	['D', 'F']
2	011010000100	['D', 'b']
2	100000011001	['U', 'R']
2	100000101001	['U', 'r']
2	100100000101	['U', 'F2']
2	100100001010	['U', 'B2']
2	100100011000	['U', 'b']
2	100100100001	['U', 'F']
2	100101000001	['U', 'f']
2	100110001000	['U', 'B']
2	101000000110	['D', 'L2']
2	101000001001	['U', 'R2']
2	111100001111	['U', 'D']

Now we're on to something! We are getting some really meaningful sequences that get us out of the solved state out into the wild, and no duplicates to boot. Note that the SELECT part of the query is almost a literal copy-paste of the CTE pass1.

Now we are ready to pack it into a real recursive CTE. There are three issues to consider.

First, to get rid of duplicates, we should drag the results of all passes through the recursion, not just the last one.

Second, we need to refer to the recursive part of the CTE in something other than a join, namely, in a NOT IN query. PostgreSQL won't let us do this straight away, but we can trick it by wrapping our recursive part in another layer of CTE (more on that later).

Third, we need to know when to stop. We could have written a stop condition by comparing the max distance with the current depth, but this, albeit possible, would require additional CTE trickery and make the query slow. We'll just take Dr. Thistlethwaite's word for this step requiring no more than 7 turns, and hardcode it into the query as a stop condition.

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, bm.*
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, move,
                CASE turns + 1 WHEN 2 THEN initial || '2' WHEN 3 THEN LOWER(initial) END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        g1s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '000000000000' AS state,
                ARRAY[]::TEXT[] AS moves
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g1s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 7
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        CROSS JOIN
                moves
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + edgeTurn[destination] + 2) % 2)::TEXT, '')
                FROM    UNNEST(edgeMove) WITH ORDINALITY AS move (source, destination)
                ) AS state (newState)
        WHERE   distance = depth - 1
                AND newState NOT IN
                (
                SELECT  state
                FROM    q q2
                )
                AND depth <= 7
        )
        )
SELECT  state, moves
FROM    g1s
WHERE   depth = 7

state	moves
000000000000	[]
011000000110	['D']
100100001001	['U']
000101001001	['U', 'L']
000110001001	['U', 'l']

111011110111	['U', 'R', 'F', 'l', 'U', 'd', 'F']
111011111110	['D', 'R', 'l', 'u', 'B', 'D', 'R2']
111111110110	['U', 'D', 'b', 'l', 'f', 'U', 'B2']
111111111001	['U', 'f', 'L', 'r', 'D', 'b', 'U']
111111111111	['D', 'B', 'F', 'U', 'l', 'r', 'd']

Digression: limitations or recursive CTE's

This is not exactly relevant to the main topic of the article, so if you're only here to see the Rubik's Cube solved, feel free to skip to the next chapter.

Recursive CTE's are a way to bring, well, recursion into a declarative language that SQL is. In fact, their existence is the crucial part for SQL being Turing complete.

In SQL, you can create functions and put the values of their variables into WHERE, LIMIT and some other clauses of SQL statements. You can treat the query SELECT * FROM mytable WHERE field1 = 2 as a function, which takes an integer (2) as an argument, and returns a resultset as a result. But if you squint hard enough, you can see how this query can also be treated as a function, which takes a resultset (mytable) as an argument and produces a resultset with the same set of fields as a result. Resultsets are not first-class citizens in SQL, so there is no real way to do this short of making dynamic SQL queries. Still, let us make this assumption and pretend that we can.

A recursive CTE takes form of WITH q AS (SELECT * FROM anchor UNION ALL SELECT * FROM f(q)). Here, f(q) is a function over a resultset. If you could actually pass a resultset into a function variable and use the variable in the FROM clause: SELECT * FROM _variable JOIN othertable, that would be it.

Now let's remember properties of UNION ALL and JOIN. If we union all two resultsets with $A$ and $B$ rows, respectively, in each, we get $A + B$ records back. If we cross join these two resultsets, we get $A\times B$ records back. UNION ALL distributes over JOIN: this means that these two queries:

SELECT * FROM a CROSS JOIN c UNION ALL SELECT * FROM b CROSS JOIN c

and

SELECT * FROM (SELECT * FROM a UNION ALL SELECT * FROM b) q CROSS JOIN c

are the same. Both queries return $(A + B)\times C$ records, which is the same as $A\times C + B\times C$ . In other words, we can treat UNION ALL as an addition of recordsets, and a JOIN as their multiplication.

Put in these terms, this CTE:

WITH q AS (SELECT * FROM anchor UNION ALL SELECT * FROM f(q))

returns

$anchor + f(anchor) + f(f(anchor)) + \ldots$

In this form, you can see how it can be useful to work with hierarchical tree structures: if $q$ stores records in a child-parent relationship and $f(q)$ means "children of records in $q$ ", then the recursive CTE would say: "give me $q$ , plus children of $q$ , plus children of children of $q$ , plus …". In other words, recursive CTE's help build transitive closures of binary relations.

That's one, undoubtedly the most common, way of using a recursive CTE, but not the only one possible. This $f(q)$ can be any old function, and most of my New Year posts make a good use of this fact.

But database developers are not fond of allowing any old functions in the recursive part, for a good reason. If you let people put anything they want into the recursive part, the database engine never knows when to terminate the query. At first glance, a good time to stop would be when f(q) returns an empty resultset. But people can program the function so that it returns a nonempty resultset when passed an empty one (say, like this: SELECT 1 EXCEPT SELECT id FROM q). Of course, the engine could check that on the next pass and stop when both $f(q)$ and $f(f(q))$ return empty resultsets. In other words, the empty resultset should be a fixpoint for the function $f(q)$ . Yet, SQL is not free of side effects, so a really nasty developer could make the code depend on time of day or something like that. Strictly speaking, the engine should apply the recursive part to the empty resultset over and over, in the vain hope that it will return something one day.

Different engines solve this problem differently. SQL Server, for instance, simply doesn't allow anything except inner joins in the recursive part of the expression. With this limitation, the arbitrary function composition series turns into a polynomial series, which is way more simple for the database engine to work with. In particular, the polynomial series can use depth-first search instead of breadth-first search, which will eventually yield the same result, and SQL Server puts this this fact to good use (see this old post of mine for details).

PostgreSQL is not that strict, but still makes some compromises.

First, it forcibly puts an end to this nonsense about empty record not being the fixpoint:

Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

So long as the working table is not empty, repeat these steps:

Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.

If, at some point, the recursive part returns no results, the query is considered done, period, by definition.

Second, people don't usually write non-terminating Turing machines in SQL, and the main use case of recursive CTE's is building good old transitive closures of adjacency lists. PostgreSQL kind of tries to put some safeguard against misusing the recursion. If you simply try to reuse the CTE name in the recursive part, or put it in a subquery or something, you will get an error. This limitation, however, is easily circumvented by wrapping the recursive part in another layer of CTE, so PostgreSQL lets you shoot yourself in the foot, if you insist hard enough.

This is exactly why we had to do that in the previous query.

Subgroup 2

This subgroup, $\langle U2, D2, F2, R2, L, R\rangle$ , is generated by half-turns on all faces except $L$ and $R$ . To get into this subgroup from an arbitrary point in Subgroup 1 (meaning to get to the state which leads to the solved state using only Subgroup 2 turns), we might still need to make $F$ and $B$ , although not $U$ or $D$ .

The principle is the same as on the previous step, although the index of Subgroup 2 in respect to its immediate supergroup, Subgroup 1, is the largest in this algorithm, and equals to 1 082 656. It means that if we take all states of the cube with correct orientations of the edges, and see which states are reachable from each other using only half-turns on U/D and F/R, you will find that there are more than a million disjoint sets of states.

In terms of padlock analogy, if you limit the turns to the last three dials out of five, you can never reach 12345 from 00000, but you can from 12000. You can see that there are 100 different sets of padlock states (corresponding to the 100 different combinations of the first two dials), which are not reachable from each other no matter what you do with the last three dials. Each of these sets is called a coset of the last three dials subgroup, and is identified by the first two digits. To get into the right coset, you will first need to identify the first two dials and lock them in place, otherwise you can turn the last three dials till your fingers get numb and still not get anywhere. The cube works in a similar way.

Let's remember the definition of the corner cubies' orientations. A corner cubie is oriented correctly if its L/R facet is aligned with the L/R faces of the cube (it can be on the same side or the opposite, it doesn't matter). We can see that L or R turns can't change corner cubies' orientations, because the facets which are currently on the L or R faces, stay there after any number of L or R turns. Half-turns of the other faces can't change corner orientations either, because all they can do is bring the L facet to the R side or vice versa. It means that if we start from the solved state and refrain from making quarter-turns on U/D or F/B, we cannot break corner orientations. So any cube state in the same coset as the solved state will have all the corners oriented correctly.

Now look at the edge cubies in the middle layer between the L and R facets (that is the cubies numbered from 8 through 11). Quarter-turns (or any other turns) on L and R don't affect them at all. Half-turns on other faces may move them, but they will stay in that middle layer. Using the same logic as before, Subgroup 2 moves starting from the solved state won't be able to kick the middle-layer edges out of the middle layer. It means that if we have a middle-layer edge outside the middle layer, we're in the wrong coset.

So here's the rule to tell if we're in the right coset of Subgroup 2: all corners are oriented correctly, and all middle-layer cubies (8, 9, 10, 11) are in the middle layer (on positions 8, 9, 10, 11). Since by this time we have all the edges oriented correctly and not making any quarter-turns on U and D, the edge orientation will remain correct, so we don't have to pay attention to it.

What happens with the cube state outside the aspect we're working with, does not interest us just yet. As on the previous pass, we can cover all the facets with painter's tape. Then, we would paint the centers of L and R facets purple, and so we would the L/R facets of all the corner cubies; all the middle-layer edge cubies we would paint pink. If we can get all the purple stickers on the faces opposite to each other, and all the pink stickers on the middle layer between the purple faces, we're done for this step.

The Subgroup 2 aspect of the cube would look like this:

We encode the part of cube's state that interests us in a 20-character string. The first 8 characters are the corner cubies' orientations (which can be 0, 1 or 3), the last 12 are the edge cubies. The solved state looks like this: '000000000000001111'. The 8 cubies outside the middle layer are indistinguishable from each other to us, so we mark all them with 0's, and so are those in the middle layer, which we mark with 1's. As soon as all the 1's are at the end of the string, we're good.

Here's the CTE to build the list of moves to get into the solution coset:

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, bm.*
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, move,
                CASE turns + 1 WHEN 2 THEN initial || '2' WHEN 3 THEN LOWER(initial) END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        g2s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '00000000000000001111' AS state,
                ARRAY[]::TEXT[] AS moves
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g2s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 10
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        JOIN    moves
        ON      move NOT IN ('U', 'u', 'D', 'd')
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + cornerTurn[destination] + 3) % 3)::TEXT, '')
                FROM    UNNEST(cornerMove) WITH ORDINALITY AS move (source, destination)
                ) AS q1 (newCornerOrientation)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 9 FOR 1), '')
                FROM    UNNEST(edgeMove) AS move (source)
                ) AS q2 (newMiddleEdgePosition)
        CROSS JOIN LATERAL
                (
                SELECT  newCornerOrientation || newMiddleEdgePosition
                ) AS q3 (newState)
        WHERE   distance = depth - 1
                AND depth <= 10
                AND newState NOT IN
                (
                SELECT  state
                FROM    q
                )
        )
        )
SELECT  state, moves
FROM    g2s
WHERE   depth = 10

state	moves
00000000000000001111	[]
01012020000001100011	['F']
10100202000010011100	['B']
00112200000001100101	['F', 'D2']
00112200000010010101	['B', 'U2']

22222221000001001110	['B', 'R2', 'l', 'B', 'R', 'F', 'U2', 'f', 'l', 'B']
22222221000001010110	['F', 'L2', 'R', 'D2', 'b', 'R2', 'B2', 'R', 'F', 'R']
22222221000010000111	['B', 'R', 'D2', 'L', 'U2', 'R2', 'F', 'r', 'D2', 'B']
22222221000010001011	['F', 'r', 'B', 'D2', 'b', 'l', 'r', 'F', 'l', 'U2']
22222221000010011100	['B', 'U2', 'D2', 'r', 'F2', 'r', 'L2', 'F', 'R', 'B']

The results of this query are trimmed for readability, but it returns 1 082 656 records (one per coset of Subgroup 2) and takes about 4 minutes to complete on my machine.

Subgroup 3

Let me quote another excerpt from Dr. Thistlethwaite's letter:

Getting from G2 into G3. This is the trickiest stage theoretically, and may be broken down for purposes of clarification into two sub-stages: first get corners into their natural orbits, and second permute the corners within their orbits so as to obtain one of the 96 corner permutations in the squares group (G3), while at the same time sorting out the edge pieces into their correct slices.

Boy is this stage tricky! Unlike the previous stages, which are easy-ish to understand, and straightforward to encode, this one is neither of these things.

Subgroup 3 is half-turns only. What exactly happens when we ban quarter-turns altogether?

First. On the previous pass, we fixed the L/R middle-layer edges in their own layer. We had left some quarter-turns allowed, so other the edge pieces could still move between then U/D layer and the F/R layer. Not anymore! By banning the quarter-turns, we fix all the edges in their respective layers.

Second. Let's look at the corner cubies. We can see that some of them are connected by face diagonals (like 1 and 2), the others by vertices (like 1 and 5), and still others by main diagonals (like 0 and 6). 0, 1, 2 and 3 are connected by diagonals, and so are 4, 5, 6 and 7. Every pair of corner cubies between these two sets are connected either by vertices, or by main diagonals. 0, 1, 2 and 3 form a tetrahedron, as well as their twins in the other set. If we look closer, we can see that half-turns can only move corner cubies through face diagonals, but not through vertices or main diagonals. It means that once a corner cubie gets into either of the two tetrahedra formed by the corners, it will stay there if only half-turns are allowed. These two tetrahedra are exactly what Dr. Thistlethwaite calls "natural orbits". We need to get corner cubies 1, 2, 3 and 4 into slots 1, 2, 3 and 4 (regardless of the order).

The third stage is the trickiest part of all the algorithm. Once cubies 1, 2, 3 and 4 get into their natural orbit, 4, 5, 6 and 7 will follow suit. There are 24 possible permutations of the cubies in the first orbit, and 24 in the second, for the total of 576 combinations of corner cubies in their natural orbits. However, only 96 of them, or one out of six, are in Subgroup 3.

If the cubies in the first orbit are on their own places: $0, 1, 2, 3$ , then the second orbit can be any of:

$4, 5, 6, 7$
$5, 4, 7, 6$
$6, 7, 4, 5$
$7, 6, 5, 4$

, but not any other permutation. All other permutations are outside Subgroup 3 and cannot be solved by half-turns only. Every other permutation of orbit 1 also defines the four permutations on the orbit 2 that can go with it. Since only 4 out of 4! = 24 possible permutations are good, it means that there is an additional factor of 6 we need to account for.

It looks like this time a piece of painter's tape and a Sharpie ain't gonna cut it. In order to be using the same approach as before, we would need to identify this factor and make sure that it is calculatable from the state, persists during the turns and ends up in the lookup table.

This question has bothered minds brighter than mine. Here's a list (far from being complete) of resources I consulted while writing this post:

I spent a great deal of time figuring out how to implement a good mapping scheme that would, first, map all possible Subgroup 2 states into 29 600 cosets of Subgroup 3, and, second, would allow to make transformations of the image itself using just corner and edge permutation rules, to no avail. It looks like this is not a trivial task. One suggestion provided by Jaap in the answers would be "temporarily solve the corner cubies", which would mean making another graph search once per cube state. This, however, would most probably come at great computational price, which is, to be honest, not something SQL is good at.

One common way to deal with in is to extend the mapping, allowing multiple states from the same coset to map to different entries.

In Drew Finnis's solution, the test for Subgroup 3 requires all corners to be in their correct spots, which is a stronger condition than needed, so his pruning table for Subgroup 3 is almost 3 million records in size (because he tries to reach one particular corner permutation in Subgroup 3, while reaching any of the valid 96 would suffice).

Stefan Pochmann's entry for Tomas Rokicki's cube solvers contest also cuts some corners:

There's only one difference to the original algorithm, namely in phase 3 my subgoal is more restrictive. I could not find out a nice way to determine the "tetrad twists", instead I split up the tetrads in half to get the four groups UFR+UBL, DFL+DBR, URB+ULF and DRF+DLB. Getting the edges in their correct slices, the corners in their correct pair groups and ensuring overall even parity results in a cube solvable by phase 4.

Now that we're in good company, let's generate a larger than needed lookup table for Subgroup 3 as well.

In each orbit, there are six "twists", or classes of corner permutations. There are four possible permutations in each twist. For instance, one of the twists has the following permutations:

$0, 1, 2, 3$
$1, 0, 3, 2$
$2, 3, 0, 1$
$3, 2, 1, 0$

and another one has these:

$0, 1, 3, 2$
$1, 0, 2, 3$
$2, 3, 1, 0$
$3, 2, 0, 1$

We can identify the twist by the last three elements of the permutation with 0 in the first position. The first twist is "123", and the second one is "123".

To be in Subgroup 3, both orbits should have the same twist (modulo 4).

As an example, let's look at this combination of corner cubies:

$3, 0, 2, 1, 7, 6, 4, 5$

The first orbit's permutation is $3, 0, 2, 1$ , which is in the same twist as $0, 3, 1, 2$ . So we say that the first orbit has twist "312".

The second orbit's permutation is $7, 6, 4, 5$ , which is in the same twist as $4, 5, 7, 6$ (or $0, 1, 3, 2$ modulo 4). The two orbits have different twists, so this combination is not in Subgroup 3 and cannot be solved using only half-moves.

Let's look at another combination:

$2, 3, 1, 0, 5, 4, 6, 7$

The first orbit's twist is "132", which the second one's is "576" ("132" modulo 4). The twists are the same, and the combination is in Subgroup 3.

We can notice that if we have a combination of moves which bring corners to the Subgroup 3, this combination will work on all permutations with the same twist. If some series of turns fixes corners $3, 2, 1, 0$ on certain positions, we can put the corners $0, 1, 2, 3$ or $1, 0, 3, 2$ , or $2, 3, 0, 1$ on the same positions, and it will fix them as well. It also works on the second orbit. In other words, if we find a series of turns to fix a certain position of corners, the same series will work on all 16 other positions with the same orbit twists.

We can come up with a canonical representation for all these 16 positions and use it in the lookup table. Here's how it works.

Let's say we have the corners arranged this way: $2, 6, 4, 5, 1, 3, 0, 7$

Split the corners by the orbit: $\fbox{2}\ \textcircled{6} \ \textcircled{4} \ \textcircled{5} \ \fbox{1} \ \fbox{3} \ \fbox{0} \ \textcircled{7}$ . The first orbit is in boxes, the second in circles
The first orbit's corners, in the arrangement order, are $2, 1, 3, 0$ . Permute them within the twist so that 0 is leading: $0, 3, 1, 2$
The second orbit's corners, in the arrangement order, are $6, 4, 5, 7$ . Permute them within the twist so that 4 is leading: $4, 6, 7, 5$
Put them back into their places in the new order. First orbit's corners go into boxes, second orbit's into circles: $\fbox{0}\ \textcircled{4} \ \textcircled{6} \ \textcircled{7} \ \fbox{3} \ \fbox{1} \ \fbox{2} \ \textcircled{5}$
All sixteen permutations within two orbits' twists will be mapped into the same value. The value preserves both orbits' positions and twists, so we can calculate the moves right on the canonical value, and re-canonicalize it after the moves are applied

Let's create a helper function to canonicalize the corner positions. Again, this function is not procedural and only saves us some typing:

CREATE OR REPLACE FUNCTION twist(state TEXT)
RETURNS TEXT
AS
$$

WITH    perms (perm, i) AS
        (
        VALUES
        (ARRAY[0, 1, 2, 3], 1),
        (ARRAY[1, 0, 3, 2], 2),
        (ARRAY[2, 3, 0, 1], 3),
        (ARRAY[3, 2, 1, 0], 4)
        )
SELECT  targetState
FROM    (
        VALUES
                (
                ARRAY
                (
                SELECT  value::INT
                FROM    STRING_TO_TABLE(state, NULL) value
                WHERE   value::INT <= 3
                ),
                ARRAY
                (
                SELECT  value::INT
                FROM    STRING_TO_TABLE(state, NULL) value
                WHERE   value::INT > 3
                )
                )
        ) orbits (orbit1, orbit2)
CROSS JOIN LATERAL
        (
        SELECT  ARRAY_AGG(orbit1[index + 1])
        FROM    perms
        CROSS JOIN LATERAL
                UNNEST(perm) index
        WHERE   i = ARRAY_POSITION(orbit1, 0)
        ) c1 (permuted1)
CROSS JOIN LATERAL
        (
        SELECT  ARRAY_AGG(orbit2[index + 1])
        FROM    perms
        CROSS JOIN LATERAL
                UNNEST(perm) index
        WHERE   i = ARRAY_POSITION(orbit2, 4)
        ) c2 (permuted2)
CROSS JOIN LATERAL
        (
        SELECT  STRING_AGG(corner::TEXT, NULL ORDER BY slot)
        FROM    (
                SELECT  corner, position
                FROM    UNNEST(permuted1) WITH ORDINALITY u (corner, position)
                UNION ALL
                SELECT  corner, position + 4
                FROM    UNNEST(permuted2) WITH ORDINALITY u (corner, position)
                ) corners (corner, cornerPosition)
        JOIN    (
                SELECT  position - 1 AS slot,
                        ROW_NUMBER() OVER (ORDER BY corner::INT / 4, position) AS cornerPosition
                FROM    STRING_TO_TABLE(state, NULL) WITH ORDINALITY st (corner, position)
                ) slots (slot, cornerPosition)
        USING   (cornerPosition)
        ) ts (targetState)

$$
LANGUAGE 'sql'
IMMUTABLE
STRICT

We can now use this function in a CTE to build the lookup table to get from Subgroup 2 to Subgroup 3. We don't account for the twist factor of 6, so we have 6 times as many states as we theoretically need. Unlike the other CTE, we initialize our table with 6 different initial positions. This won't help us keep it size down, but it will reduce the average number of moves.

After two or so minutes of heavy number crunching, we get the lookup table for Subgroup 3:

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, bm.*
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, move,
                CASE turns + 1 WHEN 2 THEN initial || '2' WHEN 3 THEN LOWER(initial) END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        g3s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                corners || '000011112222' AS state,
                ARRAY[]::TEXT[] AS moves
        FROM    (
                VALUES
                ('01234567'),
                ('01324576'),
                ('02134657'),
                ('02314675'),
                ('03124756'),
                ('03214765')
                ) o2 (corners)
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g3s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 13
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        JOIN    moves
        ON      move NOT IN ('U', 'u', 'D', 'd', 'F', 'f', 'B', 'b')
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 1 FOR 1), '')
                FROM    UNNEST(cornerMove) AS source
                ) AS q1 (newCornerPosition)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 9 FOR 1), '')
                FROM    UNNEST(edgeMove) AS source
                ) AS q2 (newEdgeLayerPosition)
        CROSS JOIN LATERAL
                twist(newCornerPosition) AS twistedCornerPosition
        CROSS JOIN LATERAL
                (
                SELECT  twistedCornerPosition || newEdgeLayerPosition
                ) q3 (newState)
        WHERE   distance = depth - 1
                AND depth <= 13
                AND newState NOT IN
                (
                SELECT  q.state
                FROM    q
                )
        )
        )
SELECT  state, moves
FROM    g3s
WHERE   depth = 13

state	moves
01234567000011112222	[]
01324576000011112222	[]
02134657000011112222	[]
02314675000011112222	[]
03124756000011112222	[]

47650123101010012222	['R', 'B2', 'r', 'B2', 'L2', 'D2', 'R', 'U2', 'r', 'D2', 'R2', 'F2', 'r']
47650231011001012222	['R', 'F2', 'D2', 'F2', 'U2', 'R2', 'F2', 'l', 'U2', 'R2', 'B2', 'R', 'B2']
47650231011010102222	['R', 'F2', 'D2', 'F2', 'U2', 'R2', 'F2', 'l', 'U2', 'R2', 'B2', 'R', 'F2']
47650231100101012222	['R', 'U2', 'L', 'D2', 'L2', 'B2', 'r', 'D2', 'L', 'U2', 'R2', 'F2', 'R']
47650231100110102222	['R', 'B2', 'R2', 'U2', 'l', 'F2', 'r', 'F2', 'B2', 'r', 'B2', 'r', 'B2']

Subgroup 4 (identity)

The final stage is very straightforward: get from Subgroup 3 to identity (a trivial subgroup of every group consisting only of the identity element). It corresponds to the solved state. The states are very simple to encode: there is no hashing or anything, every single bit or exact positions and orientations of all the cubies matters.

There are 600-something thousands elements in Subgroup 3, and this is what the size of the lookup table for the final stage will be.

Here's the CTE:

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, bm.*
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, move,
                CASE turns + 1 WHEN 2 THEN initial || '2' WHEN 3 THEN LOWER(initial) END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        g4s (depth, distance, state, moves) AS MATERIALIZED
        (
        SELECT  0, 0, '012345670123456789AB', ARRAY[]::TEXT[]
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g4s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 15
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        JOIN    moves
        ON      turns = 2
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 1 FOR 1), '')
                FROM    UNNEST(cornerMove) AS source
                ) AS q1 (newCornerPositions)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 9 FOR 1), '')
                FROM    UNNEST(edgeMove) AS source
                ) AS q2 (newEdgePositions)
        CROSS JOIN LATERAL
                (
                SELECT  newCornerPositions || newEdgePositions
                ) AS q3 (newState)
        WHERE   distance = depth - 1
                AND depth <= 15
                AND newState NOT IN
                (
                SELECT  q.state
                FROM    q
                )
        )
        )
SELECT  state, moves
FROM    g4s
WHERE   depth = 15

state	moves
012345670123456789AB	[]
013245760132457689AB	['R2']
02134657021345678A9B	['D2']
032165470123465798AB	['F2']
102354671023546789AB	['L2']

320176451032547689AB	['L2', 'B2', 'U2', 'L2', 'B2', 'D2', 'L2', 'R2', 'B2', 'U2', 'F2', 'U2', 'R2', 'U2', 'B2']
3201764523016745AB89	['L2', 'D2', 'L2', 'D2', 'B2', 'R2', 'U2', 'F2', 'D2', 'L2', 'F2', 'L2', 'B2', 'F2', 'U2']
3201764523017654AB89	['U2', 'R2', 'F2', 'L2', 'U2', 'F2', 'U2', 'R2', 'U2', 'D2', 'F2', 'D2', 'L2', 'D2', 'L2']
3201764532106745AB89	['B2', 'U2', 'L2', 'F2', 'R2', 'D2', 'F2', 'L2', 'D2', 'B2', 'F2', 'L2', 'D2', 'R2', 'D2']
3201764532107654AB89	['R2', 'F2', 'U2', 'R2', 'U2', 'B2', 'U2', 'B2', 'U2', 'F2', 'L2', 'U2', 'L2', 'R2', 'B2']

Solving the cube

Now, let's put all the pieces of the solution together.

Here is what we are going to do:

Take a series of moves to shuffle the cube
By sequentially applying the moves, put the cube into the shuffled state
Encode the cube's state the way the Subgroup 1 lookup CTE expects it to be and look it up in the materialized output of the Subgroup 1's CTE
Inverse the moves from the lookup table (both the order of turns and their direction) to get to Subgroup 2 state
Repeat the steps for each of the next subgroups. Unlike the padlock puzzle, cube's subgroups are not normal, meaning that the order in which we move to each subgroup matters. Had they been they normal, we could have encoded the source state, look it up in all the four CTE's with simple joins and combine the moves in any order. Instead, we will need to do this sequentially and only in correct order (Subgroup 1 first, then Subgroup 2 etc.)
Concatenate the series of reversed moves from each state, and we're done!

Note that every time we run this query, the lookup tables are being regenerated from scratch (which is only fair, considering that we want to do this in a single query with no saved data whatsoever). It takes some time (about 7 minutes on my machine).

Here's a series of moves to shuffle the cube:

$L2\ d\ U\ F2\ U\ F2\ D\ B\ f\ D\ f\ l\ B2\ f\ R2\ F2\ r\ F\ D2\ l\ U\ L\ R2\ f\ D2\ F\ d$

Let's try to solve it in SQL! That's what we get:

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, reverse, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, initial, LOWER(initial),
                cornerMove, edgeMove, cornerTurn, edgeTurn
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, initial,
                CASE turns WHEN 1 THEN initial || '2' WHEN 2 THEN LOWER(initial) END,
                CASE turns WHEN 1 THEN initial || '2' WHEN 2 THEN initial END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        solved (cornerPosition, edgePosition, cornerOrientation, edgeOrientation) AS MATERIALIZED
        (
        VALUES
                (
                ARRAY(SELECT v FROM GENERATE_SERIES(0, 7) v), ARRAY(SELECT v FROM GENERATE_SERIES(0, 11) v),
                ARRAY(SELECT 0 FROM GENERATE_SERIES(0, 7)), ARRAY(SELECT 0 FROM GENERATE_SERIES(0, 11))
                )
        ),
        sequence (turns) AS
        (
        VALUES
        ('L2 d U F2 U F2 D B f D f l B2 f R2 F2 r F D2 l U L R2 f D2 F d')
        ),
        turns (move, i) AS MATERIALIZED
        (
        SELECT  turn.*
        FROM    sequence
        CROSS JOIN LATERAL
                STRING_TO_TABLE(turns, ' ') WITH ORDINALITY AS turn (move, i)
        ),
        scramble (cornerPosition, edgePosition, cornerOrientation, edgeOrientation, currentMove, i) AS MATERIALIZED
        (
        SELECT  cornerPosition, edgePosition, cornerOrientation, edgeOrientation,
                NULL,
                1::BIGINT AS i
        FROM    solved
        UNION ALL
        SELECT  newValues.*,
                move,
                turns.i + 1
        FROM    scramble e
        JOIN    turns
        USING   (i)
        JOIN    moves
        USING   (move)
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        unsolved AS MATERIALIZED
        (
        SELECT  cornerPosition, edgePosition, cornerOrientation, edgeOrientation
        FROM    scramble
        ORDER BY
                i DESC
        LIMIT   1
        ),
        g1s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '000000000000' AS state,
                ARRAY[]::TEXT[] AS moves
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g1s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 7
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        CROSS JOIN
                moves
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + edgeTurn[destination] + 2) % 2)::TEXT, '')
                FROM    UNNEST(edgeMove) WITH ORDINALITY AS move (source, destination)
                ) AS state (newState)
        WHERE   distance = depth - 1
                AND newState NOT IN
                (
                SELECT  state
                FROM    q q2
                )
                AND depth <= 7
        )
        ),
        g2s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                '00000000000000001111' AS state,
                ARRAY[]::TEXT[] AS moves
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g2s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 10
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        JOIN    moves
        ON      move NOT IN ('U', 'u', 'D', 'd')
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(((SUBSTRING(state FROM source + 1 FOR 1)::INT + cornerTurn[destination] + 3) % 3)::TEXT, '')
                FROM    UNNEST(cornerMove) WITH ORDINALITY AS move (source, destination)
                ) AS q1 (newCornerOrientation)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 9 FOR 1), '')
                FROM    UNNEST(edgeMove) AS move (source)
                ) AS q2 (newMiddleEdgePosition)
        CROSS JOIN LATERAL
                (
                SELECT  newCornerOrientation || newMiddleEdgePosition
                ) AS q3 (newState)
        WHERE   distance = depth - 1
                AND depth <= 10
                AND newState NOT IN
                (
                SELECT  state
                FROM    q
                )
        )
        ),
        g3s AS MATERIALIZED
        (
        SELECT  0 AS depth, 0 AS distance,
                corners || '000011112222' AS state,
                ARRAY[]::TEXT[] AS moves
        FROM    (
                VALUES
                ('01234567'),
                ('01324576'),
                ('02134657'),
                ('02314675'),
                ('03124756'),
                ('03214765')
                ) o2 (corners)
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g3s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 13
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        JOIN    moves
        ON      move NOT IN ('U', 'u', 'D', 'd', 'F', 'f', 'B', 'b')
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 1 FOR 1), '')
                FROM    UNNEST(cornerMove) AS source
                ) AS q1 (newCornerPosition)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 9 FOR 1), '')
                FROM    UNNEST(edgeMove) AS source
                ) AS q2 (newEdgeLayerPosition)
        CROSS JOIN LATERAL
                twist(newCornerPosition) AS twistedCornerPosition
        CROSS JOIN LATERAL
                (
                SELECT  twistedCornerPosition || newEdgeLayerPosition
                ) q3 (newState)
        WHERE   distance = depth - 1
                AND depth <= 13
                AND newState NOT IN
                (
                SELECT  q.state
                FROM    q
                )
        )
        ),
        g4s (depth, distance, state, moves) AS MATERIALIZED
        (
        SELECT  0, 0, '012345670123456789AB', ARRAY[]::TEXT[]
        UNION ALL
        (
        WITH    q AS
                (
                SELECT  depth + 1 AS depth, distance, state, moves
                FROM    g4s
                )
        SELECT  *
        FROM    q
        WHERE   depth <= 15
        UNION ALL
        SELECT  DISTINCT ON (newState)
                depth, distance + 1, newState, moves || move
        FROM    q
        JOIN    moves
        ON      turns = 2
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 1 FOR 1), '')
                FROM    UNNEST(cornerMove) AS source
                ) AS q1 (newCornerPositions)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(SUBSTRING(state FROM source + 9 FOR 1), '')
                FROM    UNNEST(edgeMove) AS source
                ) AS q2 (newEdgePositions)
        CROSS JOIN LATERAL
                (
                SELECT  newCornerPositions || newEdgePositions
                ) AS q3 (newState)
        WHERE   distance = depth - 1
                AND depth <= 15
                AND newState NOT IN
                (
                SELECT  q.state
                FROM    q
                )
        )
        ),
        g1 AS MATERIALIZED
        (
        SELECT  state, moves
        FROM    g1s
        WHERE   depth = 7
        ),
        g2 AS MATERIALIZED
        (
        SELECT  state, moves
        FROM    g2s
        WHERE   depth = 10
        ),
        g3 AS MATERIALIZED
        (
        SELECT  state, moves
        FROM    g3s
        WHERE   depth = 13
        ),
        g4 AS MATERIALIZED
        (
        SELECT  state, moves
        FROM    g4s
        WHERE   depth = 15
        ),
        g1Entry AS
        (
        SELECT  g1.state, moves
        FROM    (
                SELECT  STRING_AGG(edge::TEXT, '') AS state
                FROM    unsolved
                CROSS JOIN LATERAL
                        UNNEST(edgeOrientation) edge
                ) q
        JOIN    g1
        USING   (state)
        ),
        g1Moves AS MATERIALIZED
        (
        SELECT  u.*, moves, NULL::TEXT AS move
        FROM    unsolved u
        CROSS JOIN
                g1Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g1Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        g2Entry AS
        (
        SELECT  g1Moves.cornerPosition, g1Moves.edgePosition, g1Moves.cornerOrientation, g1Moves.edgeOrientation,
                g2.moves
        FROM    (
                SELECT  *
                FROM    g1Moves
                WHERE   moves = ARRAY[]::TEXT[]
                ) g1Moves
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(value::TEXT, '')
                FROM    UNNEST(cornerOrientation) AS value
                ) AS q (corners)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG((value >= 8)::INT::TEXT, '')
                FROM    UNNEST(edgePosition) AS value
                ) AS q2 (middleEdges)
        CROSS JOIN LATERAL
                (
                SELECT  corners || middleEdges
                ) AS q3 (state)
        JOIN    g2
        USING   (state)
        ),
        g2Moves AS MATERIALIZED
        (
        SELECT  *, NULL::TEXT AS move
        FROM    g2Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g2Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        g3Entry AS
        (
        SELECT  g2Last.cornerPosition, g2Last.edgePosition, g2Last.cornerOrientation, g2Last.edgeOrientation,
                g3.moves
        FROM    (
                SELECT  *
                FROM    g2Moves
                WHERE   moves = ARRAY[]::TEXT[]
                ) g2Last
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(value::TEXT, '')
                FROM    UNNEST(cornerPosition) AS value
                ) AS q (corners)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG((value / 4)::INT::TEXT, '')
                FROM    UNNEST(edgePosition) AS value
                ) AS q2 (layerEdges)
        CROSS JOIN LATERAL
                twist(corners) AS twistedCorners
        CROSS JOIN LATERAL
                (
                SELECT  twistedCorners || layerEdges
                ) AS q3 (state)
        JOIN    g3
        USING   (state)
        ),
        g3Moves AS MATERIALIZED
        (
        SELECT  *, NULL::TEXT AS move
        FROM    g3Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g3Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        g4Entry AS
        (
        SELECT  g3Last.cornerPosition, g3Last.edgePosition, g3Last.cornerOrientation, g3Last.edgeOrientation,
                g4.moves
        FROM    (
                SELECT  *
                FROM    g3Moves
                WHERE   moves = ARRAY[]::TEXT[]
                ) g3Last
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(value::TEXT, '')
                FROM    UNNEST(cornerPosition) AS value
                ) AS q (corners)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(UPPER(TO_HEX(value::INT)), '')
                FROM    UNNEST(edgePosition) AS value
                ) AS q2 (edges)
        CROSS JOIN LATERAL
                (
                SELECT  corners || edges
                ) AS q3 (state)
        JOIN    g4
        USING   (state)
        ),
        g4Moves AS MATERIALIZED
        (
        SELECT  *, NULL::TEXT AS move
        FROM    g4Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g4Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        )
SELECT  STRING_AGG(move, ' ') AS result
FROM    (
        SELECT  *
        FROM    g1Moves
        UNION ALL
        SELECT  *
        FROM    g2Moves
        UNION ALL
        SELECT  *
        FROM    g3Moves
        UNION ALL
        SELECT  *
        FROM    g4Moves
        ) q
WHERE   move <> ''

result
D R f d L B R F2 R L D2 f F2 R F2 D2 L B2 l U2 l F2 R2 F2 L2 U2 F2 D2 B2 L2 F2

The cube is solved!

This query is very long and boring to play with. This post's GitHub repository has a script to create and store lookup tables in the database. With these tables, solving the cubes becomes instant, less than 50 milliseconds on my machine.

You can use the stored tables if you want to play with the query:

WITH    RECURSIVE
        basicMoves (initial, cornerMove, edgeMove, cornerTurn, edgeTurn) AS
        (
        VALUES
                (
                'U',
                ARRAY[ 4,  1,  2,  7,  3,  5,  6,  0]::INT[],  ARRAY[ 8,  1,  2, 11,  4,  5,  6,  7,  3,  9, 10,  0]::INT[],
                ARRAY[ 2,  0,  0,  2,  1,  0,  0,  1]::INT[],  ARRAY[ 1,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  1]::INT[]
                ),
                (
                'D',
                ARRAY[ 0,  5,  6,  3,  4,  2,  1,  7]::INT[],  ARRAY[ 0, 10,  9,  3,  4,  5,  6,  7,  8,  1,  2, 11]::INT[],
                ARRAY[ 0,  2,  2,  0,  0,  1,  1,  0]::INT[],  ARRAY[ 0,  1,  1,  0,  0,  0,  0,  0,  0,  1,  1,  0]::INT[]
                ),
                (
                'F',
                ARRAY[ 0,  6,  2,  4,  1,  5,  3,  7]::INT[],  ARRAY[ 0,  1,  2,  3,  4,  9,  8,  7,  5,  6, 10, 11]::INT[],
                ARRAY[ 0,  1,  0,  1,  2,  0,  2,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'B',
                ARRAY[ 7,  1,  5,  3,  4,  0,  6,  2]::INT[],  ARRAY[ 0,  1,  2,  3, 11,  5,  6, 10,  8,  9,  4,  7]::INT[],
                ARRAY[ 1,  0,  1,  0,  0,  2,  0,  2]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'L',
                ARRAY[ 5,  4,  2,  3,  0,  1,  6,  7]::INT[],  ARRAY[ 4,  5,  2,  3,  1,  0,  6,  7,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                ),
                (
                'R',
                ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3]::INT[],  ARRAY[ 0,  1,  7,  6,  4,  5,  2,  3,  8,  9, 10, 11]::INT[],
                ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0]::INT[],  ARRAY[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]::INT[]
                )
        ),
        moves (turns, initial, move, reverse, cornerMove, edgeMove, cornerTurn, edgeTurn) AS MATERIALIZED
        (
        SELECT  1 AS turns, initial, initial, LOWER(initial),
                cornerMove, edgeMove, cornerTurn, edgeTurn
        FROM    basicMoves bm
        UNION ALL
        SELECT  turns + 1, initial,
                CASE turns WHEN 1 THEN initial || '2' WHEN 2 THEN LOWER(initial) END,
                CASE turns WHEN 1 THEN initial || '2' WHEN 2 THEN initial END,
                t.*
        FROM    moves am
        JOIN    basicMoves bm
        USING   (initial)
        CROSS JOIN LATERAL
                turn(am.cornerMove, am.edgeMove, am.cornerTurn, am.edgeTurn, bm.cornerMove, bm.edgeMove, bm.cornerTurn, bm.edgeTurn) t
        WHERE   turns <= 2
        ),
        solved (cornerPosition, edgePosition, cornerOrientation, edgeOrientation) AS MATERIALIZED
        (
        VALUES
                (
                ARRAY(SELECT v FROM GENERATE_SERIES(0, 7) v), ARRAY(SELECT v FROM GENERATE_SERIES(0, 11) v),
                ARRAY(SELECT 0 FROM GENERATE_SERIES(0, 7)), ARRAY(SELECT 0 FROM GENERATE_SERIES(0, 11))
                )
        ),
        sequence (turns) AS
        (
        VALUES
        ('L2 d U F2 U F2 D B f D f l B2 f R2 F2 r F D2 l U L R2 f D2 F d')
        ),
        turns (move, i) AS MATERIALIZED
        (
        SELECT  turn.*
        FROM    sequence
        CROSS JOIN LATERAL
                STRING_TO_TABLE(turns, ' ') WITH ORDINALITY AS turn (move, i)
        ),
        scramble (cornerPosition, edgePosition, cornerOrientation, edgeOrientation, currentMove, i) AS MATERIALIZED
        (
        SELECT  cornerPosition, edgePosition, cornerOrientation, edgeOrientation,
                NULL,
                1::BIGINT AS i
        FROM    solved
        UNION ALL
        SELECT  newValues.*,
                move,
                turns.i + 1
        FROM    scramble e
        JOIN    turns
        USING   (i)
        JOIN    moves
        USING   (move)
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        unsolved AS MATERIALIZED
        (
        SELECT  cornerPosition, edgePosition, cornerOrientation, edgeOrientation
        FROM    scramble
        ORDER BY
                i DESC
        LIMIT   1
        ),
        g1Entry AS
        (
        SELECT  g1.state, moves
        FROM    (
                SELECT  STRING_AGG(edge::TEXT, '') AS state
                FROM    unsolved
                CROSS JOIN LATERAL
                        UNNEST(edgeOrientation) edge
                ) q
        JOIN    g1stored g1
        USING   (state)
        ),
        g1Moves AS MATERIALIZED
        (
        SELECT  u.*, moves, NULL::TEXT AS move
        FROM    unsolved u
        CROSS JOIN
                g1Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g1Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        g2Entry AS
        (
        SELECT  g1Moves.cornerPosition, g1Moves.edgePosition, g1Moves.cornerOrientation, g1Moves.edgeOrientation,
                g2.moves
        FROM    (
                SELECT  *
                FROM    g1Moves
                WHERE   moves = ARRAY[]::TEXT[]
                ) g1Moves
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(value::TEXT, '')
                FROM    UNNEST(cornerOrientation) AS value
                ) AS q (corners)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG((value >= 8)::INT::TEXT, '')
                FROM    UNNEST(edgePosition) AS value
                ) AS q2 (middleEdges)
        CROSS JOIN LATERAL
                (
                SELECT  corners || middleEdges
                ) AS q3 (state)
        JOIN    g2stored g2
        USING   (state)
        ),
        g2Moves AS MATERIALIZED
        (
        SELECT  *, NULL::TEXT AS move
        FROM    g2Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g2Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        g3Entry AS
        (
        SELECT  g2Last.cornerPosition, g2Last.edgePosition, g2Last.cornerOrientation, g2Last.edgeOrientation,
                g3.moves
        FROM    (
                SELECT  *
                FROM    g2Moves
                WHERE   moves = ARRAY[]::TEXT[]
                ) g2Last
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(value::TEXT, '')
                FROM    UNNEST(cornerPosition) AS value
                ) AS q (corners)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG((value / 4)::INT::TEXT, '')
                FROM    UNNEST(edgePosition) AS value
                ) AS q2 (layerEdges)
        CROSS JOIN LATERAL
                twist(corners) AS twistedCorners
        CROSS JOIN LATERAL
                (
                SELECT  twistedCorners || layerEdges
                ) AS q3 (state)
        JOIN    g3stored g3
        USING   (state)
        ),
        g3Moves AS MATERIALIZED
        (
        SELECT  *, NULL::TEXT AS move
        FROM    g3Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g3Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        ),
        g4Entry AS
        (
        SELECT  g3Last.cornerPosition, g3Last.edgePosition, g3Last.cornerOrientation, g3Last.edgeOrientation,
                g4.moves
        FROM    (
                SELECT  *
                FROM    g3Moves
                WHERE   moves = ARRAY[]::TEXT[]
                ) g3Last
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(value::TEXT, '')
                FROM    UNNEST(cornerPosition) AS value
                ) AS q (corners)
        CROSS JOIN LATERAL
                (
                SELECT  STRING_AGG(UPPER(TO_HEX(value::INT)), '')
                FROM    UNNEST(edgePosition) AS value
                ) AS q2 (edges)
        CROSS JOIN LATERAL
                (
                SELECT  corners || edges
                ) AS q3 (state)
        JOIN    g4stored g4
        USING   (state)
        ),
        g4Moves AS MATERIALIZED
        (
        SELECT  *, NULL::TEXT AS move
        FROM    g4Entry
        UNION ALL
        SELECT  newValues.*, moves[:(ARRAY_LENGTH(moves, 1) - 1)], moves.move
        FROM    g4Moves
        JOIN    moves
        ON      reverse = moves[ARRAY_LENGTH(moves, 1)]
        CROSS JOIN LATERAL
                turn(cornerPosition, edgePosition, cornerOrientation, edgeOrientation, cornerMove, edgeMove, cornerTurn, edgeTurn) AS newValues
        )
SELECT  STRING_AGG(move, ' ') AS result
FROM    (
        SELECT  *
        FROM    g1Moves
        UNION ALL
        SELECT  *
        FROM    g2Moves
        UNION ALL
        SELECT  *
        FROM    g3Moves
        UNION ALL
        SELECT  *
        FROM    g4Moves
        ) q
WHERE   move <> ''

result
D R f d L B R F2 R L D2 f F2 R F2 D2 L B2 l U2 l B2 L2 F2 R2 D2 F2 U2 F2 L2 F2

You can view the queries here: https://github.com/quassnoi/explain-extended-2023

In this New Year, I wish you a large subgroup of good people. May your moves be smooth, colors bright and turns expected.

Happy New Year!

Previous New Year posts:

Written by Quassnoi

December 31st, 2022 at 11:00 pm

Posted in PostgreSQL

Tagged with PostgreSQL, Rubik's cube, SQL, Thistlethwaite's algorithm

One Response to 'Happy New Year: solving the Rubik’s Cube in SQL'

Subscribe to comments with RSS

I remember doing this on Oracle 9. I think your code is cleaner than mine, however.

Mine was expanded to 5x5x5 because there afterwords the types did not change.

Stirling S Newberry

13 Aug 23 at 03:17

EXPLAIN EXTENDED