Match the pairs search algorithm?

I found an interesting pairs matching game at http://xepthu.uhm.vn. The rule is simple, you have to find and connect two identical pokemon but the path between them is not blocked and the direction can't not be changed 3 times. Let's see an example:

开发者_如何学C

I've think alot about the algorithm to check if the path between any 2 selected pokemon is valid but because I'm a newbie so I can't find any solution. Can you suggest me one in C#?

---

This is basically a path finding problem from graph theory. The fields in the grid are the nodes, and all adjacent fields are connected by an edge.

Path finding is a well-known problem, and there are many algorithms that solve this. Since your graph is quite small, the best solution here is probably just a brute force algorithm. A popular path finding algorithm is Dijkstra's algorithm.

---

Brute force: Start at some pokemon and explore all possible ways to see if one leads to an identical pokemon. You can stop exploring a way if the way is blocked or has more than 2 turns.

You'll need some "pointer" pointing to a field in the grid. The pointer can move left, right, up or down, provided that the field in that direction is not blocked. Move the pointer to an adjacent field. Remember where you came from and how many turns you made. Repeat this until you've reached your destination. Backtrack if the number of turns reaches 3. Make sure you don't run in circles.

---

Take a look at planar graphs. You will have to introduce a second condition: no more than four nodes may be traversed (start node - first direction change - second direction change - end node).