These puzzles are small enough that they can be solved with any kind of search algorithm (breadth-first, depth-first, etc.). We performed a depth-first search using a recursive backtracker, marking squares visited when we passed them (to avoid loops) and unvisited when we backtracked. The wrinkle here is that you have to keep track of your orientation to get the legal set of moves, and you also have to keep track of the orientation when marking a square as visited. For example, if you visit square ~(2,2)~ facing upwards, that is different than if you visit it facing right.

There are a number of ways you can keep track of this visited list, but the most efficient will make use of a grid where each grid has some way of setting a flag or marker for each of the four orientations.

One way to do this is to have each grid square be an int that starts off as zero. Then you can designate one bit in the underlying binary representation for each direction. For example, the least significant bit (the "1" bit) could be up, then the next ("2") could be down, then the next two ("4", "8") could be the left and right.

If you are at location ~(2,2)~ facing down and you want to check if you've been here before, use the "bitwise" AND operation available in most languages (this would be visited[2][2] & 2 in Java). To mark the square as visited, facing up, add ~2~. To unmark it, subtract ~2~.

Example: You're at square ~(2,2)~ and you've already been here facing left and right. This means that visited[2][2] must be ~12 = 4+8~ which is ~1100~ in binary. You do a bitwise AND with ~2~ to see if you've been here before facing down. Down is ~2~ which is ~0010~ in binary. Bitwise AND does an AND operation on every bit in the two operands, so the result is ~0~, which means you haven't been here before. You add ~2~ to visited[2][2] and now you get ~14~, which is ~1110~ in binary. If you did bitwise AND again, the result would be ~2~ instead of ~0~.

https://en.wikipedia.org/wiki/Bitwise_operation