#include <brute_force.h>
Public Member Functions | |
| virtual | ~solver_brute_force () |
| list_t | solve (const position &from, const position &to) |
Static Public Member Functions | |
| static pointer | create (void) |
Private Member Functions | |
| solver_brute_force () | |
| void | ply (const position &from, const position &to, const list_t &progress) |
| solver_brute_force (const solver_brute_force &rhs) | |
| solver_brute_force & | operator= (const solver_brute_force &rhs) |
Private Attributes | |
| list_t | shortest_solution |
Detailed Description
The solver_brute_force class is used to represent the processing required to solve the knight path problem, using a brute force recursive algorithm.
The worst case is that there will be 7**6 paths explored (because 6 is the longest path) and the worst case usually occurs. It would be 8**6, except that some simple anti-backtracking is emplyed.
Note that this is generally O(e**n) where n is the length of the path, and would thus get *much* worse as the size of the board increases. This is because the recursive descent is a depth-first search, and will likely discover longer paths before shorter ones.
This still solves the problem in less than a second, on a relatively modern laptop; faster than a human can do it.
Definition at line 41 of file brute_force.h.
Constructor & Destructor Documentation
| solver_brute_force::~solver_brute_force | ( | ) | [virtual] |
The destructor.
Definition at line 24 of file brute_force.cc.
| solver_brute_force::solver_brute_force | ( | ) | [private] |
The default constructor. It is private on purpose, use a create class method instead.
Definition at line 29 of file brute_force.cc.
| solver_brute_force::solver_brute_force | ( | const solver_brute_force & | rhs | ) | [private] |
The copy constructor. Do not use.
- Parameters:
-
rhs The right hand side of the initialization.
Member Function Documentation
| solver::pointer solver_brute_force::create | ( | void | ) | [static] |
The create class method is used to create new dynamically allocated instances of this class.
Definition at line 35 of file brute_force.cc.
| solver_brute_force& solver_brute_force::operator= | ( | const solver_brute_force & | rhs | ) | [private] |
The assignment operator. Do not use.
- Parameters:
-
rhs The right hand side of the assignment.
| void solver_brute_force::ply | ( | const position & | from, |
| const position & | to, | ||
| const list_t & | progress | ||
| ) | [private] |
The ply method is used to perform one ply of recursive analysis. The shortest path found is store into the shortest_solution instance variable.
- Parameters:
-
from The position to start from to The position to finish at. progress The cumulative path so far, from earlier ply()s.
Definition at line 63 of file brute_force.cc.
| solver::list_t solver_brute_force::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.
Definition at line 42 of file brute_force.cc.
Member Data Documentation
list_t solver_brute_force::shortest_solution [private] |
The shortest_solution instance variable is used to remember the shortest path found between the two points given to the solve method. It is set by the ply method when it finds a new solution.
Definition at line 73 of file brute_force.h.
The documentation for this class was generated from the following files:
- /home/archives/knight-path/branch.1/branch.0/delta5682.018/knight-path/solver/brute_force.h
- /home/archives/knight-path/branch.1/branch.0/delta5682.018/knight-path/solver/brute_force.cc
