If you can't check the diagonals then there is really know way to know if the other is there with absolute certainty.
Two ideas come to mind:
You could eliminate the spots where the other character is not at by marking the spots in the array you check with a letter. If that letter is there then you have checked it. however if the other character is moving this will not work.

Another thought is if you can still check horizontally and vertically then find the other character that way then move to a position you can attack from. Try and use walls to corner the other.

What is the board size?