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?

  • $\begingroup$ 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. $\endgroup$ – David Richerby Aug 22 '15 at 21:03
  • $\begingroup$ @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. $\endgroup$ – user3719857 Aug 22 '15 at 21:19
  • 2
    $\begingroup$ OK. So this is just a graph reachability problem. Use your favourite algorithm. $\endgroup$ – David Richerby Aug 22 '15 at 21:53

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.