#include <maze.h>
Public Member Functions | |
| virtual | ~solver_maze () |
| list_t | solve (const position &from, const position &to) |
Static Public Member Functions | |
| static pointer | create (void) |
Private Member Functions | |
| solver_maze () | |
| solver_maze (const solver_maze &rhs) | |
| solver_maze & | operator= (const solver_maze &rhs) |
Detailed Description
The solver_maze class is used to represent solving the knigth path problem using techniques more commonly found when building singlely-connected mazes.
Each square on the board is labeled with its distance from the "from" square, and it predecessor. If a new path is found to a square, and it has a shorter distance, that new solution replaces the existing solution. Once all squares are visited, the solution is constructed by tracing backwards from the "to" square.
This algorithm runs in less than 0.7% of the time taken by the brute force search. This is because it only ever visits 64 squares, and does no backtracking at all.
In general, this algorithm is O(n) where n is the length of the path. This is because it does a breadth-first search for paths, exploring the shortest paths before longer paths. As a result, the first path it finds will be the shortest (or equal-shortest, as there are usually multiple solutions of any given length). Given that the length of the path is linear with the edge length of the board, and *not* the square of the edge length, this is a huge advantage over any algorithm that is polynomial in either path length or edge length.
Constructor & Destructor Documentation
| solver_maze::solver_maze | ( | ) | [private] |
| solver_maze::solver_maze | ( | const solver_maze & | rhs | ) | [private] |
The copy constructor. Do not use.
- Parameters:
-
rhs The right hand side of the initialization.
Member Function Documentation
| solver_maze::pointer solver_maze::create | ( | void | ) | [static] |
The create class method is used to create new dynamically allocated instance of the solver_maze class.
| solver_maze& solver_maze::operator= | ( | const solver_maze & | rhs | ) | [private] |
The assignment operator. Do not use.
- Parameters:
-
rhs The right hand side of the assignment.
| solver::list_t solver_maze::solve | ( | const position & | from, |
| const position & | to | ||
| ) | [virtual] |
The solve method is used to calculate the shortest path a knight piece must take between two given positions on a chess board. There are often several equally short paths, the first one found will be returned.
- Parameters:
-
from The position at the start of the path. to The position at the end of the path.
- Returns:
- On success, a list of board positions will be returned; it will be a list of squares through which the Knight passes, the list will include the ending position, but will exclude the starting position (unless from == to). On error, (i.e. when no path is possible) an empty list will be returned.
- Note:
- Behaviour is undefined if either position is not valid.
Implements solver.
The documentation for this class was generated from the following files:
