Now you’re a pro with DFS and BFS. Let’s try using our search algorithms on a real problem.
For this project, you’ll need to use a data structure that’s similar (but not identical) to a binary tree. For a summary of a few different examples, reference this article.
A knight in chess can move to any square on the standard 8x8 chess board from any other square on the board, given enough turns (don’t believe it? See this animation). Its basic move is two steps forward and one step to the side. It can face any direction.
All the possible places you can end up after one move look like this:
Your task is to build a function
knight_moves that shows the simplest possible way to get from one square to another by outputting all squares the knight will stop on along the way.
You can think of the board as having 2-dimensional coordinates. Your function would therefore look like:
knight_moves([0,0],[1,2]) == [[0,0],[1,2]]
knight_moves([0,0],[3,3]) == [[0,0],[1,2],[3,3]]
knight_moves([3,3],[0,0]) == [[3,3],[1,2],[0,0]]
> knight_moves([3,3],[4,3]) => You made it in 3 moves! Here's your path: [3,3] [4,5] [2,4] [4,3]