Modification in knight's tour problem

Question

So i have a modified knight's tour problem. The problem is the following , is there an algorithm that can give you the route(if possible the shortest) from (1,1) to (n,m) in a chessboard of the knight piece? And also if some blocks are blocked Eg. i have 3x5 chessboard and the blocks (2,3) and (2,5) are blocked. Is there a possible route for my knight to go from (1,1) to (3,5) without my knight stepping on the denied blocks( it can go through them but not stay on them)

Answer 1

Sure. Your chessboard (or the unblocked cells) form a graph, where each cell is a vertex of the graph, and each allowed knight-move from one node to another defines an edge. The shortest path for the knight then can be found by a simple breadth-first search.

To implement this, use a 2D integer array for representing the grid. Simply assign the value zero to the starting cell, then determine all cells reachable in one move from there and mark them with 1, then loop through all 1 cells, determine all cells reachable in one move from there which were not visited before and mark them with "2", and so on, until you reached the final node (n,m). You will need some special values indicating blocked cells and cells not visited so far.

To get the final path from the 2D array, start a search at (n,m). Lets say this cell got the number k, so look for a knights-move neighbour with value k-1, then from there for a neighbour with value k-2, and so on. This will produce the path you were looking for in reverse order.