Getting the shortest paths for chess pieces on n*m board I originally posted this question of stackoverflow but I was suggested to post it here.
So:
I am stuck solving a task requiring me to calculate the minimal number of steps required to go from point A to point B with different chess pieces on a n*m board that has obstacles and save the all the shortest paths.
So far I have an algorithm that for all squares calculates the amount of steps to reach them:
Example for a knight starting from "A2" (the square marked with zero). Obstacles are marked with "-2" and free squares with "-1"
Before algorithm: 
https://dl.dropbox.com/u/65978956/before.JPG
After algorithm: 
https://dl.dropbox.com/u/65978956/after.JPG
The algorithm looks like this:
public int[,] BFS(int[,] chessBoard, Tuple<int, int> startXY, int obstacles, int piece) {
  int dimensionX = chessBoard.GetLength(0);
  int dimensionY = chessBoard.GetLength(1);

  // Look at all the movements a knight can make
  int[] knightMovementY = { -2, -2, -1, -1, 1, 1, 2, 2 };
  int[] knightMovementX = { -1, 1, -2, 2, -2, 2, -1, 1 };
  var allMoves = new Tuple<int[],int[]>(knightMovementX, knightMovementY);

  chessBoard[startXY.Item1, startXY.Item2 - 1] = 0;
  int cnt = dimensionX * dimensionY - obstacles - 1;
  int step = 0;

  // loop until the whole board is filled
  while (cnt > 0) {
    for (int x = 0; x < dimensionX; x++) {
      for (int y = 0; y < dimensionY; y++) {
        if (chessBoard[x, y] == step) {
          for (int k = 0; k < allMoves.Item1.Length; k++) {
            int dx = allMoves.Item1[k] + x, dy = allMoves.Item2[k] + y;
            if (dx >= 0 && dx < dimensionX && dy >= 0 && dy < dimensionY) {
              if (chessBoard[dx, dy] == -1) {
                chessBoard[dx, dy] = step + 1;
                cnt--;
              }
            }
          }
        }
      }
    }
    step++;
  }
  return chessBoard;
}   

The algorithm works also for the king, but for the queen, rook and bishop I need something else, because they can move many squares at a time and cannot jump over obstacles. 
I am very thankful for suggestions as to what I am supposed to do to solve this problem for the queen, bishop and rook and how to save the shortest paths from the picture "after algorithm" to an array.
I have been looking for days and know that A* algorithm is often used for finding paths, but I don't know how it is going to work when some chess pieces can move such large distances in one move.
 A: Here's a recursive process to find the number of moves from point $X$ to point $Y$  in a grid $G$ with obstacles $O$.  
Search algorithms work by generation the set of squares that can be reached in $n$ moves.
Let $B_0 = \{X\}$ - the border of expansion, $I_0 = \emptyset$ - interior, $E_0 = (G / O) / B_0$ -exterior.
Let $f$ - a function such that for any $g \in G$, $f(g)$ is the set of squares that can be reached from $g$ in one move. This function is the definition of the chess piece you use.  
Now, iterate:
$B_n = \bigcup \limits_{x \in B_{n-1}} f(x) \cap E_{n-1}$
$I_n = I_{n-1} \cup B_{n-1}$
$E_n = E_{n-1} / B_n$   
Continue until $Y \in B_n$ or $B_n = \emptyset$. In the first case $\text{distance}(X, Y) = n$, in the second, there is no path from $X$ to $Y$.
I hope that explains the general idea. There is plenty of code examples for pathfinding problems. Note that instead of sets of squares, lists of Nodes are used, where a Node is an object containing the position of a square, a reference to the Node that generated it, for the purposes of backtracking and also a priority number if heuristics are used. Heuristic is the simple idea that if $Y$ lies to the left from $X$, the path from $X$ to $Y$ most likely goes to the left (which is not true in case of obstacles). There isn't much point to use heuristics here since $f$ is usually not trivial and the grid is small.
