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