Solving Scramble Squares Puzzles

A couple of years ago my kids got a Scramble Squares puzzle (https://scramblesquares.com/) 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 - https://scramblesquares.com/product/serengeti-scramble-squares/). After spending a couple of hours trying to solve the puzzle, I decided to write a computer program that would do it for me.

XML Puzzle File

First I defined an XML representation of each puzzle piece:

<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 could be given a unique name, designated by the Name element. Each piece had a North, South, East, and West side defined. Each side consisted of two elements: Image and Half. Image indicated what picture was on the edge and Half indicated if it was the Top half or the Bottom half of the image. 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.

Next I defined an XML representation of the entire puzzle:

<ScrambleSquaresPuzzleFile>

  <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 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.

Brute Force Algorithm

My first attempt to solve the puzzle was to use a brute force algorithm that would try every possible permutation. There are nine pieces in the puzzle and each piece can be rotated in four different directions. The following formula can be used to determine how many possible solutions must be tried:

(# of sides)^(number of pieces) * (number of pieces)!

4^9 * 9! = 262,144 * 362,880 = 95,126,814,720

It turns out that 95 billion possible solutions is a lot, even for today’s fast computers. On my HP Pavilion HPE with a 3.4 GHz Intel Core i7-2600 processor, it took over 26 hours to solve the puzzle. It found four solutions (basically one solution rotated four different directions). I was happy to know the solution to the puzzle, but I was determined to reduce the time it took to solve the puzzle. No one wants to wait a full day to find the solution to a puzzle.

Multi-Threaded Brute Force Algorithms

Because the original algorithm was single threaded, it was only using a small portion of the available CPU power. My next set of solutions used various multi-threading techniques to break the work up into parts that could be done in parallel. In one I used the .NET Parallel.ForEach function (https://learn.microsoft.com/en-us/dotnet/api/system.threading.tasks.parallel.foreach) to break up the work. In another I used .NET Tasks (https://learn.microsoft.com/en-us/dotnet/api/system.threading.tasks.task). I also tried .NET Threads (https://learn.microsoft.com/en-us/dotnet/api/system.threading.thread). All of these solutions still tried all of the 95,126,814,720 possible solutions, but did so using most of the available CPU power. These algorithms got the solving time down below 10 hours, but that was still a long time to wait to solve the puzzle.

Edge Solve Algorithm

The final algorithm I attempted first determined for each side of each piece which other puzzle piece edges would match. Then it would only attempt to build the solution to the puzzle using known matching edges. This significantly reduced 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. The program could now solve the puzzle in under a second.

Scramble Squares Puzzles

I have used this program to find the solution to the following four Scramble Squares puzzles:

• Serengeti (https://scramblesquares.com/product/serengeti-scramble-squares/)
• Pufferbellies (https://scramblesquares.com/product/pufferbellies-scramble-squares/)
• Butterflies (https://scramblesquares.com/product/butterflies-scramble-squares/)
• Classic Cars (https://scramblesquares.com/product/classic-cars-scramble-squares/)

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

Scramble Squares Solver Program

You can download my Scramble Squares Solver program at https://static.heironimus.info/instructables/scramble-squares/ScrambleSquaresSolver.zip. You can download the source code and unit tests for the program at https://static.heironimus.info/instructables/scramble-squares/ScrambleSquaresSolverSource.zip. You can go to https://scramblesquares.com/ to purchase your own Scramble Squares puzzles.