A Scramble Squares Solver

The 'Scramble Squares' puzzle (made by b. dazzle, inc.) is a 3-by-3 grid of 4-inch square puzzle pieces. The goal is to place the 9 puzzle pieces such that the pictures along each edge mesh correctly. Each puzzle has a theme. The puzzle I received one Christmas used pictures of four famous airplanes: the Wright Flyer, the Spirit of St. Louis, a B-17 bomber, and the Red Baron's Fokker (which I can't even write down without hearing my Dad's voice intone "Wait ... I think that Fokker's a Messerschmitt!"). The design is such that all the airplane pictures are split along the interior borders between puzzle pieces in the 3-by-3 grid, and you have to arrange the pieces so that the left and right half (or top and bottom) all match up. It takes about four frustrating hours to realize just how "simple" it really is.

When I Googled 'Scramble Squares', I found a little 4-page paper by Keith Brandt, Kevin R. Burger, Jason Downing, and Stuart Kilzer of Rockhurst University in Kansas City entitled "Using Backtracking to Solve the Scramble Squares Puzzle". The paper describes their algorithm for solving such a puzzle using a very clever recursive method that rapidly clears the search space of possible combinations that need to be considered.

---

Let me make an attempt to describe their approach to the problem (it's a good paper ... any lack of clarity here is mine own):

- Number the squares of the 3-by-3 grid such that the first piece goes in the middle (Place 0), then advancing counter-clockwise starting due East at Place 1 around to Place 8. Like so:

+---+---+---+
| 4 | 3 | 2 |
+---+---+---+
| 5 | 0 | 1 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

- Loop through the nine pieces available, on each iteration putting a different piece in the middle position (Place 0).

- With a piece in Place 0, move to Place 1, and loop to see if any of the remaining eight pieces has an orientation where its Western edge "fits" the Eastern edge of the piece in Place 0. Since these are the only two pieces on the board so far, it is the only edge that matters.

- If you find a match, leave those two pieces in place and see if you can find, looping among the remaining seven pieces, one that can be oriented such that its Southern Edge "fits" the Northern edge of the piece in Place 1. Again, since we are placing the pieces down in a predetermined order, this is the only edge that matters.

- If you can get to Place 3, things are a little different ... the remaining pieces have to be checked whether they match along the Eastern and Southern edge. Every time you fail to find a piece that lets you proceed to the next Place, you let the algorithm roll back to the previous position and pick up its checking where it left off in the previous loop. Recursive algorithms help keep this sort of place management relatively simple.

- If you can make it to Place 8 and the remaining piece matches, in one of its orientations, along the Western and Northern edges, then you've found a complete solution!

Instructions below the form that follows describe how to set up a Scramble Squares puzzle to be solved using this script. It involves lining up your puzzle pieces on a table, and assigning a simple code that represents the half- pictures on the edges of each piece. Fill in the blanks correctly, press the "Solve" button, and (if you did it right) one or more (it is usually two) schematic diagrams are printed that show where each piece should be placed and how many turns clockwise it requires for a fit.

Piece Number	Value	State (basic tests of a valid entry)
0		Looks okay!
1		Looks okay!
2		Looks okay!
3		Looks okay!
4		Looks okay!
5		Looks okay!
6		Looks okay!
7		Looks okay!
8		Looks okay!
		Enter data for all nine pieces, then press 'Submit'

Although a C program and Perl script have been provided, C seems to be waning in popularity and Perl requires that, well, Perl be installed. Some users are up for that, but many are not. I've specifically noticed that on a Mac running OSX (which is basically Unix with Perl already installed), many people still have trouble getting the script to work. (Not me ... my G3 iMac running Tiger gets through the Perl script without incident ... but "it works on my machine" is a tired excuse.)

Instructions for encoding your puzzle follow, using the "Airplanes" Scramble Squares puzzle as an example. Start by lining up your nine pieces in a row on a table top, and to each affix a post-it note, and number each piece from 0 through 8 (yes, I know, 1 through 9 seems more intuitive, but in C and Perl, you get used to numbering things starting from 0 ... so sue me.) Use the post-it note to record this number and to determine which edge for each piece is the "top" edge (since a piece may have to be spun to a new orientation in the solution, we need to know where we start from!)

Look at the table below. Each Scramble Squares puzzle is a matrix of nine square puzzle pieces, and the subject of each puzzle are four pictures related by a theme. Each of the four pictures is split in half (front/back or top/bottom), and the object of the puzzle is to assemble a 3-by-3 board in which all of the shared edges match up the correct tops and bottoms (or fronts and backs). This means there are eight picture "halves" (four pictures, each cut in half). Assign each of these different picture "halves" a letter, such that A and B are the two halves of the first picture, C and D the halves of the second, E and F the halves of the third, and G and H the halves of the fourth.

A: Back of Fokker	B: Front of Fokker	C: Back of St. Louis	D: Front of St. Louis
E: Back of Wright	F: Front of Wright	G: Top of Bomber	H: Bottom of Bomber

With this "cheat sheet", matching each distinct picture half to one of the letters from A through H, record the letters that go with the pictures on each of the nine puzzle pieces. I put this information right on the post-it note. Write down the four letters corresponding to the half-pictures on the right edge, top edge, left edge, and bottom edge of the puzzle piece IN THAT ORDER.

Then transcribe the four letter codes for each piece into the form above and press the Solve button. If you did it right, you'll usually see two solution "schematics" following the form (if you do it wrong, you may see none, or you may see several ... two is the usual number for a standard puzzle).

The schematic will show the three-by-three grid of the final solution. Each position shows a pair of numbers. The first number is the puzzle piece (0 through 8) that goes in that position. The second number is the number of quarter-turns clockwise from its original position it needs to be "spun" through so that the edges line up correctly.

Implementation Notes

I put this project off for a long time, because it meant porting a Perl script that worked to PHP. I really like PHP, but have had trouble finding a good Integrated Development Environment (IDE) for it. To do this job, I evaluated the Zend Studio Professional, version 5.0, which turned out to be a very nice tool. The $100 price tag for the Personal edition is reasonable (the Zend site in general is full of a lot of helpful tutorial information ... those guys do nice work.)