Backtrack technique to solve Chinese Slide Block Puzzle (Hua Rong Dao)

• Download source - 11 Kb

Introduction

Chinese Slide Block Puzzle (Hua Rong Dao) was my favorite game. I used to spend hours pondering on how to solve it. So, when I learned backtracking technique, I immediately chose to try on it.

Back tracking

First, let's have a little introduction on backtracking. Backtracking is a systematical method to iterate through all the possible configurations of a search space. In general, a backtrack algorithm looks like this:

bool backtrack(int step, Solution candidate, Data input)
{
    if (IsASolution(candidate, step, input))
    {
        processSolution(candidate);
        return true;
    }
    newCandidates = CreateNewCandidates();
    foreach (Solution s in newCandidates)
    {
        bool finished = backtrack(step + 1, s, input);
        if (finished) return ture;
    }
    return false;
}

While iterating through the search space, I must make a decision which algorithm to use: Depth first search (DFS), or Breadth first search (BFS).

DFS

The above pseudo-code is actually using DFS. In general, DFS is more memory efficient since it does not store all the candidates in a queue. However, DFS has two problems:

• If I hit a solution, I don't know whether it is the best solution or not.
• If I run into a very deep branch in the search tree before hitting the solution, it will take a very long time.

To solve the first problem, I don't stop the search when I hit a solution. Instead, I continue to traverse the tree, and compare the solutions to find the best one. To solve the second problem, I arbitrarily choose a fixed depth bound. If the bound I choose is too small, I may not find any solution at all. In that case, I iteratively deepen the search limit until I find a solution.

BFS

The alternative to DFS is BFS. The pseudo-code for BFS backtracking is:

bool BSFbacktrack(Data input)
{
    queue.Enqueue(firstCandidate);

    while (!queue.empty())
    {
        candidate = queue.Dequeue();

        if (IsASolution(candidate, input))
        {
            processSolution(candidate);
            return true;
        }

        newCandidates = CreateNewCandidates();

        foreach (Solution s in newCandidates)
        {
            queue.Enqueue(s);
        }
    }
}

In BFS search, I have to store the new candidates in a queue. So, BFS requires more memory than DFS. However, unlike the DFS, its first solution is the best solution.

Decide to use DFS or BFS

Because I want the best solution, BFS algorithm is exactly what I want. As I talked above, the limit of BFS is its memory. Let's calculate how much memory I need. In the Chinese slide block puzzle, I need to move at least 116 steps to reach the goal. So, the queue must hold all the configurations for step 115. If each step has two options, then I have to store 2^115 nodes in the queue. This is certainly way too many. Fortunately, there are only 10 pieces of tile. So, the configuration of the puzzle is less than 10!<2^22. If I keep track of all nodes that I have visited, I can skip those nodes that I have visited to save memory. More importantly, this technique avoids loops. So, it is important for both BFS and DFS.

In my program, I have tried both DFS and BFS. I compare the two results to verify the program is correct. Interestingly, I found that the BFS is 60 times faster than DFS in my program. This is certainly not true in general.

Hash of the puzzle

To speed up the comparison of two configurations, I compute the hash of each case as a long number. Because the size of the puzzle is 4*5, the coordinate only needs 2+3=5 bits. There are 10 pieces of tile in the puzzle, which adds up to 50 bits. Since the size of long is 64 bits in C#, I can represent each configuration of the puzzle in one long number.

Design pattern in the class hierarchy

There are many variants in this program:

• There are five layouts of the puzzle.
• There are two search algorithms.
• There are four kinds of tiles, with different shapes and sizes.
• Each tile can move in four directions.

In the beginning, I found that I was using a lot of (switch/if) conditional statements. The same logic is repeated in many functions. This is a clear indication that I need to use design patterns here. After reviewing the class I took from NetObjectives, I realized that visitor pattern is exactly what I needed.

Vistor pattern is also called double-dispatching. Its idea is to move the decision making from run-time to design stage.

In my design, Tile is a visitor to IDireciton. Four functions are defined for each visitor: MoveUp, MoveDown, MoveRight, and MoveLeft. In the visited class IDireciton, I define a function Accept(Tile). This function is a dispatcher (virtual function) which is implemented in IDireciton's four child classes Up, Down, Left, and Right. The class hierarchy is:

Background of the Chinese Slide Block Puzzle (Hua Rong Dao)

In the three-Kingdom dynasty, CaoCao was the most powerful king. He invaded the other two kings with a mighty army. However, in the war of ChiBi, CaoCao was defeated by the union of the other two kings. In the escaping route, CaoCao was caught by General Guan Yu. Because Caocao had been very generous to him during his difficult time, General Guan Yu decided to let Caocao pass, even in the risk of the death punishment. Your goal is to help Guan Yu arrange his generals and soldiers to let CaoCao escape.

You can find the game here. In my program, I print the puzzle in this format:

2003
2003
4115
4785
6**9
-xx-
exit

There are totally ten pieces in this puzzle. Caocao is the biggest block (2X2) with number 0. General Guan Yu is the horizontal rectangle with number 1. The four vertical rectangles, numbered 2 through 5, represent four generals. The last four small blocks, numbered 6 through 9, represent four soldiers. The only two empty spaces are marked with '*'.

The rule of the game is to move the big block 0 to the bottom.

There are also other layouts of the initial state. You can find all the layouts and solutions in the bottom of the source code. Here is the easiest layout and its solution.

Initial state:
6711
0022
0033
8944
*55*
Solve the puzzle in 20 steps:
5R[001] 8D[002] 9D[003] 0D[004] 2L[005]  2L[006]  3U[007]  4U[008]  5U[009]  9R[010]
6711    6711    6711    6711    6711     6711     6711     6711     6711     6711
0022    0022    0022    **22    *22*     22**     2233     2233     2233     2233
0033    0033    0033    0033    0033     0033     00**     0044     0044     0044
8944    *944    **44    0044    0044     0044     0044     00**     0055     0055
**55    8*55    8955    8955    8955     8955     8955     8955     89**     8*9*

8R[011] 9R[012] 8R[013] 0D[014] 4L[015]  4L[016]  5U[017]  8U[018]  8R[019]  0R[020]
6711    6711    6711    6711    6711     6711     6711     6711     6711     6711
2233    2233    2233    2233    2233     2233     2233     2233     2233     2233
0044    0044    0044    **44    *44*     44**     4455     4455     4455     4455
0055    0055    0055    0055    0055     0055     00**     008*     00*8     *008
*89*    *8*9    **89    0089    0089     0089     0089     00*9     00*9     *009

The step number is in bracket. The first move is 5R, which means move the block 5 to right. The second step is 8D, which means move the block 8 down. The third step is 9D, which means move block 9 down, etc...

The implementation platform

The program is implemented with C# 2.0 and VS.NET 2005 Beta 2 because I really like the generics.