Javascript Question posted in
A very good W3school tutorial can be found here.

How to reconstruct the shortest path with BFS (Javascript) for Knight chess piece?

I’m currently working for a project with TOP and I’m asked to find the shortest path between 2 squares with a Knight on a 8×8 chessboard. Imagine I want to go from 0,0 to 7,7, my algo need to return me the shortest path, with all squares visited relative to this shortest path.

For this project, I’ve created a Graph class with an Adjacency List object. I’ve created an addEdge and addVertex functions and populateGraph and populateEdge functions.

populateGraph create vertexs from 00 to 77 as properties of adjacency List and populateEdges create edges for all properties following the knight moves rules in a chess game.

With this, I can create a BFS function with 2 params ( start and end ) who will give me the number of moves before reaching the end from the start.

For this, I create a queue with source as first element and create a visited Set and knightMove counter at 0.

While my queue is not empty, I take the first element of my queue, if it has been visited, it loop until a fresh element, else if this element is my end, I return my number of moves, else I increase my knightMove, put this element in my visited Set and take his childrens and push them into the queue.

To reach 0.0 to 7.7, it take me 63 moves. To move from 0.0 to 1.2 it take me one move.

I think I could once the ending node has been found, reconstruct the path by working on all the visited squares, but I don’t know how to do this or if this is a good solution.

Here is my BFS :

js
 bfs(source, destination) {
    const queue = [source];
    const result = [];
    const visited = new Set();
    let knightMoves = 0;
    while (queue.length !== 0) {
      let max = queue[0];
      for (let i = 0; i < queue.length; i += 1) {
        if (queue[i] > max) {
          max = queue[i];
        }
      }
      let current = max;

      while (visited.has(current)) {
        current = queue.shift();
      }
      console.log(visited);
      if (current === destination) {
        console.log('Ive found the position.');
        console.log(`This is number of moves before found : ${knightMoves}`);
        return;
      }
      knightMoves += 1;

      visited.add(current);

      const neighbor = this.adjacencyList[current];

      neighbor.forEach((value) => {
        if (visited.has(value)) {
          return;
        }

        queue.push(value);
      });
    }
  }
Tags:

2

Answers


  1. 0

    You can simply store the coordinate of the square from which the move was made to go to every other square. Then the path can be reconstructed in reverse. Alternatively, you can run a DFS where you keep track of the current path instead.

    A simplified version of your code that handles this:

    const from = {}, dist = {};
dist[source] = 0;
while (queue.length && !(destination in from)) {
    const current = queue.shift();
    for (const next of this.adjacencyList[current]) {
        if (!(next in from)) {
            from[next] = current;
            dist[next] = dist[current] + 1;
            queue.push(next);
        }
    }
}
console.log('Number of moves:', dist[destination]);
const path = [];
for (let curr = destination; curr != null; curr = from[curr])
    path.push(curr);
// Now iterate in reverse to print the path

    Note that is is a very bad idea to use an array as a queue: removing from the front takes linear, not constant, time.

    Login or Signup to reply.
  2. 0

    To reach 0.0 to 7.7, it take me 63 moves.

    That is far from optimal. The target can be reached in 6 moves.

    To reconstruct the path, keep track where you came from whenever you mark a square as visited.

    Similar to the other answer, here is one that doesn’t use a queue, but uses two arrays. Also, I didn’t build a graph, but looked for valid knight jumps while performing BFS. The square positions in bfs are single integers from 0 to 63. There are conversion functions from/to row/col coordinates.

    const knightJumps = [-17, -15, -10, -6, 6, 10, 15, 17];

function bfs(source, destination) {
    const cameFrom = Array(64).fill(-1);
    let frontier = [destination];
    cameFrom[destination] = destination;
    while (frontier.length && cameFrom[source] < 0) {
        const nextFrontier = [];
        for (const square of frontier) {
            for (const jump of knightJumps) {
                const nextSquare = square + jump;
                // Check whether move is valid and not yet visited
                if (nextSquare % 64 === nextSquare &&
                        Math.abs(square % 8 - nextSquare % 8) < 3 &&
                        cameFrom[nextSquare] < 0) {
                    nextFrontier.push(nextSquare);
                    cameFrom[nextSquare] = square;
                }
            }
        }
        frontier = nextFrontier;
    }
    // Build path
    const path = [source];
    while (source != destination) {
        source = cameFrom[source];
        path.push(source);
    }
    return path;
}

const indexToCoordinates = i => [i >> 3, i % 8];
const coordinatesToIndex = (row, col) => row * 8 + col;

const path = bfs(coordinatesToIndex(0, 0), coordinatesToIndex(7, 7))
             .map(indexToCoordinates);
for (const coordinates of path) console.log(...coordinates);

    The path that is output has these visited squares to go from 0,0 to 7,7:

    0 0
2 1
0 2
1 4
3 5
5 6
7 7

    …so 6 moves in total.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search