Matthew van Eerde's web log

  • Matthew van Eerde's web log

    Unsolving the Rubik's Cube


    Recently I was musing on Order vs. Chaos and toying with my Rubik's Cube.  I wondered, as a simple exercise, whether it would be possible to strongly unsolve the cube.  Obviously there is a single way to put the cube into a state of greatest possible order... and a multitude of ways to put it into a state of moderate to severe chaos... but is there a "most chaotic" state?

    Well, I mused, the "greatest possible order" state is achieved by bringing all the orange squares together... and all the blue squares together... and, in general, all the squares of any given color together.  How homogenous... or xenophobic.  Ew.

    Might it not be interesting to intermingle the colors to as great an extent as possible?  Can I put the cube in a state where no two orange squares are adjacent... and no two blue squares are adjacent... and, in general, no two adjacent squares are the same color?

    Of course, I responded.  In fact, I already know how to do that... I learned that trick before I even learned the Restore Order solution.

    Twelve turns later, I had a solution to the Adjacent Squares Are Different problem.

    Exercise: what are the twelve turns?

    Well, that was quick.

    But I wanted more.

    Yeah, OK, no two adjacent squares are the same color, by the usual definition of adjacency (the squares share a common border.)  But this is still a fairly homogenous solution... each face (of nine squares) still consists of only two colors, and there's a very high incidence of diagonally-touching squares of the same color.  Can't we diversify this even more?

    That took me a couple of days.  But here's the solution I came up with:

    Unsolved Rubik's cube

    Note that, as desired, no two adjacent squares are the same color... even if you consider squares that touch only at a corner to be adjacent... even if that corner lies on an edge, and the two squares in question lie on different faces of the cube.

    The method to achieving the solution was simple in the sense that it only requires two moves (starting from a solved cube) but is probably far from optimal in the "total number of turns" sense.

    There are two independent steps which can be done in either order:

    • Flip the orientation of all twelve of the "edge pieces" (the cubelets with two visible faces) 
    • Migrate all eight "corner pieces" (the cubelets with three visible faces) to the diametrically opposite position on the cube

    Each requires knowledge of a single move and a fair amount of courage.

    First, some syntax.

    Hold the cube facing you.  I will name the six faces of the cube:

    • Fore (the face closest to you - in the picture above, the face with the green center)
    • Hind (in the picture above, the face with the blue center)
    • Top (in the picture above, the face with the white center)
    • Bottom (in the picture above, the face with the yellow center)
    • Left (in the picture above, the face with the orange center)
    • Right (in the picture above, the face with the red center)

    Each face has a local definition of "clockwise"... this is the direction a clock painted on the face would turn.

    Cubelet syntax

    • A combination of two letters (FR) means the edge cubelet common to both faces - in this case the Fore and Right faces.  In the picture above, this is the green and white cubelet.
    • A combination of three letters (BHL) means the corner cubelet common to all three faces - in this case the Bottom, Hind, and Left faces.  In the picture above, this is the red-green-and-white cubelet.

    Move syntax: a letter means turn that face clockwise by 90 degrees.  A letter with a subscripted -1 means turn it counterclockwise by 90 degrees.  So a move "turn the Fore face clockwise, then turn the Left face counterclockwise, then turn the Top face counterclockwise" would be written:

    F L-1 T-1

    Start from a solved cube.

    Flip the orientation of all twelve of the "edge pieces"

    Pick your favorite color - say, red - and have that be the top face.

    The following move flips the orientation of the LT and TH edge pieces, and also disturbs the orientation of some corner pieces:

    L-1 T-1 L-1 L-1
    F-1 L-1 F-1 F-1
    T-1 F-1 T-1 T-1

    • Run the move once with red as the top face.
    • Position the cube so that red is still as the top face but the two remaining unflipped edge pieces with red on them are now in the LT and TH position.  That is, turn the whole cube 180 degrees with an axis of rotation that goes through the center of the top and bottom faces.
    • Run the move again.  All four edge cubelets with red on them should now be flipped.
    • Position the cube so that red is now the front face.
    • Run the move again four more times, keeping red as the front face but rotating the cube 90 degrees each time, so each execution of the move acts on two unflipped edge pieces.

    All twelve of the edge pieces are now flipped.  The corner pieces are still in their original positions, though they may be oriented incorrectly. That's OK.

    Reposition all eight corner pieces to the opposite corner

    The following move repositions FLT to TLH, TLH to TRH, and TRH to FLT:

    L-1 T R T-1
    L T R-1 T-1

    As a convenience, the following mirror-image move repositions FRT to TRH, TRH to TLH, and TLH to FRT:

    R T-1 L-1 T
    R-1 T-1 L T

    Strictly speaking, you can get away with only memorizing one of these moves - each move is equivalent to holding the cube in a different position and executing the other move twice.

    Pick three faces that share a common corner - say, the faces whose center cubes are red, white, and blue.  Position the cube so it is balancing on that corner.  Note that the corner cubelets now occupy four distinct strata:

    1. The "top" corner.
    2. The three corners that share a common edge with the "top" corner.
    3. The three corners that share a common edge with the "bottom" corner.
    4. The "bottom" corner. 

    This part of unsolving the cube is completed in four distinct phases:

    1. Unsolve the "top" corner - that is, find the red/white/blue cubelet (it's on the bottom corner) and move it to the top.  This will require two moves, which will to a certain degree randomize the positions of all of the rest of the corners.
    2. Unsolve the three corners that share a common edge with the "top" corner, without disturbing the cubelet in the "top" corner, or any already-unsolved cubelets in this stratum.
    3. Unsolve one of the three corners that share a common edge with the "bottom" corner, without disturbing any of the cubelets in the two strata above.
    4. Finally, there are three remaining un-unsolved cubelets.  Unsolve all three of these simultaneously - this will take precisely one execution of one of the two moves above.

    EDIT January 16 2012: Thanks to Dustin for pointing out that the diagram above shows some reds touching diagonally (near the topmost corner.)  After some analysis I believe this is just due to an error on my part in making the image; specifically, the top corner is green-yellow-red, but so is the corner in the top left.  Also, the green-yellow-orange corner is missing.

    Both of these can be explained by changing the red in the top corner to orange.  Updated image:

  • Matthew van Eerde's web log

    Spot the Bug - IMFOutputSchema


    I found a simple but nasty bug the other day in this implementation of the IMFOutputSchema interface.

    The symptoms: running this code outside of a debugger caused the app to crash.  Running it under a debugger (to catch the crash) caused the app to run clean.

    // outputschema.h
    HRESULT CreateTrustedAudioDriversOutputSchema(
        DWORD dwConfigData,
        GUID guidOriginatorID,
        IMFOutputSchema **ppMFOutputSchema

    // outputschema.cpp
    // ... various include files removed ...
    // CMFAttributesImpl implements the IMFAttributes interface, minus the IUnknown methods
    class CTrustedAudioDriversOutputSchema : public CMFAttributesImpl<IMFOutputSchema> {

        HRESULT CreateTrustedAudioDriversOutputSchema(
            DWORD dwConfigData,
            GUID guidOriginatorID,
            IMFOutputSchema **ppMFOutputSchema

        CTrustedAudioDriversOutputSchema(DWORD dwConfigData, GUID guidOriginatorID);

        ULONG m_cRefCount;
        DWORD m_dwConfigData;
        GUID m_guidOriginatorID;
        // IUnknown methods
           /* [in] */ REFIID riid,
           /* [out] */ LPVOID *ppvObject

        // IMFOutputSchema methods
        HRESULT STDMETHODCALLTYPE GetConfigurationData(__out DWORD *pdwVal);
        HRESULT STDMETHODCALLTYPE GetOriginatorID(__out GUID *pguidOriginatorID);
        HRESULT STDMETHODCALLTYPE GetSchemaType(__out GUID *pguidSchemaType);

    }; // CTrustedAudioDriversOutputSchema

    HRESULT CreateTrustedAudioDriversOutputSchema(
        DWORD dwConfigData,
        GUID guidOriginatorID,
        IMFOutputSchema **ppMFOutputSchema
    ) {
        if (NULL == ppMFOutputSchema) {
            return E_POINTER;

        *ppMFOutputSchema = NULL;

        CTrustedAudioDriversOutputSchema *pSchema =
            new CTrustedAudioDriversOutputSchema(dwConfigData, guidOriginatorID);

        if (NULL == pSchema) {
            LOG(eError, _T("new CTrustedAudioDriversOutputSchema returned a NULL pointer"));
            return E_OUTOFMEMORY;

        *ppMFOutputSchema = static_cast<IMFOutputSchema *>(pSchema);

        return S_OK;
    } // CreateTrustedAudioDriversOutputSchema

    // constructor
        DWORD dwConfigData, GUID guidOriginatorID
    : m_dwConfigData(dwConfigData)
    , m_guidOriginatorID(guidOriginatorID)

    // destructor
    CTrustedAudioDriversOutputSchema::~CTrustedAudioDriversOutputSchema() {}

    #define RETURN_INTERFACE(T, iid, ppOut) \
        if (IsEqualIID(__uuidof(T), (iid))) { \
            this->AddRef(); \
            *(ppOut) = static_cast<T *>(this); \
            return S_OK; \
        } else {} (void)0

    // IUnknown::QueryInterface
            /* [in] */ REFIID riid,
            /* [out] */ LPVOID *ppvObject
    ) {

        if (NULL == ppvObject) {
            return E_POINTER;

        *ppvObject = NULL;

        RETURN_INTERFACE(IUnknown, riid, ppvObject);
        RETURN_INTERFACE(IMFAttributes, riid, ppvObject);
        RETURN_INTERFACE(IMFOutputSchema, riid, ppvObject);

        return E_NOINTERFACE;

    // IUnknown::AddRef
        CTrustedAudioDriversOutputSchema::AddRef() {

        ULONG uNewRefCount = InterlockedIncrement(&m_cRefCount);

        return uNewRefCount;

    // IUnknown::Release
        CTrustedAudioDriversOutputSchema::Release() {

        ULONG uNewRefCount = InterlockedDecrement(&m_cRefCount);

        if (0 == uNewRefCount) {
            delete this;

        return uNewRefCount;

    // IMFOutputSchema::GetConfigurationData
        CTrustedAudioDriversOutputSchema::GetConfigurationData(__out DWORD *pdwVal) {

        LOG(eInfo1, _T("IMFOutputSchema::GetConfigurationData called"));

        if (NULL == pdwVal) { return E_POINTER; }

        *pdwVal = m_dwConfigData;
        return S_OK;

    // IMFOutputSchema::GetOriginatorID
        CTrustedAudioDriversOutputSchema::GetOriginatorID(__out GUID *pguidOriginatorID) {

        LOG(eInfo1, _T("IMFOutputSchema::GetOriginatorID called"));

        if (NULL == pguidOriginatorID) { return E_POINTER; }

        *pguidOriginatorID = m_guidOriginatorID;
        return S_OK;

    // IMFOutputSchema::GetSchemaType
        CTrustedAudioDriversOutputSchema::GetSchemaType(__out GUID *pguidSchemaType) {

        LOG(eInfo1, _T("IMFOutputSchema::GetSchemaType called"));

        if (NULL == pguidSchemaType) { return E_POINTER; }

        return S_OK;

Page 1 of 1 (2 items)

May, 2008