Part 2 took about 35 minutes of running time to get the answer, but it gives the right answer :) Since the board for part 2 is way bigger, A star algorithm would do the trick. Here I was inspired by the dijkstra algorithm, which does the job. If you have any questions regarding my code, feel free to ask in the comments :D