Warning: Use of undefined constant fb_replace_wp_version - assumed 'fb_replace_wp_version' (this will throw an Error in a future version of PHP) in /usr/home/heximal/data/www/heximal.ru/public/blog/wp-content/plugins/replace-wp-version/fb-re_wpversion.php on line 39
Chess piece shortest path algorithm | heximal blog

Home > Coding > Chess piece shortest path algorithm

## Chess piece shortest path algorithm

Warning: count(): Parameter must be an array or an object that implements Countable in /usr/home/heximal/data/www/heximal.ru/public/blog/wp-content/plugins/wp-syntax/wp-syntax.php on line 83

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.

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

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

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

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

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

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

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

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