05 January 2012

1 in 600,000

For Christmas this year, my wife gave me (among other things) Another Tough Puzzle. This puzzle claims that "with millions of wrong solutions, the chance of solving this puzzle is ONE in 600,000!"

There are 16 triangular pieces and each piece has three connections each being one of four possible shapes. The completed puzzle should be a pyramid with six connections on the edges pointing in and six pointed out.

The puzzle also claims that "it looks easy...but just when you think you've solved it, the last piece proves you wrong." This is very true and very frustrating. I (and others) played around with the puzzle for a while always ending up with one piece that didn't fit.

Then I thought, "I write software for a living; why don't I do that here?" I've enjoyed writing solvers in the past (my Minesweeper solver would actually play the GUI for you on previous Windows versions). I mostly use C++, so I decided to use it here as well. Certainly there are languages more suited to rapid development, but I'm a glutton for punishment.

The first step was to describe the pieces. We noticed pretty quickly that half of the pieces have two outward-facing connectors (outputs) and one inward-facing connector (input) and the other half are opposite (two inputs and one output). There are no pieces with three inputs or outputs.
enum FaceType
{
    eFaceTypeClover = 0,
    eFaceTypeHeart,
    eFaceTypeSpade,
    eFaceTypeDiamond,
};

enum Direction
{
    eDirIn = 0,
    eDirOut,
};

struct Node
{
    FaceType face;
    Direction dir;

    bool fits(const Node& rhs) const
    {
        return face == rhs.face && dir != rhs.dir;
    }
};
struct Piece
{
    Node node[eNumSides];

    Piece(FaceType in, FaceType out1, FaceType out2, bool)
    {
        node[0].face = in;
        node[1].face = out1;
        node[2].face = out2;
        node[0].dir = eDirIn;
        node[1].dir = node[2].dir = eDirOut;
    }
    Piece(FaceType in1, FaceType in2, FaceType out)
    {
        node[0].face = in1;
        node[1].face = in2;
        node[2].face = out;
        node[0].dir = node[1].dir = eDirIn;
        node[2].dir = eDirOut;
    }
};
Using these structures, all of the pieces can be declared:
Piece pieces[eNumPieces] =
{
// one input, two outputs
Piece(eFaceTypeSpade, eFaceTypeDiamond, eFaceTypeHeart),        // 0
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade),        // 1
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade),       // 2
Piece(eFaceTypeClover, eFaceTypeSpade, eFaceTypeHeart),         // 3
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeClover),         // 4
Piece(eFaceTypeHeart, eFaceTypeSpade, eFaceTypeClover),         // 5
Piece(eFaceTypeSpade, eFaceTypeClover, eFaceTypeDiamond),       // 6
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart),       // 7

// two inputs, one output
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeHeart, true), // 8
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeSpade, true), // 9
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade, true),  // a
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeDiamond, true), // b
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeSpade, true),   // c
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart, true), // d
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade, true), // e
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeDiamond, true)   // f
};
Now that the pieces are all set up, the gameboard must be described. The end result should be a pyramid made up of all 16 pieces (see diagram). Therefore, I had to describe how the pieces relate to each other in the gameboard. This will allow the solver algorithm to test that a piece 'fits' if its connectors match the adjacent pieces. In order to do this, each position in the desired puzzle shape is marked with a number and each side of the triangular pieces are numbered as well. The sides are always numbered clockwise starting at the horizontal side so that adjacent pieces in the puzzle have sides matching (for instance, pieces 7 and 8 both share their side number 2).






The array of PieceLoc structures define how each piece relates to adjacent pieces:
PieceLoc locs[eNumPieces] =
{
// Sides:     0               1               2          // Pieces
PieceLoc(eInvalidPiece,  eInvalidPiece,              1), // 0
PieceLoc(            7,              2,              0), // 1
PieceLoc(eInvalidPiece,              1,              3), // 2
PieceLoc(            9,              4,              2), // 3
PieceLoc(eInvalidPiece,              3,              5), // 4
PieceLoc(           11,              6,              4), // 5
PieceLoc(eInvalidPiece,              5,  eInvalidPiece), // 6
PieceLoc(            1,  eInvalidPiece,              8), // 7
PieceLoc(           12,              9,              7), // 8
PieceLoc(            3,              8,             10), // 9
PieceLoc(           14,             11,              9), // a
PieceLoc(            5,             10,  eInvalidPiece), // b
PieceLoc(            8,  eInvalidPiece,             13), // c
PieceLoc(           15,             14,             12), // d
PieceLoc(           10,             13,  eInvalidPiece), // e
PieceLoc(           13,  eInvalidPiece,  eInvalidPiece)  // f
};
The fitting function is recursive. The first time it is called it has all 16 pieces remaining to try and fit. It loops through all remaining pieces rotating them in all possible positions each time checking to see if the piece fits. If the piece fits, it calls itself again this time with 15 pieces remaining. When a pieces is found that fits, it calls itself again with 14 pieces remaining. And so on, and so forth until all pieces have been used. If a piece doesn't fit, it goes on to the next piece. If a solution is found or no more pieces fit, the function returns and tries the next piece.

Since we only have 16 pieces, I use a bitmask to determine which pieces are already used.
void FitRemaining(int remain)
{
    if (remain <= 0)
    {
        ShowSolution();
    }
    else
    {
        int index = eNumPieces-remain;
        for (int i = 0; i < eNumPieces; ++i)
        {
            if ((used & (1 << i)) == 0)
            {
                used |= (1 << i); // Mark in-use
                pieces[index] = i;
                for (int r = 0; r < eNumRotations; ++r)
                {
                    rotation[index] = r;
                    if (validate(index))
                    {
                        FitRemaining(remain - 1);
                    }
                }
                pieces[index] = eInvalidPiece;
                used &= ~(1 << i); // No longer in-use
            }
        }
    }
}

The last part is the validation function. We really only need to validate the most recent piece added. Figuring out which sides are facing each other is the most difficult part, but even that is pretty easy. Because of how the gameboard is organized we already know that side indexes on adjacent pieces always face each other. All we need to do is take the rotation into account and ensure that the shapes match:
bool validate(int piece) const
{
    assert(piece >= 0 && piece < eNumPieces);
    const Piece* cur = Get(piece);
    int rot1 = rotation[piece];
    const PieceLoc& fit = locs[piece];
    for (int f = 0; f < eNumSides; ++f)
    {
        const Piece* p = Get(fit.neighbors[f]);
        if (p)
        {
            int rot2 = rotation[fit.neighbors[f]];
            if (!cur->node[(rot1 + f) % 3].fits(p->node[(rot2 + f) % 3]))
            {
                return false;
            }
        }
    }
    return true;
}

That's all there is to it! I probably spent less time writing this program than manually (and frustratingly) trying to find the solution.

In fact with this program I found all 518,469 solutions to the puzzle. Here's the first one:

If you'd like the full C++ source: Go here.

8 comments:

MrTact said...

Ah, brute force... the bluntest of the instruments in the programmer's toolbox.

I would mock you for writing code on vacation, if I hadn't done exactly the same thing.

DBump said...

That's very, very neat.
It almost looks like you could tile multiples of this puzzle together, with the solution pictured.
Have you thought about updating the code to check if that's feasible?

Joshua Kriegshauser said...

@DBump

I haven't specifically approached that problem, but I did later extend it to output searchable patterns for the edges (i.e. so you could find solutions where all edges are alternating in/out, etc.) Based on that, I'm sure that it's possible to attach multiple puzzles together in larger configurations.

Timo said...

Hi - I came upon your post because I wrote a similar program to solve the same puzzle. I basically took the same approach as you. My version also solves for a variable number of "game sets", allowing 4 (or more) sets to be combined to create larger and larger pyramids.

One minor thing I wanted to mention. I think there are actually only 172823 unique solutions. I exclude 2/3 of 518469 because they are basically just the entire solved puzzle rotated.

Otherwise, nice writeup.

Simon Snake said...

I just received this for Christmas and have just opened the box and put it together into a triangle that meets the requirement of six outward facing and six inward facing joints in a triangle formation, and got it first go. The box claims there are 600,000 wrong ways to assemble the game but only one solution. Unless the pieces in each box are different (mine have both sides black) my solution differs from yours in the placement of the inward and outward facing joins.

Richard S. Maddox said...

great and nice blog post.thanks for sharing.
all software free download

hou said...

I played around with the puzzle for a while always ending up with one piece that didn't fit.
meizu mx5
xiaomi redmi note 2
meizu m2

hou said...

I just received this for Christmas and have just opened the box and put it together into a triangle that meets the requirement of six outward facing and six inward facing joints in a triangle formation, and got it first go. The box claims there are 600,000 wrong ways to assemble the game but only one solution. Unless the pieces in each box are different (mine have both sides black) my solution differs from yours in the placement of the inward and outward facing joins.
Lenovo Lemon X3 Unboxing
LG G4 H818 Unboxing
Blackview Omega Pro Review
DOOGEE F3 Pro Specs