This post is about some research Prof. Martin Kreuzer, at the Univ. of Passau, does which combines Grobner bases and solving permutation puzzles, such as the Rubik’s cube.

Non-commutative Grobner Bases and Twisty Puzzles was the title of his talk (the link takes you to his slides, which he kindly allowed me to post).

Grobner bases were introduced in the mid-1960s (by Bruno Buchberger and, independently, Heisuke Hironaka), but in hindsight it is amazing they weren’t invented earlier. Indeed, Grobner bases arise when one tried to generalize long division of polynomials in one variable to polynomials of several variables. Non-commutative Grobner bases arise when one does not allow the variables to commute with each other. The main setting is where
is a finitely presented monoid,
is a monoid ring, and where
is a two-sided ideal generated by binomials.

First, Prof. Kreuzer introduces the non-commutative analogs of term ordering, leading term, and Grobner basis with respect to that ordering.

After developing enough theory, it turns out that the word problem in group theory can be re-expressed in terms of the membership problem for .

Martin Kreuzer defines a twisty puzzle as a special form of a permutation puzzle. Its pieces (usually called cubies) can be permuted by twisting certain faces of the puzzle. The cubies carry stickers defining their location in the solved puzzle. For example, with the Rubik’s Cube, the 54 stickers of a 3×3×3 cube can be permuted by 90 degree turns of the faces. The possible permutations form a group called the Rubik’s cube group. Then he gives the following definition and remarkable Theorem.

Definition: Let G be a twisty puzzle group given via a set X of generating twists.
(a) The graph whose vertices are the elements of G and whose edges are pairs of positions which differ by just one twist is called the Cayley graph of G.
(b) The diameter δ(G) of the Cayley graph of G is called God’s number for the twisty puzzle.
(c) An algorithm which produces for every scrambled position p an element of X∗ whose length is the distance (in the Cayley graph) from p to the solved position is called a God’s algorithm for the twisty puzzle.

Theorem (God’s Algorithm via Grobner Bases)
Let X be a set of twists (and their inverses) which generate the group of a twisty puzzle. Given a scrambled position p of the puzzle, perform the following steps:
(1) Compute a Grobner basis G of the defining ideal of the twisty puzzle group ring w.r.t. a length compatible word ordering.
(2) Find any word w ∈ X∗ representing a sequence of twists that result in the position p.
(3) Compute NRG(w) ∈ X∗ and return this word.

This is an algorithm which computes a word representing a shortest possible sequence of twists that produces p from the solved position.

This has even been implemented on a computer in Cocoa, for a permutation puzzle with a very small group.