TreeProblemFramework - Usage guide
TreeProblemFramework (TPF) is a .NET Core class library to solve puzzles whose solution is found by performing a tree search. TPF receives as input a description for a puzzle and outputs the steps that reach a solution. This guide explains the functionality of TPF and is divided into two parts.
- Part 1: Presents the TPF's core concepts required to provide it with a puzzle to be solved (an input).
- Part 2: Explains how concepts shown in Part 1 are represented in code and how they are exposed as an API. Then, several links to the API reference are provided.
It is assumed that the reader has a well set knowledge of algorithms, data structures and programming (mainly OOP).
Describing a puzzle
In order to provide TPF with a puzzle to solve, it is required to describe such puzzle by including the following components:
- A set of entities: Entities are those elements whose behavior or properties must be modified or mutated in order for the puzzle's solution to be found. For instance, in the N-Puzzle game, the entities are the various labeled square tiles that must be slid and arranged into a certain order.
- An environment: It is the place where entities live and evolve. An environment along with the set of entities represent a state at a certain time. For instance, in the N-Puzzle game, the environment is the actual board that holds the square tiles whose order determines the state.
- A set of transformations: Transformations describe how entities' behavior or properties mutate from a given state, thus being responsible for expanding such state into new ones through time. In the N-Puzzle game, transformations describe that square tiles must be slid vertically or horizontally and that no square tile should occupy the space of another one.
- Entity retriever: It determines which are the first/next entities on which to apply transformations.
- Description of the solution: It is the final state which must be reached by expanding states. It is represented either by a still goal state or by the constraints that must be satisfied. In the N-Puzzle game, a solution might be described by the final order into which square tiles must be arranged.
- An initial state: It is the first state which will be expanded by iteratively applying transformations on its set of entities, therefore producing more states that will form a tree data structure.
As mentioned, the components above conform a tree data structure that must be traversed while searching for a solution, either by meeting a goal state or by satisfying constraints. In that sense, the following parameters are required:
- The search algorithm: The algorithm, either BFS or DFS, to be used for traversing through the tree formed by the various states.
- An heuristic function: A function that computes how close a given state is to the goal state or how well it satisfies the constraints in order to be considered as a solution. This function helps for determining the next immediate states on which transformations should be applied, therefore preventing less-close states from being expanded. If no function is provided, then inevitably and eventually, a solution may be brute-forcedly found. The output of this function is called heuristic value.
- The heuristic priority: A parameter that determines which states to expand first based on their heuristic values, meaning either the ones with the greatest heuristic value or the ones with the smallest heuristic value.
- A summary function: A function that computes a unique identifier for a given state. This identifier is used to keep track of states already expanded, therefore preventing from falling into endless loops.
Main code components
The above concepts are implemented in TPF's code through several interfaces and classes, such as:
IEntity: Interface that represents an entity. It exposes no members, as its intent is to set a "common type" on value object classes, allowing them to flow through TPF.
IEnvironment: Interface that represents an environment implemented by, as an example, an n-dimensional space (either an array, a matrix, a hypercube, etc. Take a look at MultidimensionalSpaceLib for an implementation of such).
ITransformation: Interface that exposes a transformation definition.
IDescriptor: Interface that bundles up the components required to describe a puzzle; thus, it exposes: the set of transformations, the entity retriever and the solution description.
IParameters: Interface that bundles up the parameters to perform the tree search; thus, it exposes: the search algorithm, the heuristic function, the heuristic priority and the summary function.
TransformationResult: Class that holds the state resulting from applying a transformation on a given, different, state. It represents a step.
Solution: Class that contains the sequence of steps that reach a solution.
ISolver: Interface that exposes methods to find one or more solutions for a puzzle in either a synchronous or asynchronous fashion.
Other, yet important, code components
EntityCollection: A collection of
Descriptor: Base class that abstractly implements
IDescriptor. It is recommended that custom puzzle descriptors inherit from this class.
StandaloneDescriptor: Class that inherits from
Descriptorand whose behaviour should be implemented through delegates.
Transformation: Base class that abstractly implements
ITransformation. It is recommended that custom puzzle transformations inherit from this class.
StandaloneTransformation: Class that inherits from
Transformationand whose behaviour should be implemented through delegates.
TransformationCollection: A collection of
Parameters: Base class that abstractly implements
IParameters. It is recommended that custom parameter classes inherit from this class.
StandaloneParameters: Class that inherits from
Parametersand whose behaviour should be implemented through delegates.
Solver: Class that implements
ISolver, which performs the tree search by a provided
IDescriptorobject and under a provided
IParametersobject. As an argument for the search, it receives the game's initial state of type
The following links provide an outline based on steps about how to code with TPF.
- Code using VB.NET.
- Code using C#.
Once a man said:
May there be an API reference? Let there be an API reference!
And that man had to write an API reference (that man was me).
Find details on TPF's code
public members in the following links.