Algortihm for path existence in a N by N board moving with a chess knight

Question

I have a problem which goes like this.

There is an $N$ x $N$ board in which some squares are maked with $x$. The upper left and lower right corner squares are also marked. You have a chess knight with which you want to go from the upper left to the lower right corner, using only marked squares. Find an effective algorithm which determines if such a path exists. The input is a boolean matrix $N$ x $N$, where there is a $1$ if the square is marked.

My first thought is to use recursion to check if such a path exists, but that doesn't sound very effective. Any ideas?

Answer 1

I think that you should run directed floodfill "knight-connected" from both ends using BFS and mark every visited x as 0.

From starting points you check board as knight would move, mark 0 (as it is no longer needed, and if you were there already, there would be shorter path). Add to Queue, and do the same on the other side.

If queue is empty on any side and it has not finished yet it is unreachable.

If array is really boolean, you should check if both queues contain same element, otherwise denote visited elements as 2, and upon reaching such number you have path.

On every move you should increase counter if you need length.

Why directed floodfill? It works similar to this algorithm with different params, and by directed I mean flag where you came from to avoid checking it.