Introduction: Solving Scramble Squares Puzzles

By Programming Ponderings

A couple of years ago my kids got a Scramble Squares puzzle (http://www.b-dazzle.com/scramble.asp) from their grandmother. A Scramble Squares puzzle contains nine squares puzzle pieces. The edge of each piece has half an image on it (e.g. the head of a zebra, the tail of an elephant, etc.). The puzzle pieces must be arranged in a 3 x 3 grid so that the images on the edges line up correctly (e.g. the head of the zebra is against the tail of the zebra). The actual puzzle my kids received was the Serengeti puzzle. After spending a couple of hours trying to solve the puzzle, I decided to write a computer program that would do it for me.

This Instructables explains how to use that program to solve any Scramble Squares puzzle.

Step 1: Puzzle Piece XML

The Scramble Squares Solver program uses an Extensible Markup Language (XML) file to describe the puzzle pieces. The following is an example of what the XML for each puzzle piece looks like:

<PuzzlePiece>
   <Name>A</Name>
   <North>
      <Image>Zebra</Image>
      <Half>Bottom</Half>
   </North>
   <South>
      <Image>Giraffe</Image>
      <Half>Bottom</Half>
   </South>
   <East>
      <Image>Rhinoceros</Image>
      <Half>Top</Half>
   </East>
   <West>
      <Image>Elephant</Image>
      <Half>Bottom</Half>
   </West>
   <CenterImageDirection>NorthEast</CenterImageDirection>
</PuzzlePiece>

Each piece can be given a unique name, designated by the Name element. Each piece has a North, South, East, and West side defined. Each side consists of two elements: Image and Half. Image indicates what picture is on the edge and Half indicates if it is the Top half or the Bottom half of the image. The value use you for Image and Half can be anything you like, but you must be consistent. There should only be four unique Image values and two unique Half values.

Each puzzle piece also has an image in the center. I was not sure if this image had anything to do with the solution to the puzzle or not, so I included an element to indicate which direction this image was rotated. As it turned out, this image is not significant, so this is not really necessary.

Step 2: Puzzle XML

The following is an example of what the XML for the entire puzzle looks like (I excluded the contents of the PuzzlePiece elements to save space):

<ScrambleSquaresPuzzleFile><br>  <NumberOfRows>3</NumberOfRows>
  <NumberOfColumns>3</NumberOfColumns>
  <PuzzlePieces>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
    <PuzzlePiece>…</PuzzlePiece>
</ScrambleSquaresPuzzleFile>

The puzzle XML contains three elements. The first, NumberOfRows, indicates how many rows of pieces should be in the solution. The second, NumberOfColumns, indicates how many columns of pieces should be in the solution. The last, PuzzlePieces, contains the list of puzzle pieces that make up the puzzle.

Step 3: Scramble Squares Solver Algorithms

The program I wrote implements various algorithms to solve the Scramble Squares puzzle. The quickest of these algorithms is what I called the “Edge Solve Algorithm”. It first determines for each side of each puzzle piece which other puzzle piece edges would match it. Then it only attempts to build the solution to the puzzle using known matching edges. This significantly reduces the number of possible solutions that needed to be tested. In the case of the Serengeti puzzle, only 10,699 solutions had to be attempted, rather than 95,126,814,720, which is how many solutions the other algorithms must test. This algorithm can take less than a second to solve the puzzle (depending on the speed of your computer).

It takes the computer hours to solve a puzzle using any of the other algorithms included in the Scramble Squares Solver program. If you would like to read more about the other algorithms, see the following article: http://mheironimus.blogspot.com/2015/01/solving-scramble-squares-puzzles.html.

Step 4: Scramble Squares Solver Program

You can download my Scramble Squares Solver program at https://static.heironimus.info/instructables/scramble-squares/ScrambleSquaresSolver.zip. You can also download the source code and unit tests for the program at https://static.heironimus.info/instructables/scramble-squares/ScrambleSquaresSolverSource.zip. This program will only work on Microsoft Windows Vista and above.

Both downloads include the XML Puzzle Files for the following puzzles:

Unlike the other puzzles, the Butterflies puzzle actually has eight solutions (two solutions rotated four ways).

To solve a puzzle run the ScrambleSquaresSolver.exe program. Verify the "Edge Solve Single Threaded" engine is selected and click the "Select & Solve" button. An "Open Puzzle File" dialog will appear that will allow you to select a Puzzle File (*.pml). After selecting the desired puzzle file, click the Open button. The program will then proceed to solve the puzzle.

Step 5: Scramble Squares Solver Program Output

Once the Scramble Squares Solver Program has solved the puzzle, it will display the solutions it found to the screen. The format of the output is as follows:

Solution #1
Row #1:
Column #1: B (Up: Red Car-Top, Right: Black Car-Bottom, ...)
Column #2: A (Up: Blue Car-Bottom, Right: Green Car-Bottom, ...)
Column #3: G (Up: Green Car-Bottom, Right: Black Car-Top, ...)
Row #2:
Column #1: D (Up: Blue Car-Top, Right: Green Car-Top, ...)
Column #2: I (Up: Blue Car-Bottom, Right: Black Car-Top, ...)
Column #3: F (Up: Red Car-Bottom, Right: Red Car-Top, ...)
Row #3:
Column #1: H (Up: Black Car-Bottom, Right: Green Car-Bottom, ...)
Column #2: E (Up: Red Car-Bottom, Right: Red Car-Bottom, ...)
Column #3: C (Up: Blue Car-Bottom, Right: Green Car-Bottom, ...)

The three puzzle pieces that make up the first row are listed first in left to right order, followed by the second and third row's pieces.