Write a program that'd solve the following puzzle:
There is a box of 3x3 movable puzzles, each numbered 1..8. All
the puzzles are randomly mixed creating the starting state, e.g:
As you might already noticed, there is an empty space in the box. That's the place
where neighbor puzzle can shift to. Shifting those puzzles around find the way
to reach the final condition:
1. The heuristic recursive algorithm.
The problem is naturally solved recursively. All possible moves can be represented as a tree.
Generating descendants for each branch and descending into the branches while searching for
the goal state would lead to the solution, but the number of states that can be created by
algorithm is great. Also, the first found solution is not necessarily the shortest one.
To find the optimal way from initial state to goal state I used heuristic algorithm that tries
to determine the best next move before it descends into the branch of the current state.
The algorithm is controlled by the depth limit and visited branches limit parameters.
Lowering the depth limit and/or increasing the visited branches limit is helpful in searching
for the shortest solution of the puzzle.
2. Linear tree search.
The tree of all permutations is the structure of states with four descendants
each. Each descendant represents move in one direction in the puzzle. For many
states only two moves are valid, for some all four. Invalid moves may be
replaced by the NULL pointer in the branch. Also, when the move is about to
repeat the state that is already generated in one of the previous branches, it
should also be considered illegal:
GoalState R0
------------------------
Left Up Down Right
/ | | \
/ NULL | NULL
/ |
State1 LB0 |
------------------------ |
Left Up Down Right |
/ NULL DB1 NULL |
/ State2 DB2
State LB1 ------------------------
Left Up Down Right
/ | | \
/ NULL | NULL
/ |
State3 LB3 |
------------------------ |
Left Up Down Right |
|
State4 DB3
------------------------
Left Up Down Right
The approach to solve the puzzle is to generate all possible descendants of
the goal state in the form of a tree. For 3x3 puzzle we have 9! permutations.
Each configuration has exactly 9!/2 solutions.
Data is represented in the linear tables couple:
Index:
0 1 2 3 4 5 6 7 ...
Tree:
X R0 LB0 DB2 LB1 DB1 LB3 DB3 ...
Parent state index table:
X 0 1 1 2 2 3 3 ...
First row represents the index in the table. The second row represents the
states of the puzzle. The index #0 is not used. The Parent state index table
is used to create the sequence of the moves once the initial state is
generated.
The tree array keeps the values of pointers to the PTree structure:
struct PuzzleTree
{
Box anBox; // represents the state
// descendants
PuzzleTree *pUp;
PuzzleTree *pDown;
PuzzleTree *pRight;
PuzzleTree *pLeft;
// internal use
long lID;
};
typedef struct PuzzleTree PTree;
typedef PTree *PTreePtr;
The InitialState R0 is the actual goal state. It is better to generate all
descendants of the goal state because it gives the image of entire tree of
legal moves. This algorithm is much faster than heuristic recursive one.
Release Notes:
The complete tree is saved in the binary file converted from the type of int[3][3] (Box) arrays
to the adequate int values thus saving the disk space by 6 and speeding up the IO operations on
this file. Once the file exists on the disk, there is no need to generate the new one but to
read it from the file. Searching through the tree represented in the linear table is really fast
so the solution (or it's non-existence) can be found really quickly.
