not an impossible problem, just a really big one

My mother gave the fam a new game for Xmas called “The Impossible Puzzle.” Or maybe that was the company name. Either way, the label is certainly apt.

The puzzle is composed of nine, 4-sided pieces with interlocking parts in the shapes of the 4 card suits (hearts, diamonds, etc). There is only one way to lock the 9 pieces into a 3X3 square, and the game touts the fact that “there are over 300,000 combinations, only one of which is correct.”

Fig.1: An example of the puzzle pieces.

My mother, her bf, and myself all fiddled with this puzzle for a while before becoming too frustrated. There seemed to be no way to logically sort through the options of all possible arrangements and rotations of the pieces and clearly a brute-force method of trying all combinations would take way too long by hand. But maybe not for a computer. So, I figured this would be an excellent opportunity to try out my programming skills.

The idea seemed simple enough: I needed a way to model each puzzle piece in a program, and then have the program arrange those 9 pieces in each of every possible way and then test whether or not that arrangement was a solution. To test for matches, I decided that I would assign each shape a number, and the positive version would represent the “outy” and the negative would be the “inny”. The test for a matching pair would then be “if(side A = the opposite of side B), then they are a match”. For illustration, see the diamond shape in the figure above.

I then needed three more things:

  1. A way to re-arrange the puzzle pieces methodically into every possible 3×3 spacial arrangement;
  2. A way to rotate each piece methodically for every possible arrangement of rotations, within each spacial arrangement;
  3. A test for whether or not the arrangement was a solution.

I’ll go through these one-by-one, then hit the programming in a later post.

1. Spacial Re-arrangement

Since there are exactly 9 different pieces, finding the number of possible spacial arrangements requires the use of permutations.

Starting with all nine pieces, I have 9 options for the first position, p[1]. Since I now only have 8 puzzle pieces left, I only have 8 options for p[2]. Then 7 for p[3] and so on. That means that the number of possible arrangements of these nine puzzle pieces is equal to

9*8*7*6*5*4*3*2*1 = 9! =362,880

So, the game’s claim of  “over 300,000” was correct, but is an incredibly low-ball estimate because it is already too low before taking into account that the pieces have 4 different rotational positions as well!

Now, I have a suspicion that there are actually fewer than 9! arrangements, since the puzzle is a 2D structure. For example, the arrangements

| 1 2 3 |             | 9 8 7 |
| 4 5 6 |    and   | 6 5 4 |
| 7 8 9 |             | 3 2 1 |

Are actually just the same arrangement where the entire puzzle is rotated 180°. In fact, rotating the puzzle by 90° increments will give you the same puzzle (this makes perfect intuitive sense; just imagine turning a jigsaw puzzle), but this is only true if the puzzle pieces are also rotated (a little less intuitive). The end result is that we could decrease the total number of computations required by a factor of 4.

2. Rotations

So, we have 9! ways of arranging this puzzle into a 3×3 grid, but we also have to bear in mind that each puzzle piece has four possible rotations. For example, in Figure 1, the pieces are in a rotation in which the “inny” and “outy” diamonds can connect. If we were to rotate the “inny” piece by 90°, the two pieces can no longer be connected.

Fig. 2: We also have to take into consideration each rotation.

How many different ways can we rotate the 9 puzzle pieces? Since the rotation of one has no bearing on the rotation of another, the situation is different than before. At position p[1] we have 4 options. At p[2] through p[9] we also have 4 options. The total number of rotational arrangements is then

(4*4*4*4*4*4*4*4*4 )= 49 = 262,144

which is a similarly huge number. It gets a lot more frightening when you realize that this is how many rotational arrangements there are for each positional arrangement! Our total number of potential solutions is then, taking into account piece rotation, puzzle rotation, and piece arrangement:

(possible arrangments)*(possible rotations per arrangement) =

(362,880/4)*262,144 =  23,781,703,680

Yeah. 23 billion.

Where the hell did they get 300,000? They were off by a factor of 100,000! Or perhaps I’m just doing something wrong; that whole combination vs. permutation thing has aways confused me :).

3. Testing Potential Solutions

We now have an idea of how many different solutions there are to this problem, but only one of them (the game-makers claim) is correct! So we also need a way to test for correctness.

The most straight-forward thing to do would be to check whether or not each neighboring side is a match (i.e. is equal but opposite in value). There are 12 pairings that have to match in the correct arrangement.

Fig. 3: The correct solution must have 12 matching sides (red bars).

If each puzzle piece has a defined top, bottom, left, and right, then we simply need 12 comparison tests in the spirit of “if the right side of the top-left square is equal but opposite to the left side of the top-middle square, they are a match.”

Next Steps

Now that I have laid out the problem and a rough idea of what needs to be accomplished to solve it, we can walk through a short computer program that will do this work for us. I’ve already finished the program and successfully tested it against fake data that I knew had a  solution, so I will run it overnight tonight against the real puzzle and hope that my Eee PC’s tiny processor can chug through all the necessary calculations fast enough to have an answer for me by morning. Once it works, I’ll write up a post on the program itself.

**UPDATE**

That first test against the real puzzle didn’t work, because I had recorded the pieces incorrectly. That was fixed and the solution was found, and this is described in a later post.

7 thoughts on “not an impossible problem, just a really big one

  1. Hey there. I’ve just been taking a trip down memory lane reading this. I remember my step father getting the jigsaw from somebody for a wee Christmas present. He spend a good few hours trying to solve it before telling me “I couldn’t do it so you have no chance”. Needless to say he was pretty miffed after I completed it in a matter of minutes.
    The puzzle is hard no doubt about that. It was nearly 20 years ago but if I remember correctly (and it’s the same design) it’s the piece with a positive heart one side and the negative straight opposite that is the centre piece.

    I’m not sure if that’s any use to you but thought I’d mention it.

    Peace

  2. Hello,

    I believe I have a solution to the puzzle problem. I wrote it in C# in an attempt to solve 9 piece puzzles such as the ones found here:

    http://www.google.com/products?q=B+Dazzle+Game+Birds+&hl=en&aq=f

    So far, after letting it run for about an hour, I have 3 working solutions.

    Let me know if you would like to see the rest of the project.

    Here is some of the code:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using Puzzle;

    namespace Puzzle
    {
    public class Piece : IEquatable
    {
    private int _number = -1;
    private int _attempt = 0;
    private Side _top;
    private Side _bottom;
    private Side _left;
    private Side _right;

    public Piece(int Number)
    {
    _number = Number;
    }

    public int Number
    {
    get { return _number; }
    set { _number = value; }
    }

    public int Attempt
    {
    get { return _attempt; }
    set { _attempt = value; }
    }

    public Side Top
    {
    get { return _top; }
    set { _top = value; }
    }

    public Side Bottom
    {
    get { return _bottom; }
    set { _bottom = value; }
    }

    public Side Left
    {
    get { return _left; }
    set { _left = value; }
    }

    public Side Right
    {
    get { return _right; }
    set { _right = value; }
    }

    public override bool Equals(object obj)
    {
    return Equals(obj as Piece);
    }

    public bool Equals(Piece other)
    {
    // Check whether the compared object is null.
    if (ReferenceEquals(other, null)) return false;

    // Check whether the compared object references the same data.
    if (ReferenceEquals(this, other)) return true;

    // Check whether the Piece’ properties are equal.
    return Number.Equals(other.Number) &&
    Top.Equals(other.Top) &&
    Bottom.Equals(other.Bottom) &&
    Left.Equals(other.Left) &&
    Right.Equals(other.Right);
    }

    public override int GetHashCode()
    {
    //Get hash code for the ProductId field.
    int hashNumber = Number.GetHashCode();

    int hashTop = Top == null ? 0 : Top.GetHashCode();
    int hashBottom = Bottom == null ? 0 : Bottom.GetHashCode();
    int hashLeft = Left == null ? 0 : Left.GetHashCode();
    int hashRight = Right == null ? 0 : Right.GetHashCode();

    //Calculate the hash code for the product.
    return hashNumber ^ hashTop ^ hashBottom ^ hashLeft ^ hashRight;
    }

    public static bool operator ==(Piece a, Piece b)
    {
    // If both are null, or both are same instance, return true.
    if (System.Object.ReferenceEquals(a, b))
    {
    return true;
    }

    // If one is null, but not both, return false.
    if (((object)a == null) || ((object)b == null))
    {
    return false;
    }

    return a.Equals((object)b);

    }

    public static bool operator !=(Piece a, Piece b)
    {
    return !(a == b);
    }

    }

    public class Side
    {
    private Col _color;
    private Part _birdpart;

    public enum Col
    {
    Blue,
    Green,
    Pink,
    Black
    }

    public enum Part
    {
    Head,
    Tail
    }

    public Col Color
    {
    get { return _color; }
    set { _color = value; }
    }

    public Part BirdPart
    {
    get { return _birdpart; }
    set { _birdpart = value; }
    }

    public static bool operator ==(Side leftside, Side rightside)
    {
    bool match = false;

    // If both are null, or both are same instance, return true.
    if (System.Object.ReferenceEquals(leftside, rightside))
    {
    return true;
    }

    // If one is null, but not both, return false.
    if (((object)leftside == null) || ((object)rightside == null))
    {
    return false;
    }

    if (leftside.BirdPart == Side.Part.Head)
    {
    if (leftside.Color == rightside.Color && rightside.BirdPart == Side.Part.Tail)
    {
    match = true;
    }
    }
    else if (leftside.BirdPart == Side.Part.Tail)
    {
    if (leftside.Color == rightside.Color && rightside.BirdPart == Side.Part.Head)
    {
    match = true;
    }
    }

    return match;

    }

    public static bool operator !=(Side a, Side b)
    {
    return !(a == b);
    }
    }
    }

  3. My son Uly got this puzzle for xmas this morning. I solved it in less than 6 minutes. The box says that there are 300,000 possible combinations and that only 1 is correct. well, it was easy to solve and now he’s upset because “I ruined it for him.” So, I did learn a lesson from this puzzle==> I shouldn’t play with my kids toys.

  4. my old teacher had this puzzle and ive been hunting for it everywhere, do you know where to get it?

Comments are closed.