Home > Coding > Chess piece shortest path algorithm

Chess piece shortest path algorithm

Recently I had to solve the problem of finding the shortest path from A to B and implement it programmatically. “There exists tons of solutions for sure”, – that what I thought… I was wrong. Few days of searching didn’t give any relevant result. The maximum I have found is some mentions that this problem can be solved by using graphs theory and so called BFS algorithm (breadth first search). In this article I’ll try to analyze this method of finding chess pieces shortest path in details with code examples and explanations.

Let’s formalize the objective first. So, we have a chess board of 8×8 size (actually it’s not so important, the board can be of any size), a number of pieces (obstacles), piece V and piece U. It’s required to find the shortest path of piece V to the position of piece U. Important notice: in this article a minimal number of moves is meant by shortest path.

Objective (no obstacles)

With obstacles

First of all we need to build an undirected graph, the vertices number of which equals to a number of cells to which can be reached by figure V. Such pieces as Rook, Knight, Queen and King can reach any board cell for particular number of moves, which means the vertices number of graph is 64. A Bishop can visit only the cells with the same color as the cell it stands on. So the graph for Bishop will have only 32 vertices. The graph must not contain those cells, which contain obstacle (all pieces except U and V).
Next we have to build graph edges. An edge connects any two vertices. Each vertex needs to be connected with all other vertices of graph, on which it’s possible to make a move with piece U from this vertex. Now we have the graph with all possible moves from all possible locations of piece S.
Let’s create a FIFO (first in first out) queue and place the vertex of graph associated with the location of piece U. Also we need to create a collection of visited (explored) vertices and a dictionary for storing parent vertices (parents). Next we run a while loop while queue is not empty. On each iteration we extract last element from queue which represents a vertex.
Then we extract all edges of this vertex from graph and put them into the queue, but only those that not contained in explored collection. If current vertex matches the position of piece U we exit the BFS loop.
When BFS loop is done we compose a collection of vertices and it’s going to be the shortest path. We start a backward traverse (with the vertex of target piece V) and run a while loop again until parent-variable is null (this will be a signal that a end of the path is found). Inside the while loop body we assign associated value from parents dictionary to the loop variable.
Here is pseudo-code for the solution.

// --- BFS(u, v)-----------------------------
      for each vertex w
      do  flag[w] := false;
          pred[w]  := -1  ;  // predecessor of w
      Q := empty queue;
      flag[u] := true;       // already visited
      enqueue(Q, u)
      while Q not empty
      do    w:= dequeue(Q);
            for each x adjacent to w
                     if flag[x] = false
                        flag[x] := true;
                        pred[x] := w   ;
                        if x = v
                           empty Q;
                           break;
                        else
                           enqueue(Q, x);
 
// --- ReportShortestPath(u, v)---------------
// backward path - v to u:
      current := v;
      do    output current;
            current := pred[currrent];
      while current != -1

Now a JavaScript implementation (why JS? because the project that required this was exactly on JS)

  var bishop_pos = p(3, 5);
  var target_pos = p(3, 1);
 
  var board = [
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, "b", 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, "t", 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0]
  ];
 
  /**************************************
    Chess board logic functions
  ***************************************/
  function p(x, y) {
    return {
      x: x,
      y: y
    };
  }
 
  function pos2int(pos) {
    return pos.y * 10 + pos.x;
  }
 
  function int2pos(intpos) {
    var y = Math.trunc(intpos / 10);
    var x = pos_int - (y * 10);
    return p(x, y);
  }
 
  function cell_color(location) {
    var color = 1;
    if (location.x % 2 == 0 && location.y % 2 == 0)
      color = 1;
    if (location.x % 2 != 0 && location.y % 2 == 0)
      color = 0;
    if (location.x % 2 == 0 && location.y % 2 != 0)
      color = 0;
    if (location.x % 2 != 0 && location.y % 2 != 0)
      color = 1;
    return color;
  }
 
  function board_obj(pos) {
    var res = 0;
    if (pos.x  7 || pos.y  7)
      res = "o";
    else
      res = board[7 - pos.y][pos.x];
    return res;
  }
 
 
  /**************************************
    Major find path functions
  ***************************************/
  var iterations = 0;
  // let's prevent scanning with particular iterations count
  // to avoid very long execution
  var max_iterations_count = 10000;
 
  /*
      ----------------    
      | nw |    | ne |
      ----------------
      |    | Bs |    |
      ----------------
      | sw |    | se |
      ----------------
  */
 
  var nw_vector = p(-1, 1);
  var ne_vector = p(1, 1);
  var se_vector = p(1, -1);
  var sw_vector = p(-1, -1);
 
  function vector_point(pos, vector, shift) {
    return p(pos.x + shift * vector.x, pos.y + shift * vector.y);
  }
 
  function possible_moves_from(pos) {
    var vectors = [{
      active: true,
      vector: se_vector
    }, {
      active: true,
      vector: sw_vector
    }, {
      active: true,
      vector: nw_vector
    }, {
      active: true,
      vector: ne_vector
    }];
    var shift = 1;
    var res = [];
    while (vectors[0].active || vectors[1].active || vectors[2].active || vectors[3].active) {
      for (var j = 0; j < vectors.length; j++) {
        if (vectors[j].active) {
          iterations++;
          var v_pos = vector_point(pos, vectors[j].vector, shift);
          var l_obj = board_obj(v_pos);
          if (l_obj == "o" || l_obj == "b") {
            vectors[j].active = false;
          } else {
            res.push(v_pos.y * 10 + v_pos.x);
          }
        }
      }
      shift++;
    }
    return res;
  }
 
  function search_bfs(original_pos, target_pos) {
    // reset global iterations counter
    iterations = 0;
    var original_pos_int = pos2int(original_pos);
 
    // create undirected graphs with all possible bishop positions
    var vertices = {};
 
    var pos = p(0, 0);
    // if bishop cell color differs from color of left-bottom cell color (A1)
    // than start with cell (A2)
    if (cell_color(pos) != cell_color(original_pos)) {
      pos.x = 1;
    }
 
    // let&#039;s convert cell positions {x: n, y: m} to integer representation
    // int_pos = y+10 + x, e.g. B2 = 1 * 10 + 1 = 11
    var target_pos_int = pos2int(target_pos);
    for (var i = 0; i  7) {
        pos.x = pos.x % 2 == 0 ? 1 : 0;
        pos.y++;
      }
    }
 
    // initialize BFS queue (enqueue bishop position)
    var queue = [original_pos_int];
    // initialize BFS explored nodes collection
    var explored = [original_pos_int];
    // initialize parent nodes map
    var parents = {};
    while (queue.length > 0) {
      iterations++;
      if (iterations >= max_iterations_count) {
        console.log("max iterations exceeded (" + max_iterations_count + "). stop searching");
        return [];
      }
      var pos_int = queue.pop();
      var y = Math.trunc(pos_int / 10);
      var x = pos_int - (y * 10);
      var pos = p(x, y);
      var possible_moves = vertices[pos_int];
      if (possible_moves == null) continue;
      for (var j = 0; j < possible_moves.length; j++) {
        var possible_move = possible_moves[j];
        if (explored.indexOf(possible_move)  1 ? path : [];
  }
 
  var path = search_bfs(bishop_pos, target_pos);
  // переменная path содержит искомый путь
  // если path является пустым массивом, значит заданная клетка недостижима для фигуры

Main routine is search_bfs. It has two arguments: a location of atacking pisce V and the target location U.

An embedded demo is presented next. It contains an implementation of BFS for Bishop shortest path.
You can view or download it here and also on jsfiddle

Categories: Coding Tags: , , , ,
  1. wb77
    January 20th, 2018 at 13:47 | #1

    А почему не выбрал классический алгоритм Дейкстры?

  2. wb77
    January 20th, 2018 at 13:58 | #2

    И еще, мне кажется, нужно ребрам присвоить вес – за сколько ходов фигура добирается до вершины, которую соединяет данное ребро.

  3. wb77
    January 20th, 2018 at 14:02 | #3

    Не, протупил, вес не нужен)
    Условия задачи – как раз это количество ходов и найти)

  4. January 23rd, 2018 at 19:35 | #4

    @wb77, таки да) я не проверял, но интуиция подсказывает, что Дейкстра дороже стоит.