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

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?

• What's the significance of the squares marked $x$? On an $N\times N$ board for $N>3$, the knight can always move from one corner to the other so there's nothing for an algorithm to do. – David Richerby Aug 22 '15 at 21:03
• @DavidRicherby The squares marked $x$ are basically the $1$ in the boolean matrix. The knight can only step on the squares marked with $x$ ( $1$) if he steps on an unmarked square it's game over. – user3719857 Aug 22 '15 at 21:19
• OK. So this is just a graph reachability problem. Use your favourite algorithm. – David Richerby Aug 22 '15 at 21:53