# TreeProblemFramework - Usage guide

## Introduction

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).**

## Part 1

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

### Setting parameters

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.

## Part 2

### Main code components

The above concepts are implemented in TPF's code through several interfaces and classes, such as:

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.`IEntity`

:Interface that represents an environment implemented by, as an example, an`IEnvironment`

:*n*-dimensional space (either an array, a matrix, a hypercube, etc. Take a look at MultidimensionalSpaceLib for an implementation of such).Interface that exposes a transformation definition.`ITransformation`

: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.`IDescriptor`

: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.`IParameters`

:Class that holds the state resulting from applying a transformation on a given, different, state. It represents a step.`TransformationResult`

:Class that contains the sequence of steps that reach a solution.`Solution`

:Interface that exposes methods to find one or more solutions for a puzzle in either a synchronous or asynchronous fashion.`ISolver`

:

### Other, yet important, code components

A collection of`EntityCollection`

:`IEntity`

objects.Base class that abstractly implements`Descriptor`

:`IDescriptor`

. It is recommended that custom puzzle descriptors inherit from this class.Class that inherits from`StandaloneDescriptor`

:`Descriptor`

and whose behaviour should be implemented through delegates.Base class that abstractly implements`Transformation`

:`ITransformation`

. It is recommended that custom puzzle transformations inherit from this class.Class that inherits from`StandaloneTransformation`

:`Transformation`

and whose behaviour should be implemented through delegates.A collection of`TransformationCollection`

:`ITransformation`

objects.Base class that abstractly implements`Parameters`

:`IParameters`

. It is recommended that custom parameter classes inherit from this class.Class that inherits from`StandaloneParameters`

:`Parameters`

and whose behaviour should be implemented through delegates.Class that implements`Solver`

:`ISolver`

, which performs the tree search by a provided`IDescriptor`

object and under a provided`IParameters`

object. As an argument for the search, it receives the game's initial state of type`IEnvironment`

.

### Implementation workflow

The following links provide an outline based on steps about how to code with TPF.

- Code using VB.NET.
- Code using C#.

## API Reference

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.

Namespace | Link |
---|---|

`TreeProblemFramework.Description` |
Visit |

`TreeProblemFramework.Description.Transformations` |
Visit |

`TreeProblemFramework.Solver` |
Visit |