puzzle solver, part II

In a previous post, I discussed my attempt to write a program to solve a puzzle. I never updated that post because, well, I ran the program all night and it didn’t find the solution!

I had made up a fake puzzle that I knew had a solution for testing, and the program could solve it in 15 minutes. But it couldn’t solve the one I had recorded for the real puzzle. I figured (and hoped) that I had simply recorded it wrong and to check, I re-recorded the pieces and tried again. And it worked! Here’s how:

Preamble

The program (I’ll just call it puzzleSolver) was written in C++, since that’s the only language in which I am at all competent. I’m self-taught, and only for the past half-year or so, which means that there will likely be better ways to do a lot of the things that follow. This project was mostly to practice my C++ writing, so if you have a suggestion or comment on the code or algorithms, please drop it in the comments!

Modeling the Pieces

As explained in the previous post, I used the numbers 1-4 to represent the different shapes so that it would be easy to model the pieces and test for matches.

Fig. 1: Number assignments for representing the puzzle shapes.

I then went through the puzzle pieces and recorded the values for their shapes clockwise from the top (of course, I could have started anywhere as long as I was recording them the same direction). For example, the two puzzle pieces in Figure 1 would be written as (top, right, bottom, left) = (-3,-2,-1,-4) and (3,4,1,2). The real puzzle pieces each have two negative shapes and two positive shapes.

For the program, I created a class called piece to model the real puzzle pieces. The digital puzzle pieces need to have variables representing the values of each side, the ability to be rotated, and the ability to be represented on the screen (printed) so that the user can see the results. So, I defined the class as follows:

class piece
{
public:
    piece ( int top, int right, int bottom, int left, int ID);
    void print()  ;
    void rotate() ;
    int  id       ;
    int  mTop     ;
    int  mBottom  ;
    int  mLeft    ;
    int  mRight   ;
};

For anyone not familiar with Java or C++, that likely looks awfully cryptic. I’ll (very) briefly explain each part:

The word public just makes it so that the program has complete access to everything inside the class piece.

Following that, you see piece( some stuff ). This is a constructor, which just means that when I want to create a puzzle piece in my program, I have to type “piece( blah, blah )”. The things on the inside are the values that piece needs in order to become a legitimate model of a puzzle piece. Int simply stands for “integer” (i.e. …,-2,-1,0,1,2,…) because C++ likes to know what kind of values it is working with (since the values could otherwise be characters, decimal numbers, etc). The word after int is a stand-in for a value defining some aspect of the puzzle piece. Top represents the shape on the top of the puzzle piece, and so on. ID is just a value to keep track of which puzzle piece is which.

End result: if I were to type “piece( 3,4,1,2, 9)”, into my code, then the program would create a digital puzzle piece where the top is of value 3, the right of value 4, and so forth. The value 9 is the piece’s ID. In fact, the piece that this creates is the same as the right-side puzzle piece in Figure 1!

piece constructor
Fig.2: The piece constructor.

Okay, moving along to the next two lines that start with void. Ignore this, the important stuff is what follows. print and rotate are two functions that I wanted a puzzle piece to have. In C++ you have to declare these functions first (in other words, say “hey C++, I will be using a function by this name that requires these values to work. I’ll tell you how it works later.”) So, I’m telling the program that I’ll later define functions called print and rotate, and neither require any values (which is why the parentheses following are empty).

So far so good? The last things should look familiar, since they are the values that are in the constructor! In other words, these are the things that actually remember the values that you give to the constructor. So, when I made puzzle piece number 9 by typing “piece( 3,4,1,2, 9)”, what actually happened was the the values of id, mTop, and so on were assigned those values and will now remember them.

At this point we have told the program that we want to be able to print and rotate the puzzle pieces, but we haven’t told it how. I’ll ignore the printing function, since it isn’t relevant to an understanding of how this program will solve the puzzle.

Rotation

Why does’t the rotate function require any values? How will it know how much to rotate?

The puzzle pieces can only be rotated in 90° increments, and so any larger rotation is the same as the 90° one applied several times. A 180° rotation is just two rotations of 90°. This means that we only need a function that turns the puzzle piece by the minimum increment. The direction doesn’t matter (counter- vs. clockwise) as long as it is the same every time. So, the function rotate() will always do one 90° clockwise rotation of a puzzle piece. Here’s the code:

void piece::rotate()
{
    int temp ;
    temp    = mTop    ;
    mTop    = mLeft   ;
    mLeft   = mBottom ;
    mBottom = mRight  ;
    mRight  = temp    ;
}

So what’s happening here? The first thing that happens is a new variable, called temp for temporary is made, and then we give it the top value of the puzzle piece. We do this because the program is about to change the value of Top, and we don’t want to lose the old value.

Now, we simply need to swap out values in what will be, in our minds, a circular fashion. The following gif should (hopefully) clarify what the code does:

rotation of puzzle piece object
Fig.3: Visualization of rotation() function.

Next Steps

Now that we have a C++ object to represent any puzzle piece, and the ability to rotate those pieces, we next need to figure out how to

  1. represent the entire 9-piece puzzle;
  2. rearrange the pieces of the puzzle in every possible way;
  3. within each arrangement, rotate the individual pieces in every possible way.

Clearly, there is a lot left, so I’ll come back later with another installment.

2 thoughts on “puzzle solver, part II

  1. Or maybe I won’t! It’s been so long since I wrote the code now, I probably won’t be able to figure out what I did…

  2. OK… you are officially a bad man for not finishing this post. I started writing an application that solves this SAME problem! After an hour of coding… I decide to see if anyone else took on the same challenge and I came across your post. My design was very similar down to assigning positive and negative values for inny and outty… My algorithm had a “game board” of 9 positions and started top left finding a candidate for that position and walking across the board finding matches for each position until it failed to find match and then would backtrack with each position until it decided that that candidate piece for that position was not valid. I was anxious to see your solution… but then saw your follow up post that said you no longer had the post…Baaaaad programmer. Baaaaad programmer

Comments are closed.