{"id":665,"date":"2014-11-05T03:55:52","date_gmt":"2014-11-05T03:55:52","guid":{"rendered":"http:\/\/anthonybarranco.com\/blog\/?p=665"},"modified":"2014-11-05T04:37:10","modified_gmt":"2014-11-05T04:37:10","slug":"rubiks-cube-ai-1","status":"publish","type":"post","link":"http:\/\/anthonybarranco.com\/blog\/rubiks-cube-ai-1\/","title":{"rendered":"Rubiks Cube AI Part 1 – Parity"},"content":{"rendered":"

Rubiks Cubes! I cant solve them to completetion for the life of me. But now I can just solve them using an AI.<\/p>\n

But before jumping into heuristics, A* algorithms, and all kinds of solving. First, let us consider a random Rubiks Cube itself. Is the cube actually\u00a0solveable\u00a0<\/em>in the first place? Can we go from the random state pictured above to a solved cube?<\/p>\n

The answer is no. The Rubiks Cube parity has been altered!<\/p>\n

<\/p>\n

Intro<\/h1>\n

Note that this is for a classic Rubiks cube (3x3x3).<\/p>\n

Quite simply, the cube’s corners have been twisted. Its the equivalent of taking the stickers off a normal Rubiks Cube and sticking them into different positions. It makes the cube\u00a0impossible to solve<\/em>. Or at least, the chances of getting random stickers into a solveable position is tough. The total number of possible valid<\/em>\u00a0Rubiks Cube scrambles is\u00a043 quintillion<\/strong> (8! x 3^7 x (12!\/2) x 2^11). The total number of possible Rubiks Cube scrambles\u00a0in total (both valid and invalid)\u00a0<\/em>is a rediculous\u00a0519 quintillion . <\/em><\/strong>(8! x 3^8 x 12! x 2^12) And that’s not including the possibility of switching stickers (invalid cubie possibilities, but more on that later). So the number is even more astronomical.<\/p>\n

You have a 1\/12 chance for a random Rubiks Cube to be valid (that was made with valid cube colors)<\/em><\/strong><\/p>\n

What is a Rubiks Cube made of?<\/em>
\nAs a 2D representation, a Rubiks Cube has unique 54 squares (or stickers) and there are 6 colors represented on each of the 6 faces of the cube. So there are 9 squares of each color. Usually Red, Orange, Yellow, Green, Blue, White.<\/p>\n

There is more to a Rubiks Cube though. Categorically, you can split a Rubiks Cube up into 3\u00a0types of “cubes”. Otherwise known as\u00a0Cubies<\/em>. Its easier to picture this in 3D. A\u00a0Cubie<\/em> is a 3D cube that represents part of the whole Cube.
\nThere are\u00a026\u00a0Cubies<\/em> on a Rubiks Cube.
\n8 of them are\u00a0Corner Cubies<\/em> and\u00a012\u00a0<\/em>of them are\u00a0Edge Cubies<\/em>. \u00a0The other 6 are\u00a0Center Cubies<\/em>.
\nThe main difference between corner and edge cubies are that corner cubies have\u00a03 different colors<\/em> and edge cubies have\u00a02 different colors<\/em>. Center cubies\u00a0only have 1<\/em> and its impossible to actually move a center cubie.<\/p>\n

\"2000px-Rubik's_cube.svg\"<\/a><\/p>\n

So right off the bat, there are a bunch of ways to tell if a Cubie is not solveable. It has to have 6 colors and 9 stickers or squares of each color. Each color has to be represented in a center cubie\u00a0only once<\/em>. No more, no less. If you peel off a center sticker and replace it with a different color, the cube is immediately not “solveable”.<\/p>\n

However, just these alone are not enough. You need more than that. Namely, none of those checks look at\u00a0parity.<\/em> The parity of a cube needs to be correct in order for all the cubies to be able to properly be orientated in their home positions.\u00a0Home positions<\/em> in a Rubiks Cube is the position on a face in which the cubie is facing the right direction. For example, the Blue\/Yellow edge cubie has its Blue side touching the Blue center and the Yellow side is touching the Yellow Center. Its in its home position. When all cubies are in their home position with correct orientation, the cubie is solved.<\/p>\n

So in my original example at the top of the page, the picture has the corners all twisted. The parity is off because we’ve twisted corner cubies and their orientations can never be correct with the rest of the cube now. Those corners can never be in the right position and orientation without the rest of the cube being incorrect!<\/p>\n

So how does one check for these? Three tests:<\/p>\n

    \n
  1. Permutation<\/li>\n
  2. Corner Parity<\/li>\n
  3. Edge Parity<\/li>\n<\/ol>\n

    Believe it or not, I found an incredible lack of information online regarding these tests. The best rescources I can find through Google were here<\/a>,\u00a0here<\/a>\u00a0and here<\/a>, and only the latter skantly goes into detail how to actually perform the tests. And any information about performing the tests is either a little off or under explained! \u00a0At least, for example, permutation tests only consider one side of a cube and not the WHOLE cube. So thats why I felt it necessary to make this lengthy blog in detail.<\/p>\n

    Permutation Test<\/h2>\n
    \"Passes_edge_and_corner_test\"<\/a>

    Fails permutation test, but corner and edge parity tests pass!<\/p><\/div>\n

    In my opinion, the easiest test to implement.
    \nSimply consider each unqiue Edge and Corner Cubie as an arbitrary unique number. Seperately for Edge and Corner, pick a fixed cubie to start from and consider what # is actually in that position and repeat for all Edges or Corners. Then if the total number of inversions to make both\u00a0lists (edges and corners) ordered is\u00a0even<\/em>, you have a valid permutation.<\/p>\n

    Rewind.
    \nLets start with edges, we have 12 unqiue cubies for them.
    \nRW – RG – RB – RY – GW – GY – GO – YB – YO – BW – BO – OW
    \n<\/strong>0 \u00a0 \u00a0 – \u00a01 \u00a0 – \u00a02 \u00a0 – \u00a03 \u00a0 – \u00a0 4 \u00a0 – \u00a05 \u00a0 – \u00a0 6 \u00a0 – \u00a07 \u00a0– \u00a08 \u00a0 – \u00a0 9 \u00a0 – \u00a010 \u00a0– \u00a0 11<\/strong><\/p>\n

    This is the order I went with. I number each of these cubies 0 to 11. Basically, if I look at\u00a0any<\/em> edge on the cubie in my program (or physically in real life), you can tell that if the edge cubie is R & Y or Y & R, then its\u00a0value<\/em> is\u00a03.<\/strong> R & W or W & R is 0.<\/b>\u00a0And so on.<\/p>\n

    To make things easier, its also nice to look at the\u00a0positions\u00a0<\/em><\/strong>in the same way. So if I say “go to position 0 for edges”, you’d look at where\u00a0RW<\/strong> is\u00a0supposed to be (its home position).<\/em> Sometimes this is hard for newbies to Rubiks Cubes when someone says go look at a position. Its where the Red and White cubie would be if you would look at a solved cube. That never changes! What’s\u00a0in that position<\/em> changes.<\/p>\n

    So consider the list G =\u00a0<\/b>{\u00a00, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
    \nWe’d agree with the explanation above that is “solved”. It doesn’t mean the cube itself is actually solved, but that order is how we\u00a0expect<\/em> the cubes to be in when we solve a cube.<\/p>\n

    If we have the list\u00a0\u00a0A<\/strong>\u00a0=\u00a0<\/strong>{7, 6, 4, 0, 11, 10, 5, 1, 9, 8, 2, 3}
    \nThat means YB is where RW should be, GO is where RG should be, and so on.
    \nFrom this list, find the number of\u00a0inversions<\/em> to get from\u00a0A\u00a0<\/strong>to\u00a0G.\u00a0<\/strong>Inversions are simply the number of times each number has to be swapped to get into sorted order. Read it from left to right to understance easier.<\/p>\n

    Very simple inversion code:<\/p>\n

    \"inversion\"<\/a><\/p>\n

    Perhaps A<\/strong> is a bit of a\u00a0complex example, but it would take\u00a038 inversions to get to list G<\/strong>\u00a0from it.<\/p>\n

    Take the results from doing this with corners, handled the exact same way (but from 0 to 7 instead), and add the results together<\/i>.<\/p>\n

    If the result of cornerInversions + edgeInversions is even<\/strong> then a whopping\u00a01\/2<\/strong> of invalid possibilities are rejected! Its an easy and effective test to do!<\/p>\n

    If its odd, then two cubies or more are out of parity. They’ve been swapped, possibly from deconstructing and reconstructing the cube. (eg, you switched BO and OW or something)<\/p>\n

    The reason for this test is because each inversion is a “swap”, and there can never be a total number of odd swaps. In other words, no matter how many times you turn a Rubiks cube, if they’re legal (valid) twists of the cube – they always result in even swaps in total.<\/p>\n

    \u00a0Corner Parity Test<\/h2>\n
    \"Fail_corner\"<\/a>

    Invalid Corner orientation, but the permutation and edge are not!<\/p><\/div>\n

    A bit tougher. Look at a face of your cube straight on. Never change the orientation of the cube from here on out. Always look at that face and always make sure the top and bottom colors never change.<\/p>\n

    For example. if I look at the Orange face on a classic Rubiks Cube and Yellow is the top face, then White is\u00a0garunteed<\/em> to be my bottom face.\u00a0Blue\u00a0is my right face. Green is my left face. And Red is my back face. Choose however you want to look at it, but just make sure you never change it in the middle of Corner and Edge Parity tests.<\/p>\n

    We’re going to do something similar to the permutations in regards to positions. So from 0 to 7, we’re going to look at these positions the same all the time. Its contents can be different, but the positions are where we expect the cubes in their home positions.<\/p>\n

    For example,
    \nRGW – RBW – RGY – RBY – GOW – GOY – YOB – BOW
    \n0 \u00a0 \u00a0 – \u00a0 \u00a01 \u00a0 \u00a0 – \u00a0 2 \u00a0 – \u00a0 \u00a03 \u00a0 \u00a0– \u00a0 \u00a0 4 \u00a0 \u00a0 – \u00a0 \u00a05 \u00a0 \u00a0 – \u00a0 6 \u00a0 \u00a0– \u00a0 7<\/strong><\/p>\n

    When I look at position 2, it could have any corner cubie in any orientation in it, but its where\u00a0RGY should be if its a solved cube.<\/p>\n

    Starting from 0, look at every position to 7 and consider the\u00a0orientation<\/em> of the cubie. What do I mean by that?\u00a0Again, in my example picture, the corner cubies have been twisted. We’re testing for this!<\/p>\n

    How its going to work is we treat the top and bottom colors as the\u00a0same<\/em>. In other words, forget the sides of the corner cubies that are Yellow and White in my example. Treat Yellow and White as if they were exactly the same color. Its kind of weird, but bear with me.<\/p>\n

    If the\u00a0White or Yellow<\/strong>\u00a0part of a corner cubie is touching\u00a0White or Yellow<\/strong> center, then we know that our cubie is\u00a0correctly orientated.\u00a0<\/em>If the top\/bottom color is not touching the center of their friend, then we know that the cubie is\u00a0not correctly orientated<\/em>. The issue is the cubie can be two kinds of not correct – clockwise or counter clockwise.<\/p>\n

    The way to tell which kind of incorrect orientation is by imaginging you’re twisting the corner cubie yourself. You’re pulling out that corner cubie from your Rubiks Cube and physically rotating it in your mind. How many clockwise turns does it take to get that top\/bottom color to touch ? One or two turns?
    \nAn important thing to remember is that using your left or right hand matters here. A clockwise turn with your left hand is not the “same” turn with your right hand.<\/p>\n

    Its tough to explain in words – here might be a few pictures to help:<\/p>\n

    \"20141104_222143\"<\/a>

    Value = 2<\/p><\/div>\n

    \"20141104_222456_4_bestshot\"<\/a>

    Twist the corner piece<\/p><\/div>\n

    \"20141104_222032\"<\/a>

    Value = 1 but if you rotate it again the value will be 0<\/p><\/div>\n

    This is where corner positions play an important role. For each of the corner cubie positions we discussed before from 0 to 7, you have to play with your corners to figure out which corners orientations take 2 rotations and which corners only take 1. You can determine this and kind of hard code it into your program by considering which side White or Yellow is on (or whatever your top color is) and simply loop through your structure of 3 colors (corner cubie). If the White or Yellow cubie is in corner X (0-7) and the position inside your corner cubie is Y (0-2), then its either correctly, clockwise, or counterclockwise orientated.<\/p>\n

    Those three results should be numbered. 0 for correct, 1 for clockwise, 2 for counterclockwise.
    \nFor each of your 8 corner cubies, add those numbers together.\u00a0If the total number is divisible by 3<\/strong>, then your corner cubies have a valid parity. Thats\u00a01\/3<\/strong> invalid possibilities rejected for your Cube!<\/p>\n

    \u00a0Edge Parity Test<\/h2>\n
    \"Fail_edge\"<\/a>

    Edge orientation is invalid, but corner and permutation are not!<\/p><\/div>\n

    The hardest test to\u00a0program out. I personally went through and found every possibility for this on my Rubiks Cube and hard coded this test pretty throughoughly at first. But, there is an easier way to figure this out on the fly. It has to do with opposing faces, much similar to the Top\/Bottom (White\/Yellow) in the Corner Parity Test.<\/p>\n

    Again, make sure you look at the same face as you did before with the same orientation in the Corner Parity Test too. (Mine was looking at orange, Yellow on Top, White on the bottom)<\/p>\n

    White and Yellow are opposing faces for me. Blue and Green are also opposing. And so is Red and Orange.\u00a0Think of the opposing colors as the same colors, again similar to White\/Yellow. If the opposing color is correctly touching the center opposing color correctly, then it is correctly orientated.<\/p>\n

    \"20141104_221034\"<\/a>

    Red-Blue is incorrectly orientated! Notice how the back face is rotated.<\/p><\/div>\n

    For example, Orange and Red are again opposing colors. If you have Red\/White edge in the position where Orange\/Yellow should be, and Red is touching Orange center and White is touching Yellow, your cube is not correctly<\/em>\u00a0<\/strong>orientated!<\/p>\n

    For every edge cubie, go through each position (0 to 11) and perform this test. If its\u00a0not correctly orientated,\u00a0<\/em>increment a counter. If that counter is divisible by 2 after testing every edge cubie, then you’ve just rejected another\u00a01\/2 <\/strong>of invalid configurations!<\/p>\n

    \"20141104_221007\"<\/a>

    Blue-Red is correctly orientated! Notice how only the right and top faces needed to be rotated. NOT the front or back.<\/p><\/div>\n

    But first, why does this work? If you read Arjun’s page earlier, it has to do with using the front and back faces to flip edges. If you’re looking at a cube at the orange face, then in order to get an incorrectly orientated edge into position, you need to use either the back or front faces to turn. For correctly orientated edges, you don’t need to do this! You can use the Top, Bottom, Left, or Right faces to get that cubie into home position with the right orientation.<\/p>\n

    Here’s a good video about edges as well:
    \n