# Supplemental notes for the Knight's Travails Project

We are going to create a data structure that makes it easy to find a path that a knight could take from one position to any other position on the board.

There are 20 tests for the first phase of the project (writing the `Node` class that we will use to build our move tree). You can run these tests alone with the command:

python -m unittest test/test_node.py

There are 17 tests for the following three phases. You can run just those tests with the following command.

python -m unittest test/test_path_finder.py

**Important**: The instructions tell you to create a file called `path_finders.py` for Phase 2, but the tests expect you to call the file `path_finder.py`.

## Phase 1

(notes under construction)
- The tests expect you to write depth-first search recursively, but the instructions never mention this. The iterative solution to depth-first search is perfectly valid, but if you want the tests to pass you will have to write it recursively.

## Phase 2
### `get_valid_moves`:
With this method, we want to get a list of every position that could result from moving a knight once. This method takes one argument (in addition to `self`), which is a tuple representing the initial position to move from. We aren't taking into account the starting position of the `KnightPathFinder` instance, or the set of `_considered_positions` yet—just the position that was passed in as an argument.

This method returns a list of tuples—each tuple is an `(x,y)` coordinate on the chess board. There are never more than 8 valid moves, but if the knight is close to the edge there will be fewer.

Relatively speaking, the set of possible moves would consist of the following list. You would just need to add each of the x-coordinates to the x-coordinate of the initial position, and add each of the y-coordinates to the y-coordinate of the initial position to get the absolute positions. You will also need to exclude any positions that aren't on the board (so if either coordinate is less than 0 or greater than 7).

possible_moves = [ 
    (-2, -1),
    (-2, 1), 
    (-1, -2), 
    (-1, 2), 
    (1, -2), 
    (1, 2), 
    (2, -1), 
    (2, 1),
]


### `new_move_positions`
The `new_move_positions` method takes in a position as an argument, and returns the set of valid moves from that location that haven't already been considered yet.
1. Use the `get_valid_moves` method get all the moves that would be valid from the given position.
2. Compare that set to the set of positions you have already considered (`self._considered_positions`) to find the ones that are new. Save the set of new move positions to a variable, since we will need to return that set.
3. Update the set of considered positions to include the new positions you just identified.
4. Return the set of new positions from step 2.

## Phase 3

### `build_move_tree`
We want to create a structure that represents every path that a knight could take from our start position.

Starting position tuple (root node):                     (x,y)
                                                      /    |    \ 
Positions that the knight can reach in one move:    (x,y)(x,y)(x,y)
                                                   /  |  \  |  /  \ \
Positions that the knight can reach in two moves: ( )( )( )( )( )( )( )
                                                ... MANY MORE LEVELS ....
until we run out of positions:              ()()()()()()()()()()()()()()()()                   

To do this,
1. We get the `new_move_positions` from our starting location (the value of our root node).
2. Create nodes for each position in the set of new move positions and add them as children to the current node
3. Add those as child nodes to a queue.
4. Continue this process (popping a node off of the queue, getting new move positions from its value, making nodes from those positions, adding them as children to our current node, and adding the nodes to end of queue) on each node in the queue until our queue is empty.

If that sounds a little like a breadth-first search, that's probably because we are using a similar approach. It's not a search, but we are building the tree in a breadth-first way. If we used a stack instead of a queue, and tried to build a depth-first tree, we would wind up with extremely inefficient paths.

Conveniently, we don't need to do extra work to figure out if the positions have been visited before—every time we use `new_move_positions` to get the new move positions, it is automatically checking then updating our considered positions! That means that we'll never put the same position into our tree twice. How convenient!

## Phase 4

### `trace_to_root`

                      (x,y)
                   /    |    \ 
                 (x,y)(x,y)(x,y)
                /  |  \  |  /  \ \
              ( )( )( )( )( )( )( )
            ... MANY MORE LEVELS ....
        ()()()()()()()()()()()()()()()()                   

Assuming our `build_move_tree` was run successfully, we already have a structure which contains a path to every available board position. But how do we use that structure to actually get the single path to given position?

To do that, we need to be able to find the path from a given node in the tree all the way back up to the root node, and return a list of all the nodes that we passed in between.

The `trace_to_root` method takes in a node as an argument—the node whose value is the position we are trying to reach. We make a list that will contain the path that we take back to the root. To start, we add the node that we are given to the list. Then we continue adding the parent of our node, and the parent of that node, continuing until we run out of parents (each node should be added to the front of the list, not the end). Once we've run out of parents, that means we've reached the root node. The function should return that list.

### `find_path`

The `find_path` method takes in a desired end position tuple, and returns a list of positions—starting with the root position, ending with the desired position. We already have the `trace_to_root` function

1. Use one of our search functions from our `Node` class to find the node that corresponds to our desired position.
- NOTE: the path we use when we traverse our move tree to find the node that corresponds to our desired position is NOT the same as the path our knight would take to reach the position. So, we can use either the depth-first search, or the breadth-first search function from our `Node` class—it won't affect the outcome. There will only be one node that has a given position value, so we always will get the same result either way.
2. Once we have located the node of interest, we can use `trace_to_root` to get the sequence of nodes from that position back up to the start.
3. Using the list of nodes from the previous step, we can map over the list to get the values (which are position tuples) rather than the nodes.
4. Return the list of values.

It is worth noting that this strategy will always result in an optimally efficient path, but it won't guarantee which of the equivalently efficient paths you would find.

That is, if you compare the move tree from your KnightPathFinder class to the move tree from the one that a friend wrote, you may not have exactly the same tree. The paths you get will be the same length, however.

For example, if your starting position was `(0,0)`, and your end position was `(3,3)`, there are two valid paths that are equally efficient.

path_finder = KnightPathFinder((0,0))
path_finder.build_move_tree()
path = path_finder.find_path(3,3)
print(path) 
# could return [(0,0), (1,2), (3,3)]
# or it could return [(0,0), (2,1), (3,3)]