Rubik's Cube in Prolog – Order | Hacker News Reader

Rubik's Cube in Prolog – Order

medium.com

41 pointsmyth_drannon14 comments

I'm not sure if anyone has noticed, a rubiks cube can be represented by only the orientations of the pieces. You do this by defining their "correct" position in cube coordinates rather than piece coordinates (local about the piece center). In other words you might define a 3d model for each piece in world space assuming the cube as a whole is centered on the origin. With pieces offset from the origin like this, any rotation about an axis will appear to move the piece as well as rotate it. With 24 orientations, you'll find 3 that place a corner in the same position but colors rotated. Similarly edges have 2 orientations for each of 12 locations.

One does need to compute the traditional position of the pieces to determine which ones need to be rotated for a given move, but the total state is significantly reduced.

Tell me this isn't news to the cube world. It cant be. Can it?

I'm trying to figure out what you're trying to say here.

You didn't really define what "cube coordinates" or "piece coordinates" are.

If you're trying to reduce the size of the state needed to represent the entire state of the cube, you can represent it as the operations needed to transform a solved cube into that state.

Each possible permutation of legal state in a rubiks cube can be achieved in 20 operations (moves) or less.

But that's expensive to calculate if you are only given the target state without the list of operations to generate that state.

It also doesn't let you represent illegal states (e.g. someone has spun a single corner piece on the spot) or know if a given state is illegal without trying to brute-force solve the cube.

Needing to represent the state of a cube without knowing the operations that generate that state is far more useful than being given a state that's already the solution to solve a cube.

By "cube" coordinates i mean a coordinate system centered on the whole cube. By "piece" coordinates i mean with the origin centered on one of the smaller pieces of the puzzle.

In graphics programming you'd use world coordinates and object coordinates in a similar way. Each piece is geometrically the same (except color) in object coordinates. To rotate you normally rotate in object coordinates and then move (translate) in world coordinates. Im saying just define each piece in world coordinates and rotate them in world coordinates. They'll orbit the center of the whole cube that way and you'll only be changing their orientation.

Another way to say it might be: use quaternions to describe the orientation of a piece where (1,0,0,0) is the piece in "solved" position. After applying several rotations to a piece you still have orientation in a single quaternion, which can also be applied to the original position vector to find out where it is now. Location and orientation are not independent.

Another way to say it is that if you have any given piece and know its orientation, there is only one place it can be on the puzzle.

Unable to fully parse what you are trying to express.

> the total state is significantly reduced.

The minimal "state space" of a rubiks cube is a constant value. Any "reduction" would imply the model being reduced was inefficient.

On the topic of cool "alternative" views of rubiks I recently saw this and thought it was novel.

https://old.reddit.com/r/gifs/comments/z3okyv/the_only_way_t...

>> > the total state is significantly reduced. >> The minimal "state space" of a rubiks cube is a constant value.

The article is about solving a cube with software. Software typically represents both the orientation AND position of 20 (or 26) pieces. Orientation might be enumerated so it can be represented by number 1-24 or 0-23 as software tends to do. It could also be represented by a set of Euler angles for each piece. Position is could be enumerated since there are only 20 positions or it could be a vector indicating the piece center relative to the origin. There is a certain amount of data needed to represent the cube in a useful way. Apparently some people store the color (1-6) for each face for a total of 6x9 = 54 numbers each from 1-6. Any of these representations has more possible states than an actual cube because you can encode position that are not possible to achieve on a real cube (solved with a single corner rotate for example). My point is that the 20 orientations are enough without the positions if you're trying to track position AND orientation like the linked article does. The positions can be recovered from the orientations.

That link. This is a Celtic Knot and 92 is half of 99. I had to.

I don't have enough time now to work out how are the movement described in your representation to evaluate its convenience. If you have worked out something, could you share it?

I don't know anything about the cube world as I'm just a noob in this.

Fun article! Makes me want to play with prolog again.

I put together something looking at a rubik's cube as a permutation of numbers a while back. https://taeric.github.io/cube-permutations-1.html I remember realizing that my representation essentially had some permutations of numbers that it would never hit, but wasn't sure it was worth trying to more directly model the pieces of the cube. Curious if there are advantages here that I'm ignoring.

one nice thing is that if you represent the state as a permutation matrix P, and have a matrix of starting piece locations x, rendering is just Px. Then, for smooth rotation animations, if your move is a permutation M, animation is just expm ( t logm( M)) P x with t going from 0 to 1

I blather about the permutation matrix of a rubiks cube for a long while at https://www.hgreer.com/TwistyPuzzle/

Nice! I have a css based animation at the bottom of the page I was playing with. Considered trying to do it with 3d animations, but at that point I was assuming something like the main article here would be needed to keep the faces coherent to each other.

I also never kept going down this route to actually learn solutions. Which, I think should be easy enough to do.

It would be much funnier, if the Cube was at origo. So indexes are {-1,0,+1}. And thus Cube[0,0,0] is empty, or maybe there is a ball with 6 screw-holes in it.

Nearest nonhuman intelligence seems to be the only one to appreciate this approach. It shortens the code and also search space as it is easier to recognize symmetries.

OT: The time between releasing a free Rubik's cube program to play store and receiving a cease & desist has always impressed me.

Prolog's pattern matching makes this elegant. The constraint-based approach for state space pruning is clever.

Reply on news.ycombinator.com