The challenge was to find the shortest number of moves required to travel from any given start square to any given destination on a chess board, by only taking knight moves (L-shaped moves). My solution to this problem will take any two numbers between 0 and 63 (representing the squares on a chess board) and will return the shortest number of knight moves between them.
To give some insight into my journey completing this puzzle, I can divide my main struggles into two parts. The first difficulty was identifying from each position of the knight, what moves are valid. The possible moves that the knight can make vary between 2 to 8; 2 when it is in the corner of the board and 8 when it is within the center 4x4 of the 8x8 chess board. To solve this, I created a valid moves function, and it was helpful to convert the current position into cartesian coordinates in order to create the boundary of the board. The use of a dictionary made this more efficient, as it linked the two numbering systems by key-value pairs, instead of manually converting with several IF statements.
The second difficulty, was more of a self-imposed obstacle, as after solving the problem I wasn't satisfied with the inefficient method I arrived at. I had separate loops to evaluate whether the number of required moves was 1,2,3,4,5 or 6 and by the last one there were 6 nested FOR loops with 6 nested IF statements and all-in-all about 30 variables. This inefficient code was what I ended up submitting in the Foobar challenge, because as long as it works it's accepted and I was running out of time. I ended up coming back to this problem at a later date to make it more efficient, because I felt that the repetitiveness of my code could be replaced with recursion. The trouble, however, was I when I tried to simply combine all the nested loops into one recursive function, one entire route was being explored at a time giving an answer that was not neccessarily the minimum move solution. What was required instead was for all the possible positions at a given step/move-number to be compared against the destination square before moving on to the next step/move-number.
Thus, I introduced a step variable that stored all the possible positions after a step/move-number and then compared them all at once against the destination before moving on. A temp variable was used to clear the contents in the step variable before moving on to the next move, so that old moves were not re-evaluated every-time. At each recursion level a counter variable was incremented, which kept a count of which step/move-number we were on.
EDIT: Reflecting on this problem now, I have realised that the reason recursion didn't seem suitable in the first instance was that I was trying to implement a Depth-First-Search (DFS) algorithm, whereas when I changed this to solve for one level at each time -a Breadth-First-Search (BFS) algorithm- I could correctly translate my inefficient code into a recursive function.