Solving Scramble Squares - Backtracking Algorithm in C#

• Download source - 15.9 KB

Table of Contents

• Introduction
• Background and solving methodology
• Implementation

Introduction

B-Dazzle Company introduces a game known as (Scrambled Squares) or Scrabble Squares. The game has a multi patterns; some of colored, some not, ... etc. You can find this puzzle game at the official site www.b-dazzle.com.

The game consists of 4, 9 or 16 squares arranged in d X d array. Here is an example ….

A student called me – couple months ago – asking for some help. He faced some problems when studying the problem. I illustrated it, so I’ll put this solution here with illustrations.

The best web site that talks about this problem I found is www.public.asu.edu/~kburger2/scholar/scramble/scramble.html, it contains a PDF file that demonstrates the problem. The code is also provided as JAVA applet.

In this article, I’ll introduce you to the solution step by step explaining the algorithm and data structure used to solve the problem.

What is the Problem?

You may notice that each separated square has 4 different sides. Take the first square (for example) and you’ll see 4 skiers, but not all the skier’s body appears, you can see either upper part of the body or lower part. Also, you’ll see that every body part has a different color. Some squares contains 4 different colors, others have only 3.

In this game, your job is reordering or rotating each square to form a complete board whereas every body part from one square side should complement the adjacent square side, and the color must be the same.

This work must be coded … and we should first understand the problem and developing an algorithm, taking into account the best understandable way for programmers.

Background and Solving Methodology

Suppose you have a board of 2 X 2 squares.

To solve the puzzle, you will follow these steps:

• Consider sq1 (square no 1) in position 1.1 (first row. first column)
• Now you have to try sq2 in the next position 1.2, and check if both sq2 left side can complement the sq1 right side.
• If yes, then we proceed to the position 2.1 with sq3 and so on.
• else we have to rotate sq2 (e.g. to left) and recheck the compatibility
• We can try to rotate the sq2 three times each must recheck the compatibility, if this rotation was not useful then you replace sq2 by sq3 in the position and retry same steps
• If no square can complement sq1 in position 1.1, we have to rotate sq1 and try all previous steps.
• If rotation 3 times and trying not useful for sq1, you have to replace sq1 by sq2 and repeat steps above
• And so on …..

This redundant iteration and steps will fit with the Recursive Algorithms that we’ll discuss. These type of recursion algorithms are called BACKTRACKING ALGORITHMS, because we can try a step, if succeeded we’ll proceed; if not we’ll roll back and change the previous step, then try … and so on. These algorithms depend on error and experimentation.

Now, how much does it take? Let us talk about it mathematically….

1. Each square is rotated in any position 3 times
2. For each position, we have n permutations

Where n = total elements (squares) count.

So for each partial solution, we have 3n Rotations, and we have (n!) Replacements, Wow, this is a huge number of transitions and rotations, especially if you play larger dimension game.

So, for our example, we have 3^4 X 4! = 1944 (movements in worst case). Now, it is clear why we need a computer program to solve this problem.

Now you understand the backtracking algorithm, which I implanted in the code.

For each position in this board, starting in position 0, we shall put a card, then we have to try all available cards to fit the next position, to do so, we can compare the top and left sides of the current card with the existing cards.

Suppose you reached position 4, you must compare the top side of current experimental card with the bottom side of the card positioned in place 1, and compare left side of current experimental card with the right side of the card positioned in the place 3.

If the experimental cards fits in this position … that’s ok we can proceed to the next position, if not … the card must be rotated in the position, and retry the comparisons. If the card rotated 3 times … this means you tried all available rotations of this card in this position, you have to replace your card by next card that is not used yet and retry the previous steps, if no card accepted in this position, then we have to BACKTRACK to the previous position in board (position 3) and try to rotate the card then redo all.

Aha… this is a summary of what this algorithm do.

The pseudo code for each backtrack algorithm is as follows:

TrySolve()
{ 
Initialize selection of candidates;
Do { 
Select next candidate;
If (acceptable)
{ 
Record it;
If (solution incomplete)
{ 
Try next step;
If (not successful)
Cancel recording;
} 
} 
} while (not successful) and (remains of candidates);
} 

That means, in our algorithm:

• Take position x
• For each card ( crd ) available … (not used in another position)
  • Compare crd.left with left_crd.right && crd.top with upper_crd.bottom
  • If comparison is OK
    • Register this partial solution in draft
    • Try same steps for position x+1
    • If position x+1 solution not succeeded
      • Unregister x partial solution
  • Rotate crd in position x and try again

Backtracking algorithms as mentioned above depend on error and experimentation which means any partial solution that was not able to construct another partial solution upon, to achieve the main goal, is removed and try other piece of puzzle.

The best example of this algorithm is a chess horse movement. And others.

Implementation

• Input files format
• The classes (project structure)
• Step by step

You should now realize some facts:

• Writing the solution using OOP methodology is for obviousness and ease of understanding purpose only. You may notice the performance is not as you hope.
• I focused on the algorithm and code structure rather than the input and output forms, so you can develop a new code that uses graphical form for input and output.

Input File Format

Suppose the previous square we will name it a CARD. This card has four sides TOP, RIGHT, BOTTOM, and LEFT. Each consists of body’s PART (upper part, lower part) and COLOR. So this card is written as this form in the input file:

CardName	top-color	right-color	bottom-color	left-color
0	HEAD-VIOLET	TAIL-BLUE	HEAD-VIOLET	HEAD-YELLOW

Now look at this file, it will be used for test and it is packaged with the source as well.

This file is for constructing a /3 X 3/ game board, notice it has 9 items start from 0 to 8.

And these cards distributed in the array form in a row like the figure …

The Classes and Methods

Let us take a closer look at the code.

1- CardReader: Reading the card input file and store it as mentioned above.

This class contains 4 methods, the main one is MakeAllCards, this method reads file’s row and passes the row to MakeCard method which separates each side components using GetPart and GetColor methods, then it constructs 4 sides, creates new card and return this card to MakAllCard method. It repeats this procedure till the file ends.

The input file format is linked to this class, if you wish to change file format you have to change this class to suit a new format.

2- Part , PartColor enums: enumerates parts <HEAD|TAIL> and part colors <RED|BLUE|GREEN|YELLOW> (4 or more color)

The color and part enums are used to construct Side class, since the side should be compared with another card side we can assign a numeric value to every color and part. Now take this equation:

Part <HEAD = 1|TAIL = -1>

Color <RED=1|Blue=2|Green=3|Yellow=4>

3- Side: creates one side of the square/card which contains the pair PART-COLOR

This class is the basic one in the code; it represents a side of square, and has a numeric value that distinguishes it from another side depending on PART-COLOR dual.

Suppose a side1 <Head|Green>, side2 <Tail|Green> and side3 <Head|Blue>

If you calculate the value of each one, you find: 3, -3 and 2 respectively.

So you can say side1, side2 and side3 are not equals, but side2 complement side1.

Each complements if added together must return 0.

It contains a Boolean method CanJoin(Side side) that decides if this side is complementary of the parameter side. The value of the side can be obtained from the public property Value that calculates it.

4- Border: Contains 4 sides and forms CARD base class

Border class has 4 sides and integer value that changes in every rotation, also has Rotate() method which changes the sides in a circular way Then it increments Orientation property, it can rotate while orientation less than 3.

5- Card: derived from BORDER but add new properties … etc.

So it has Border properties in addition to new properties like name, position, …etc. the most important method in this class is IsCompatible(Card left, Card top) method, which returns true if this card can be positioned in this place and compatible with upper and left cards. It uses side’s method (CanJoin(side s)) to decide the compatibility.

But you can notice that every previous class contains Clone() method, that implanted manually … you can get IClonable interface help.

6- DraftSpace: a representation of empty game board that holds the solution cards temporary to build a solution.

This class is only for handling the solution temporarily, and you can drop it, but using it makes the code more ordered. The method TryAdd(card c) is used for filling the draft array depending on its position and neighbors cards, it is an empty array d X d representing the game board.

7- Result: represents the solution.

To store the solutions we invent this class, also you can drop it because we display the first and only first solution. I didn’t complete the code to discover other solutions, but you have to.

8- ScrambledSquares: main class that implements the algorithm

The main class in the problem, contains Solve(int x) method. This method implements backtracking algorithm, in addition it has some helper methods such PickCard(int position) since we pass the position as a one number instead of ( X,Y ) in the array, and RegisterSolution method to register a solution in the Result instance (as I said for multiple solutions, but now one solution ).

Step by Step

In the Solve(int position) method in the ScrambledSquares class, you see:

logger.WriteLine("----------------------------------------------");
logger.WriteLine("Position = {0}\t\t\tSearch depth = {1}", pos, SearchDepth);
++SearchDepth;

The logger is just a file writer that writes each step to see how the program works, SearchDepth is an integer property that is incremented in each call for this method to see the depth reached.

if (pos == MAX_CARDS)
{
   logger.WriteLine("Done");
   RegisterResult();
   draft.Clear();
   return true;
}

This snippet of code is to determine if we succeed having a solution, in the recursive algorithms we have to use a stop code according to some conditions that decide the success or failure. Now for our stop code, if we reached the position that is out of array boundaries, then we have a solution otherwise the recursion is not finished yet.

Now the iteration over all the cards is to determine a best card in the current position.

for (int current = 0; current < MAX_CARDS; current++)
{
    Card c = PickCard(current);
    if (!c.Used)
    {
        c.ResetOrientation();
        while (c.CanRotate)
        {
            if (draft.TryAdd(c, pos))
            {
                logger.WriteLine("((TRY)) {0} --> {1} after {2} rotation", c.Name, pos, c.Orientation);
                c.Used = true;
                c.Position = pos;
                if (Solve(pos + 1))
                {
                    return true;
                }
                c.Used = false;
                logger.WriteLine("[REJECT] {0} from position {1}", c.Name, pos);
            }
            c.Rotate();
            logger.WriteLine("<<ROTATE>> {0} in position {1}", c.Name, pos);
        }
    }
}
return false;

We start searching from 0 using PickCard method, it brings a card by one number instead of two (row and column) by calculating the row and column values, like that:

private Card PickCard(int pos)
{
    try
    {
        return cards[pos / dimension, pos % dimension];
    }
    catch (Exception)
    {
        return null;
    }
}

(Pos / dimention) will return the row, (pos % dimension) return the column; this is applicable for all n X n arrays. But if the position is out of range of array, it returns null value.

Back to main code, the picked card must be not be used before in any place so we discuss the stat of the card; if not used we proceed; else we pick another card and so on.

if (!c.Used)

To ensure that the picked card is rotatable, we should first reset its orientation, then we’ll try all available rotations in the current position, so we start a while circle among all available card rotations to try a card with all rotations.

c.ResetOrientation();
while (c.CanRotate)
{
}

If the card is acceptable in the current position, it will be added to draft board, marked as used, then we try to repeat those actions for position+1 ( next position in the game board).

if (draft.TryAdd(c, pos))
{
  c.Used = true;
  c.Position = pos;
  if (Solve(pos + 1))
  {
    return true;
  }

If all positions are visited, this means all cards are positioned in the preferred stat and position.

If not, that means the card is not in perfect position, so if it can be rotated, we rotate it otherwise we set the card is not used and proceed to the next card:

c.Used = false;

If all cards are experimented without any result, it returns as fail.

We have 2 output files, one for the result – if it exists – and the other for log, in the log file you will see the steps taken for solving the problem

Thanks for reading!